计算幂集的算法

Question

我刚刚发现了一种找到幂集的算法。我在网上搜索了解决方案，但没有找到好的方法，所以我自己想出了一个。但我想知道它是什么算法，因为我在网上或书中找不到它。我的意思是，它有名字吗？与我在某些网站上找到的计算幂集的算法相比，我认为我的算法更好，想知道为什么没有人使用它？

以下是该算法：

R <- []
L <- [ e1, e2 ... en ]
c <- 0
function: powerSet(L, c)
  R <- R union L
  for e in L starting at c
    powerSet(L\{e}, c)
  end
  return R
end

以下是Java实现：

public static void powerSet(List<String> list, int count)
{
  result.add(list);

  for(int i = count; i < list.size(); i++)
  {
    List<String> temp = new ArrayList<String>(list);
    temp.remove(i);

    powerSet(temp, i);
  }
}

- rejeep

Answer 1

主要有两个原因：

1. 它使用了全局变量；
2. 它是递归的，尽管这并不重要，因为它是一个O(2^n)算法。

- João Silva

---

+1。它还为原始集合中的每个元素添加了空集。 - ChssPly76

我应该指出，我只将我的算法与其他O(2^n)算法进行比较。我知道它非常慢。我想出这个算法是因为我们在学校里有一个分配任务要创建一个暴力算法。但是要成为暴力算法，我认为我的算法非常好。我真的不明白它使用全局变量会成为问题的原因。在许多情况下，您实际上并没有将集合存储在结果中，而是对集合执行操作。ChssPly76，它只添加了一个空集，那就是空集。算法的结果是幂集，没有别的。 - rejeep

一个幂集包含2^n个元素，因此除非我错得离谱，否则算法至少必须是O(2^n)。@rejeep - phant0m

Answer 2

请看Rosetta Code Power Set页面。那里有几个递归解决方案的实现（包括Java）。然而，总的来说，递归解决方案意味着一个疯狂大的调用堆栈，这会使事情变慢。

- Richie Cotton

Answer 3

public final static Set<Set<Character>> powerSet(Set<Character> s){
    Set<Set<Character>> result = new HashSet<Set<Character>>();
    result.add(s);
    for (Character c:s){
        Set<Character> subSet = new HashSet<Character>(s);
        subSet.remove(c);
        result.addAll(powerSet(subSet));
    }
    return result;
}

- Michiel Rop

---

复活一段效率低下的代码线程 :-) 这是Omega(n!)，不是O(2^n)。 - Aryabhatta