メモリ効率の良いパワーセットアルゴリズム

Question

9文字の文字列 'ABCDEFGHI'のすべてのサブセット（power set）を計算しようとしています。

私のマシンは標準的な再帰的な方法を使用して、完了する前にメモリ不足（1GB）エラーが発生します。私には物理的記憶がありません。

これはどのようにして改善できますか？言語は問題ではなく、標準出力に送信される結果も問題ありません。出力する前にすべてをメモリに保持する必要はありません。

Answer 1

のパワーセットから些細な全単射マッピングがありX = {A、B、C、D、E、F、G、H、I} 0と2の間の数の集合へ^ | X | = 2^9：

入出力マップ（ベース2）000000000に対して

{A} 100000000にマッピング（ベース2）

{B} 010000000にマッピング（ベース2）

{ C}は001000000（ベース2）

...にマッピング

{I} 000000001にマッピング（ベース2）

{A、B}が110000000（ベース2）

{A、C}が1.01億にマップ（ベース2）

...

{A、B、C、D、Eにマッピングあなたは避ける。このように

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 
} 

：、F、G、H、I}は111111111（基本2）

あなたは、この（擬似コード）のように設定された電力を作成するには、この観察を使用することができますにマップ任意の再帰（そして、あなたが何を必要とするかに応じて例えば、パワーセットをプリントアウトするだけでよい場合など、多くのデータ構造を割り当てることなくパワーセットを「生成」することさえできるかもしれません。このエレガントな解決策について

Answer 2

私はこのために除算を使用し、征服します：

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

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

その方法は、あなたがすぐに解決策の数が2であることがわかり^ | originalSet |それが「パワーセット」と呼ばれる理由です。あなたの場合、これは2^9になるので、1GBのマシンにメモリ不足のエラーがあってはいけません。私はあなたのアルゴリズムにいくつかの誤りがあると思います。

Answer 3

私は、これがうまくいったことを確認：

#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

少しスキームソリューション

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

またはR5RSスキーム、より多くのスペース効率的なバージョンで

(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

どのように？ nCrを生成するコードを拡張して、r = 1まで繰り返して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; 
} 

出力：

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