Algorithme d'ensemble d'alimentation à mémoire efficace

Question

Essayant de calculer tous les sous-ensembles (power set) de la chaîne de caractères de 9 lettres 'ABCDEFGHI'.

En utilisant des méthodes récursives standard, mon ordinateur rencontre une erreur de mémoire insuffisante (1 Go) avant de terminer. Je n'ai plus de mémoire physique.

Comment cela peut-il être mieux fait? La langue n'est pas un problème et les résultats envoyés à la sortie standard sont également corrects - il n'est pas nécessaire de les conserver tous en mémoire avant de les sortir.

Answer 1

Il existe une application bijective trivial de l'ensemble des parties de X = {A, B, C, D, E, F, G, H, I} à l'ensemble des nombres compris entre 0 et 2^| X | = 2^9:

cartes Ø à 000.000.000 (base 2)

{A} cartes à 100.000.000 (base 2)

{B} cartes à 010.000.000 (base 2)

{ C} cartes à 001.000.000 (base 2)

...

{I} cartes à 000.000.001 (base 2)

{A, B} mappe 110000000 (base 2)

{A, C} mappe 101000000 (base 2)

...

{A, B, C, D, E , F, G, H, I} cartes à 111.111.111 (base 2)

vous pouvez utiliser cette observation pour créer la puissance comme cela (pseudo-code):

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 cette façon, vous évitez toute récursivité (et, en fonction de ce que vous avez besoin de la puissance pour, vous pouvez même "générer" le powerset sans allouer de nombreuses structures de données - par exemple, si vous avez juste besoin d'imprimer l'ensemble d'alimentation).

Answer 2

J'utiliser diviser pour mieux régner pour cela:

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 cette façon, vous voyez tout de suite que le nombre de solutions est 2^| originalSet | - c'est pourquoi on l'appelle le "power set". Dans votre cas, ce serait 2^9, donc il ne devrait pas y avoir une erreur de mémoire insuffisante sur une machine de 1 Go. Je suppose que vous avez une erreur dans votre algorithme.

Answer 3

je vérifié que cela a fonctionné 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

une petite solution de système

(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))))) 

Ou dans r5rs Scheme, plus d'espace version efficace

(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

Que diriez-vous de cette solution élégante? Étend le code qui génère nCr pour itérer pour r = 1 jusqu'à 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 sortie:

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