Pregunta discreta: dado un grupo arbitrario, encuentre el algoritmo para todos sus subgrupos.

Hablando de un subgrupo específico, para cada elemento del grupo, solo hay dos estados: dentro/no en el subgrupo

Entonces, al cambiar las etiquetas bool de presencia de cada elemento y la ausencia puede generar todos los subgrupos

Por ejemplo, para un subgrupo de un grupo de tres elementos, el conjunto completo significa que todos los elementos están ubicados en el subgrupo, es decir, 111, y solo los dos primeros. es 110 en ese momento, y solo el último subgrupo es 001

De manera similar, para cualquier subgrupo con múltiples elementos, todos los subgrupos se pueden generar cambiando el estado de cada elemento

Lo siguiente El algoritmo considera cada bit de la variable entera como la marca de existencia del elemento, es decir, el tercer bit es 1, lo que indica que el tercer elemento está en este subgrupo:

#include <. /p>

int main()

{

unsigned iLen = 0;

puts("¿El número de elementos de la colección?( 1~31 )");

scanf("%u", &iLen);

if (iLen > 31 || iLen <= 0)

{

puts("fuera de rango");

return -1;

}

ARCHIVO *pFile = fopen("out .txt ", "w");

if (pFile == NULL)

{

puts("Error al abrir el archivo");

return -2;

}

iMax sin signo = 1 << iLen;

para (i sin signo = 1; i < iMax; + + i)

{

for (int j = 0; j < iLen; ++j)

{

if ( ( i >> j) & 1)

{

fprintf(pFile, "%u ", j + 1);

}

}

fputc('\n', pFile);

}

fclose(pFile);

}< / p>

El algoritmo anterior, cuando hay 3 elementos, procesará los primeros tres dígitos. El rango de números enteros compuestos por 3 dígitos es 1 ~ 7 (el conjunto vacío no se procesará), por lo que para 1 ~ 7. cada número, saca cada uno de sus dígitos por turno para determinar si es 1, entonces podrás saber si el elemento correspondiente a este dígito está en el conjunto correspondiente a este número

Por ejemplo

Cuando i es igual a 5, 5 es igual a 101 en binario. El primer y tercer elemento están en el conjunto, pero el segundo no. Este es un subconjunto.

El código anterior puede. solo maneja elementos de 1 a 31 bits, principalmente porque cuando hay demasiados elementos, es imposible enumerarlos todos (n! crece demasiado rápido si tiene que enumerarlos, de manera similar, puede simplemente implementar la suma de números grandes); , y los números grandes van del 1 al n, cada número se trata como un conjunto y cada bit es 1, lo que indica que este elemento está en el conjunto