内存高效的电源设置算法

Question

尝试计算9个字母的字符串'ABCDEFGHI'的所有子集(幂集).

使用标准递归方法,我的机器在完成之前就会出现内存不足(1GB)错误.我没有更多的物理记忆.

怎么能做得更好？语言没有问题,发送到标准输出的结果也很好 - 在输出之前不需要全部保存在内存中.

Answer 1

从X = {A,B,C,D,E,F,G,H,I}的幂集到0到2 ^ | X |之间的数字集有一个简单的双射映射.= 2 ^ 9:

Ø映射到000000000(基数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
}

通过这种方式,您可以避免任何递归(并且,根据您需要的poweret,您甚至可以"生成"powerset而无需分配许多数据结构 - 例如,如果您只需要打印出电源组) .