Algoritmo de querido: enumerar todos los subconjuntos de un conjunto en orden creciente de sumas

Question

Estoy en busca de un algoritmo, pero no sé bien cómo ponerlo en práctica. Lo que es más importante, no sé qué google. Peor aún, no estoy seguro de que se puede hacer en el polinomio de tiempo.

Dado un conjunto de números (dicen, {1, 4, 5, 9}), quiero enumerar todos los subconjuntos de este conjunto (su juego de poder, en realidad) en un orden determinado: aumento de la suma de los elementos.

Por ejemplo, dada {1, 4, 5, 9}, los subconjuntos deben ser enumerados en este orden, "más pequeño" de los conjuntos de primera:

{} = 0

{1} = 1

{4} = 4

{5} = 5

{1, 4} = 5

{1, 5} = 6

{9} = 9

{4, 5} = 9

{1, 9} = 10

{1, 4, 5} = 10

{4, 9} = 13

{5, 9} = 14

{1, 4, 9} = 14

{1, 5, 9} = 15

{4, 5, 9} = 18

{1, 4, 5, 9} = 19

Esto se siente como una impía mezcla entre una búsqueda en anchura y una búsqueda en profundidad, pero no puedo envolver mi cabeza alrededor de la forma adecuada para la mezcla de estas dos estrategias de búsqueda.

Mi espacio de búsqueda es muy grande ($2^{64}$ elementos) así que no puedo precompute de todos ellos frente y ordenarlas. En esa nota, yo también no es necesario enumerar la totalidad del espacio de búsqueda -- los más de 4.096 subconjuntos está bien, por ejemplo.

¿Alguien puede dar alguna sugerencia o incluso alguna pista para google? Muchas gracias.

Answer 1

He aquí un algoritmo. La idea básica es que cada número en la serie original recorre la lista de subconjuntos usted ya ha encontrado, tratando de ver si añadiendo que el número para el subconjunto es en la actualidad teniendo en cuenta los resultados en el menor subconjunto suma no se ha encontrado.

El algoritmo utiliza las cuatro matrices (todos los cuales son indexados comenzando con $0$).

1. $N$ se compone de los números en la serie original; es decir, $N = [1, 4, 5, 9]$ en su ejemplo.
2. $L$ es la lista de subconjuntos encontrados hasta la fecha.
3. $A[i]$ contiene el subconjunto que se $N[i]$ está estudiando en la actualidad.
4. $S[i]$ es la suma de los elementos del subconjunto $i$$L$.

Algoritmo:

1. Inicializar $N$ a los números en la serie original, todas las entradas de $A$ a $0$, $L[0] = \{\}$, $S[0] = 0$. Deje $j = 1$.
2. Para la iteración $j$ encontrar el mínimo de $S[A[i]] + N[i]$ sobre todos los números de $N[i]$ en la serie original. (Este se encuentra el subgrupo con suma más pequeña aún no $L$.) Desempate se hace por el número de elementos en el conjunto. Deje $i^*$ denotar la argmin.
3. Deje $L[j] = L[A[i^*]] \cup \{N[i^*]\}$. Deje $S[j] = S[A[i^*]] + N[i^*]$. (Esto de las actualizaciones $L$ $S$ con el nuevo subconjunto.)
4. Aumentar el $A[i^*]$ para el siguiente elemento de la $L$ que no tiene ningún número mayor que $N[i^*]$. Si no hay ninguno, vamos a $A[i^*] =$ NULO. (Este se encuentra el siguiente subconjunto de $L$ a tener en cuenta para el número de $N[i^*]$ acaba de agregar a una existente subconjunto en $L$ a crear el subconjunto acaba de agregar a $L$.)
5. Si todas las entradas en $A[i]$ son NULOS, entonces pare, cosa incremento $j$ e ir al Paso 2.

---

Por ejemplo, aquí están las iteraciones para su ejemplo, junto con el subconjunto de $L$ actualmente apuntado por cada número.

Initialization:     
{}   1, 4, 5, 9

Iteration 1:    
{}   4, 5, 9
{1}  

Iteration 2:  
{}   5, 9
{1}  4 
{4}

Iteration 3:  
{}   9
{1}  4, 5
{4}
{5}

Iteration 4:  
{}   9
{1}  5
{4}
{5}
{1,4}

Iteration 5:  
{}   9
{1}  
{4}  5
{5}
{1,4}
{1,5}

Iteration 6:  
{}   
{1}  9
{4}  5
{5}
{1,4}
{1,5}
{9}

Iteration 7:  
{}   
{1}    9
{4}  
{5}
{1,4}  5
{1,5}
{9}
{4,5}

Iteration 8:  
{}   
{1}    
{4}    9
{5}
{1,4}  5
{1,5}
{9}
{4,5}
{1,9}

Iteration 9:  
{}   
{1}    
{4}    9
{5}
{1,4}  
{1,5}
{9}
{4,5}
{1,9}
{1,4,5}

Y el resto de las iteraciones sólo implican la adición de $9$, sucesivamente, a cada subconjunto ya construidos que no incluye a $9$.

Answer 2

(Demasiado largo para un comentario.)

Nijenhuis y Wilf de la Combinatoria de los Algoritmos de los detalles de un algoritmo para la enumeración de todos los subconjuntos de un conjunto dado, basado en el código Gray (también hay una modificación que hace producir los subconjuntos lexicográficamente). El libro puede ser descargado de forma gratuita desde el enlace que me dio. Puede descargar el FORTRAN rutinas NEXSUB() y LEXSUB() de Skiena de la página web. Algunas modificaciones que sería necesario para tener la salida de resultados en el orden deseado.