内存高效发电机组的算法 [英] 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}到X |为0至2 ^的组数字| = 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}映射到0.1亿（基数为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}映射到1.1亿（基数为2）

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

{A，C}映射到1.01亿（基数为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)

您可以使用此观测创建电源设置这样的（伪code）：

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
}

在这样就避免了任何递归（并且，根据你所需要的幂的，你甚至能够产生的幂不分配许多数据结构 - 例如，如果你只需要打印出来的发电机组）。

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屋！