内存高效的幂集算法 [英] Memory efficient power set algorithm

问题描述

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

Trying to calculate all the subsets (power set) of the 9-letter string 'ABCDEFGHI'.

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

Using standard recursive methods, my machine hits out of memory (1GB) error before completing. I have no more physical memory.

如何才能做得更好?语言没有问题，发送到标准输出的结果也很好 - 在输出之前不需要将其全部保存在内存中.

How can this be done better? Language is no issue and results sent to the standard output is fine as well - it does not need to be held all in memory before outputting.

推荐答案

从 X = {A,B,C,D,E,F,G,H,I} 的幂集到0 到 2^|X| 之间的一组数字= 2^9:

There is a trivial bijective mapping from the power set of X = {A,B,C,D,E,F,G,H,I} to the set of numbers between 0 and 2^|X| = 2^9:

Ø 映射到 000000000(基数 2)

Ø maps to 000000000 (base 2)

{A} 映射到 100000000(基数 2)

{A} maps to 100000000 (base 2)

{B} 映射到 010000000(基数 2)

{B} maps to 010000000 (base 2)

{C} 映射到 001000000(基数 2)

{C} maps to 001000000 (base 2)

...

{I} 映射到 000000001(基数 2)

{I} maps to 000000001 (base 2)

{A,B} 映射到 110000000(基数 2)

{A,B} maps to 110000000 (base 2)

{A,C} 映射到 101000000(基数 2)

{A,C} maps to 101000000 (base 2)

...

{A,B,C,D,E,F,G,H,I} 映射到 111111111(基数 2)

{A,B,C,D,E,F,G,H,I} maps to 111111111 (base 2)

您可以使用此观察来创建这样的幂集(伪代码):

You can use this observation to create the power set like this (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
}

通过这种方式，您可以避免任何递归(并且，根据您需要 powerset 的用途，您甚至可以在不分配许多数据结构的情况下生成"powerset - 例如，如果您只需要打印电源组).

In this way you avoid any recursion (and, depending on what you need the powerset for, you may even be able to "generate" the powerset without allocating many data structures - for example, if you just need to print out the power set).

这篇关于内存高效的幂集算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！