No busques más por todo internet porque llegaste al lugar adecuado, contamos con la solución que necesitas recibir y sin problema.
Solución:
Parece que está buscando un algoritmo rápido para calcular todas las k-combinaciones. 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 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
Aquí hay una solución bastante divertida que depende de conjuntos de bits. Tal como está, está limitado a conjuntos de tamaño no superior a 32. No creo que sea una limitación práctica, ya que hay una lote de subconjuntos para un conjunto de cardinalidad mayor que 32.
La salida no está en el orden que desea, pero sería bastante fácil de solucionar 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 fragmentos de código están dando vueltas para abordar el problema. Se ha escrito un algoritmo muy agradable en algún código, pero no era C estrictamente limpio y no era portátil a través de UNIX o Linux o cualquier sistema POSIX, por lo tanto, lo limpié y agregué mensajes de advertencia, uso y la capacidad de proporcionar un tamaño establecido y tamaño del sub_conjunto en la línea de comando. También peine[] ha pasado a un puntero más general a un array de enteros y calloc utilizados para poner a cero la memoria necesaria para cualquier tamaño de conjunto que se desee.
Lo siguiente es ISO IEC 9899: 1999 C limpio:
/*********************************************************************
* 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 [email protected] 28 Dec 2012
*
*********************************************************************/
#define _XOPEN_SOURCE 600
#include
#include
/* 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( "bbn" );
/* 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 kn", argv[0] );
printf ( " : Where n is the set size and k the sub set size.n" );
printf ( " : Note that k <= nn" );
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 kn", argv[0] );
printf ( " : Where n is the set size and k the sub set size.n" );
printf ( " : Note that k <= nn" );
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 rápida y trivial con un tamaño de conjunto 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 entero array comb se basa en un sistema de punteros que 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 empujar 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 probar algo más grande, pero las matemáticas parecen correctas, así como el resultado hasta ahora. No dude en hacerme saber si se necesita alguna corrección.
Dennis Clarke
[email protected]
28 dic 2012
Eres capaz de añadir valor a nuestra información asistiendo con tu veteranía en las interpretaciones.