內存有效功率集算法

Question

試圖計算9個字母的字符串'ABCDEFGHI'的所有子集（power set）。

使用標準的遞歸方法，我的機器在完成前遇到內存不足（1GB）錯誤。我沒有更多的物理記憶。

這怎麼能做得更好？語言不成問題，並且發送到標準輸出的結果也很好 - 在輸出之前不需要全部保存在內存中。

Answer 1

有從電源組的瑣碎的雙射映射X = {A，B，C，d，E，F，G，H，I}到0和2^| X |之間的數字集合= 2^9：

Ø映射到000000000（基數爲2）

{A}映射到100000000（基數爲2）

{B}映射到0.1億（基數爲2）

{ ç}映射到001000000（基數爲2）

...

{I}映射到000000001（基數爲2）

{A，B}映射到1.1億（基數爲2）

{A，C}映射到1.01億（基數爲2）

...

{A，B，C，d，E ，F，G，H，I}映射到111111111（基數爲2）

您可以使用此觀測創建設置這樣的（僞代碼）電源：

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 
} 

這樣可以避免任何遞歸（並根據你需要的權力設置爲，您甚至可以在不分配許多數據結構的情況下「生成」powerset，例如，如果您只需要打印出電源設置）。

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