尝试计算 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).
更多推荐
内存高效的幂集算法
发布评论