combinación sin repetición de n elementos sin uso para ... para ...
https://stackoverflow.com/questions/8316479
-
25-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Quiero cargar en una lista la combinación de n número sin repetición, dando a la entrada los elementos y el grupo. Por ejemplo, con 4 elementos [1,2,3,4], tengo para:
Group 1: [1][2][3][4];
Group 2: [1,2][1,3][1,4][2,3][2,4][3,4];
Group 3: [1,2,3][1,2,4][1,3,4][2,3,4]
Group 4: [1,2,3,4]
Ahora, lo he resuelto usando bucle anidado para, por ejemplo, con el grupo 2, escribo:
for x1 := 1 to 3 do
for x2 := Succ(x1) to 4 do
begin
// x1, x2 //
end
o para el grupo 3, escribí:
for x1 := 1 to 2 do
for x2 := Succ(x1) to 3 do
for x3 := Succ(x2) to 4 do
begin
// x1, x2, x3 //
end
Y así para otros grupos. En general, si quiero hacerlo para el grupo N, como puedo hacer, sin escribir n procedimientos con bucles anidados? He pensado en un doble tiempo ... . ¿Quién puede darme algunos sugerencias al respecto? Muchas gracias.
Solución
Parece que está buscando un algoritmo rápido para calcular todas las combinaciones de K. El siguiente código Delphi es una traducción directa del código C que se encuentra aquí: Generación de combinaciones. ¡Incluso arreglé un error en ese código!
program kCombinations;
{$APPTYPE CONSOLE}
// Prints out a combination like {1, 2}
procedure printc(const comb: array of Integer; k: Integer);
var
i: Integer;
begin
Write('{');
for i := 0 to k-1 do
begin
Write(comb[i]+1);
if i<k-1 then
Write(',');
end;
Writeln('}');
end;
(*
Generates the next combination of n elements as k after comb
comb => the previous combination ( use (0, 1, 2, ..., k) for first)
k => the size of the subsets to generate
n => the size of the original set
Returns: True if a valid combination was found, False otherwise
*)
function next_comb(var comb: array of Integer; k, n: Integer): Boolean;
var
i: Integer;
begin
i := k - 1;
inc(comb[i]);
while (i>0) and (comb[i]>=n-k+1+i) do
begin
dec(i);
inc(comb[i]);
end;
if comb[0]>n-k then// Combination (n-k, n-k+1, ..., n) reached
begin
// No more combinations can be generated
Result := False;
exit;
end;
// comb now looks like (..., x, n, n, n, ..., n).
// Turn it into (..., x, x + 1, x + 2, ...)
for i := i+1 to k-1 do
comb[i] := comb[i-1]+1;
Result := True;
end;
procedure Main;
const
n = 4;// The size of the set; for {1, 2, 3, 4} it's 4
k = 2;// The size of the subsets; for {1, 2}, {1, 3}, ... it's 2
var
i: Integer;
comb: array of Integer;
begin
SetLength(comb, k);// comb[i] is the index of the i-th element in the combination
//Setup comb for the initial combination
for i := 0 to k-1 do
comb[i] := i;
// Print the first combination
printc(comb, k);
// Generate and print all the other combinations
while next_comb(comb, k, n) do
printc(comb, k);
end;
begin
Main;
Readln;
end.
Producción
{1,2}
{1,3}
{1,4}
{2,3}
{2,4}
{3,4}
Otros consejos
Aquí hay una solución bastante divertida que depende de bitsets. Tal como está, se limita a conjuntos de tamaño no mayores a 32. No creo que sea una limitación práctica ya que hay un lote de subconjuntos para un conjunto de cardinalidad mayor que 32.
La salida no está en el orden que desee, pero eso sería bastante fácil de remediar si le importa.
program VisitAllSubsetsDemo;
{$APPTYPE CONSOLE}
procedure PrintBitset(Bitset: Cardinal; Size: Integer);
var
i: Integer;
Mask: Cardinal;
SepNeeded: Boolean;
begin
SepNeeded := False;
Write('{');
for i := 1 to Size do begin
Mask := 1 shl (i-1);
if Bitset and Mask<>0 then begin
if SepNeeded then begin
Write(',');
end;
Write(i);
SepNeeded := True;
end;
end;
Writeln('}');
end;
procedure EnumerateSubsets(Size: Integer);
var
Bitset: Cardinal;
begin
for Bitset := 0 to (1 shl Size)-1 do begin
PrintBitset(Bitset, Size);
end;
end;
begin
EnumerateSubsets(4);
end.
Producción
{}
{1}
{2}
{1,2}
{3}
{1,3}
{2,3}
{1,2,3}
{4}
{1,4}
{2,4}
{1,2,4}
{3,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
Y aquí hay una variante que solo enumera los subconjuntos de una cardinalidad específica:
function SetBitCount(Bitset: Cardinal; Size: Integer): Integer;
var
i: Integer;
Mask: Cardinal;
begin
Result := 0;
for i := 1 to Size do begin
Mask := 1 shl (i-1);
if Bitset and Mask<>0 then begin
inc(Result);
end;
end;
end;
procedure EnumerateSubsets(Size, NumberOfSetBits: Integer);
var
Bitset: Cardinal;
begin
for Bitset := 0 to (1 shl Size)-1 do begin
if SetBitCount(Bitset, Size)=NumberOfSetBits then begin
PrintBitset(Bitset, Size);
end;
end;
end;
begin
EnumerateSubsets(4, 2);
end.
Producción
{1,2}
{1,3}
{2,3}
{1,4}
{2,4}
{3,4}
Esta parece ser una pregunta que surge una y otra vez y algunos bits de código están dando vueltas sobre esa dirección del problema. Se ha escrito un algoritmo muy agradable en algún código, pero no era estrictamente limpio C y no portátil en Unix o Linux o cualquier sistema POSIX, por lo tanto, lo limpié y agregé mensajes de advertencia, uso y la capacidad de proporcionar un tamaño establecido y Tamaño de sub_set en la línea de comando. También se ha realizado una transición a un puntero más general a una variedad de enteros y Calloc utilizado para cero la memoria necesaria para cualquier tamaño establecido que uno desee.
Lo siguiente es ISO IEC 9899: 1999 C Clean:
/*********************************************************************
* The Open Group Base Specifications Issue 6
* IEEE Std 1003.1, 2004 Edition
*
* An XSI-conforming application should ensure that the feature
* test macro _XOPEN_SOURCE is defined with the value 600 before
* inclusion of any header. This is needed to enable the
* functionality described in The _POSIX_C_SOURCE Feature Test
* Macro and in addition to enable the XSI extension.
*
* Compile with c99 or with gcc and CFLAGS to include options
* -std=iso9899:199409 -pedantic-errors in order to ensure compliance
* with ISO IEC 9899:1999 C spec.
*
* Code cleanup and transition to comb as a pointer to type ( int * )
* array by Dennis Clarke dclarke@blastwave.org 28 Dec 2012
*
*********************************************************************/
#define _XOPEN_SOURCE 600
#include <stdio.h>
#include <stdlib.h>
/* Prints out a combination like {1, 2} */
void printc( int *comb, int k) {
int j;
printf("{ ");
for ( j = 0; j < k; ++j )
printf("%d , ", *( comb + j ) + 1 );
printf( "\b\b}\n" );
} /* printc */
/**********************************************************************
next_comb(int comb[], int k, int n)
Generates the next combination of n elements as k after comb
comb => the previous combination ( use (0, 1, 2, ..., k) for first)
k => the size of the subsets to generate
n => the size of the original set
Returns: 1 if a valid combination was found
0, otherwise
**********************************************************************/
int next_comb( int *comb, int k, int n) {
int i = k - 1;
++*( comb + i );
while ( ( i >= 0 ) && ( *( comb + i ) >= n - k + 1 + i ) ) {
--i;
++*( comb + i );
}
if ( *comb > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
return 0; /* No more combinations can be generated */
/* comb now looks like (..., x, n, n, n, ..., n).
* Turn it into (..., x, x + 1, x + 2, ...) */
for (i = i + 1; i < k; ++i)
*( comb + i ) = *( comb + ( i - 1 ) ) + 1;
return 1;
} /* next_comb */
int main(int argc, char *argv[]) {
int *comb, i, n, k;
n = 9; /* The size of the set; for {1, 2, 3, 4} it's 4 */
k = 6; /* The size of the subsets; for {1, 2}, {1, 3}, .. it's 2 */
if ( argc < 3 ) {
printf ( "\nUSAGE : %s n k\n", argv[0] );
printf ( " : Where n is the set size and k the sub set size.\n" );
printf ( " : Note that k <= n\n" );
return ( EXIT_FAILURE );
}
n = atoi ( argv[1] );
k = atoi ( argv[2] );
if ( k > n ) {
printf ( "\nWARN : k > n is not allowed.\n" );
printf ( "USAGE : %s n k\n", argv[0] );
printf ( " : Where n is the set size and k the sub set size.\n" );
printf ( " : Note that k <= n\n" );
return ( EXIT_FAILURE );
}
comb = ( int * ) calloc( (size_t) k, sizeof(int) );
for ( i = 0; i < k; ++i)
*( comb + i ) = i;
/* Print the first combination */
printc( comb, k );
/* Generate and print all the other combinations */
while ( next_comb( comb, k, n ) )
printc( comb, k );
free ( comb );
return ( EXIT_SUCCESS );
}
Uno puede compilar lo anterior en una máquina basada en Opteron, así:
$ echo $CFLAGS
-m64 -g -malign-double -std=iso9899:199409 -pedantic-errors -mno-mmx
-mno-sse -fexceptions -fpic -fvisibility=default -mtune=opteron
-march=opteron -m128bit-long-double -mpc80 -Wl,-q
$ gcc $CFLAGS -o combinations combinations.c
Una prueba trivial rápida con un tamaño establecido de 10 y un subconjunto de 6 será así:
$ ./combinations 10 6 | wc -l
210
Las matemáticas son correctas:
( 10 ! ) / ( ( 10 - 6 )! * ( 6! ) ) = 210 unique combinations.
Ahora que el peine de matriz entero se basa en un sistema de puntero, solo estamos restringidos por la memoria y el tiempo disponibles. Por lo tanto, tenemos lo siguiente :
$ /usr/bin/time -p ./combinations 20 6 | wc -l
real 0.11
user 0.10
sys 0.00
38760
Esto parece correcto:
( 20 ! ) / ( ( 20 - 6 )! * ( 6! ) ) = 38,760 unique combinations
Ahora podemos superar los límites un poco así:
$ ./combinations 30 24 | wc -l
593775
Nuevamente, las matemáticas están de acuerdo con el resultado:
( 30 ! ) / ( ( 30 - 24 )! * ( 24! ) ) = 593 775 unique combinations
Siéntase libre de superar los límites de su sistema:
$ /usr/bin/time -p ./combinations 30 22 | wc -l
real 18.62
user 17.76
sys 0.83
5852925
Todavía tengo que intentar algo más grande, pero las matemáticas se ven correctas y la salida hasta ahora. Siéntase libre de avisarme si se necesita alguna corrección.
Dennis Clarke dclarke@blastwave.org 28 de diciembre de 2012
A menos que no pueda hacer llamadas a funciones con algún requisito, haga esto:
select_n_from_list(int *selected, int n, int *list, int list_size):
if (n==0) {
// print all numbers from selected by traversing backward
// you can set the head to a special value or make the head location
// a static variable for lookup
}
for (int i=0; i<=list_size-n; i++) {
*selected = list[i];
select_n_from_list(selected+1, n-1, list+i+1, list_size-i-1);
}
}
Realmente necesita algún tipo de recursión porque necesita almacenamiento automático para resultados intermedios. Avíseme si hay un requisito especial que haga que esta solución no funcione.
Seguir el enlace que David publicó y haciendo clic me llevó a un artículo donde acuñaban el término "búsqueda del banquero", que parece adaptarse a su patrón.
El artículo proporciona una solución de ejemplo en C ++, utilizando la recursión:
Creé este guión aquí y funcioné muy bien:
$(document).ready(function(){
$("#search").on('click', function(){
var value = $("#fieldArray").val().split(",");
var results = new SearchCombinations(value);
var output = "";
for(var $i = 0; $i< results.length;$i++){
results[$i] = results[$i].join(",");
output +="<li>"+results[$i]+"</li>";
}
$("#list").html(output);
});
});
/*Helper Clone*/
var Clone = function (data) {
return JSON.parse(JSON.stringify(data));
}
/*Script of Search All Combinations without repetitions. Ex: [1,2,3]*/
var SearchCombinations = function (statesArray) {
var combinations = new Array(),
newValue = null,
arrayBeforeLevel = new Array(),
$level = 0,
array = new Clone(statesArray),
firstInteration = true,
indexFirstInteration = 0,
sizeValues = array.length,
totalSizeValues = Math.pow(2, array.length) - 1;
array.sort();
combinations = new Clone(array);
arrayBeforeLevel = new Clone(array);
loopLevel: while ($level < arrayBeforeLevel.length) {
for (var $i = 0; $i < array.length; $i++) {
newValue = arrayBeforeLevel[$level] + "," + array[$i];
newValue = newValue.split(",");
newValue.sort();
newValue = newValue.join(",");
if (combinations.indexOf(newValue) == -1 && arrayBeforeLevel[$level].toString().indexOf(array[$i]) == -1) {
if (firstInteration) {
firstInteration = false;
indexFirstInteration = combinations.length
}
sizeValues++;
combinations.push(newValue);
if (sizeValues == totalSizeValues) {
break loopLevel;
}
}
}
$level++;
if ($level == arrayBeforeLevel.length) {
firstInteration = true;
arrayBeforeLevel = new Clone(combinations);
arrayBeforeLevel = arrayBeforeLevel.splice(indexFirstInteration);
indexFirstInteration = 0;
$level = 0;
}
}
for (var $i = 0; $i < combinations.length; $i++) {
combinations[$i] = combinations[$i].toString().split(",");
}
return combinations;
}*{font-family: Arial;font-size:14px;}
small{font-size:11px}<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<label for="">
<input type="text" id="fieldArray">
<button id="search">Search</button>
<br><small>Info the elements. Ex: "a,b,c"</small>
</label>
<hr>
<ul id="list"></ul>