algorithm - 内存高效的幂集算法

Question

尝试计算 9 个字母字符串 'ABCDEFGHI' 的所有子集（幂集）。

使用标准递归方法，我的机器在完成之前遇到内存不足 (1GB) 错误。我没有更多的物理记忆。

怎样才能做得更好？语言没有问题，发送到标准输出的结果也很好——输出前不需要全部保存在内存中。

score 25 · Accepted Answer

从 X = {A,B,C,D,E,F,G,H,I} 的幂集到 0 到 2^|X| 之间的数字集之间存在一个平凡的双射映射。= 2^9:

Ø 映射到 000000000 (base 2)

{A} 映射到 100000000（以 2 为底）

{B} 映射到 010000000（以 2 为底）

{C} 映射到 001000000（基数 2）

...

{I} 映射到 000000001（以 2 为底）

{A,B} 映射到 110000000（以 2 为底）

{A,C} 映射到 101000000（以 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 的用途，您甚至可以在不分配许多数据结构的情况下“生成”powerset - 例如，如果您只需要打印出 powerset） .

score 1 · Accepted Answer

我会为此使用分而治之：

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 机器上不应出现内存不足错误。我猜你的算法有一些错误。

score 1 · Accepted Answer

一个小方案解决方案

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

score 0 · Accepted Answer

我证实这运作良好：

#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);
  }
}

score 0 · Accepted Answer

这个优雅的解决方案怎么样？扩展生成 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;
}

输出：

algorithm - 内存高效的幂集算法

5 回答 5

Related

Reference