Algoritmo de potencia de memoria eficiente

Question

Intentando calcular todos los subconjuntos (power set) de la cadena de 9 letras 'ABCDEFGHI'.

Utilizando los métodos recursivos estándar, mi máquina se agota el error de memoria (1GB) antes de completar. No tengo más memoria física.

¿Cómo se puede hacer esto mejor? El lenguaje no es un problema y los resultados enviados a la salida estándar también están bien, no es necesario que todo se guarde en la memoria antes de la salida.

Answer 1

Hay una biyectiva de representación trivial desde el conjunto potencia de X = {A, B, C, D, E, F, G, H, I} al conjunto de números entre 0 y 2^| X | = 2^9:

mapas Ø a 000000000 (base 2)

{A} se asigna a 100000000 (base 2)

{B} se asigna a 010000000 (base 2)

{ C} se asigna al 001 000 000 (base 2)

...

{I} se asigna a 000000001 (base 2)

{A, B} se asigna al 110000000 (base 2)

{A, C} se asigna al 101 000 000 (base 2)

...

{A, B, C, D, E , F, G, H, I} se asigna al 111111111 (base 2)

puede utilizar esta observación para crear el poder establecer así (pseudo-código):

Set powerset = new Set(); 
for(int i between 0 and 2^9) 
{ 
    Set subset = new Set(); 
    for each enabled bit in i add the corresponding letter to subset 
    add subset to powerset 
} 

de esta manera se evita cualquier recursión (y, dependiendo de lo que necesite el poder establecido, incluso puede ser capaz de "generar" el conjunto de potencias sin asignar muchas estructuras de datos; por ejemplo, si solo necesita imprimir el conjunto de energía).

Answer 2

me gustaría utilizar divide y vencerás para esto:

Set powerSet(Set set) { 
    return merge(powerSet(Set leftHalf), powerSet(Set rightHalf)); 
} 

merge(Set leftHalf, Set rightHalf) { 
    return union(leftHalf, rightHalf, allPairwiseCombinations(leftHalf, rightHalf)); 
} 

De esa manera, se ve inmediatamente que el número de soluciones es 2^| originalSet | - Es por eso que se llama el "conjunto de poder". En su caso, esto sería 2^9, por lo que no debería haber un error de falta de memoria en una máquina de 1GB. Supongo que tienes algún error en tu algoritmo.

Answer 3

I comprobado que este funcionó bien:

#include <iostream> 

void print_combination(char* str, char* buffer, int len, int num, int pos) 
{ 
    if(num == 0) 
    { 
    std::cout << buffer << std::endl; 
    return; 
    } 

    for(int i = pos; i < len - num + 1; ++i) 
    { 
    buffer[num - 1] = str[i]; 
    print_combination(str, buffer, len, num - 1, i + 1); 
    } 
} 

int main() 
{ 
    char str[] = "ABCDEFGHI"; 
    char buffer[10]; 
    for(auto i = 1u; i <= sizeof(str); ++i) 
    { 
    buffer[i] = '\0'; 
    print_combination(str, buffer, 9, i, 0); 
    } 
} 

Answer 4

esquema de una solución poco

(define (power_set_iter set) 
    (let loop ((res '(())) 
      (s set)) 
    (if (empty? s) 
     res 
     (loop (append (map (lambda (i) 
          (cons (car s) i)) 
          res) 
         res) 
       (cdr s))))) 

O en R5RS Esquema, más eficiente del espacio versión

(define (pset s) 
    (do ((r '(())) 
     (s s (cdr s))) 
     ((null? s) r) 
    (for-each 
     (lambda (i) 
     (set! r (cons (cons (car s) i) 
         r))) 
     (reverse r)))) 

Answer 5

¿Qué tal esta solución elegante? Extiende el código que genera nCr para iterar para r = 1 hasta n!

#include<iostream> 
using namespace std; 

void printArray(int arr[],int s,int n) 
{ 
    cout<<endl; 
    for(int i=s ; i<=n-1 ; i++) 
     cout<<arr[i]<<" "; 
} 

void combinateUtil(int arr[],int n,int i,int temp[],int r,int index) 
{ 
    // What if n=5 and r=5, then we have to just print it and "return"! 
    // Thus, have this base case first! 
    if(index==r) 
    { 
     printArray(temp,0,r); 
     return; 
    } 

    // If i exceeds n, then there is no poin in recurring! Thus, return 
    if(i>=n) 
     return; 


    temp[index]=arr[i]; 
    combinateUtil(arr,n,i+1,temp,r,index+1); 
    combinateUtil(arr,n,i+1,temp,r,index); 

} 

void printCombinations(int arr[],int n) 
{ 
    for(int r=1 ; r<=n ; r++) 
    { 
     int *temp = new int[r]; 
     combinateUtil(arr,n,0,temp,r,0); 
    } 
} 



int main() 
{ 
    int arr[] = {1,2,3,4,5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 

    printCombinations(arr,n); 

    cin.get(); 
    cin.get(); 
    return 0; 
} 

La salida:

1 
2 
3 
4 
5 
1 2 
1 3 
1 4 
1 5 
2 3 
2 4 
2 5 
3 4 
3 5 
4 5 
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 
1 2 3 4 
1 2 3 5 
1 2 4 5 
1 3 4 5 
2 3 4 5 
1 2 3 4 5