在Erlang中生成一个不使用栈的幂集

Question

注意：这是我之前关于幂集的问题的续集。

我找到了一个不需要保留堆栈的好的Ruby解决方案，用来生成一个集合的幂集。之前我在这个问题上提出过。

class Array
  def powerset
    return to_enum(:powerset) unless block_given?
    1.upto(self.size) do |n|
      self.combination(n).each{|i| yield i}
    end
  end
end
# demo
['a', 'b', 'c'].powerset{|item| p item} # items are generated one at a time
ps = [1, 2, 3, 4].powerset # no block, so you'll get an enumerator 
10.times.map{ ps.next } # 10.times without a block is also an enumerator

这个工具可以很好地完成任务。

但是，我想尝试使用Erlang重写相同的解决方案，因为对于{|item| p item}块，我已经编写了大量可以在Erlang中运行的代码（它对每个生成的子集执行一些操作）。

虽然我有一些使用Erlang的经验（我已经阅读了所有2本书：），但我对示例和sepp2k针对我的上一个幂集问题提供的评论感到非常困惑。我不理解示例的最后一行 - 我唯一知道的就是它是列表推导式。我不明白如何修改它才能够对每个生成的子集进行一些操作（然后将其丢弃并继续下一个子集）。

我该如何在Erlang中重写这个Ruby迭代幂集生成器？或者提供的Erlang示例已经几乎符合要求了吗？

- skanatek

---

可能有点疯狂的问题：为什么要在没有堆栈的情况下生成这个人？在 Erlang 中，最快的版本可能需要保留与幂集元素数量成比例的堆栈。请注意，在 Erlang 中，堆栈的限制比其他语言要少。它会自动增长，不容易耗尽。 - I GIVE CRAP ANSWERS

我想尝试生成一个非常大的幂集——超过300个元素。但我不需要所有的子集，因此我尝试找到一种解决方案，一次只生成一个子集，并根据特定的条件进行筛选。 - skanatek

Answer 1

所有给定的示例都具有O(2^N)的内存复杂度，因为它们返回整个结果（第一个示例）。最后两个示例使用常规递归，因此堆栈会增加。下面的代码是对这些示例进行修改和编译后得到的，可以实现您想要的功能：

subsets(Lst) ->
    N = length(Lst),
    Max = trunc(math:pow(2, N)),
    subsets(Lst, 0, N, Max).

subsets(Lst, I, N, Max) when I < Max ->
    _Subset = [lists:nth(Pos+1, Lst) || Pos <- lists:seq(0, N-1), I band (1 bsl Pos) =/= 0],
    % perform some actions on particular subset
    subsets(Lst, I+1, N, Max);
subsets(_, _, _, _) ->
    done.

在上面的代码片段中，使用了尾递归，这是由Erlang编译器进行优化并在内部转换为简单迭代。只有在递归调用是函数执行流程中的最后一个调用时，才能以这种方式优化递归。还要注意的是，每个生成的子集都可以用作注释的替代，并且在此之后将被遗忘（垃圾回收）。由于这样既不会增加堆栈也不会增加堆，但您还必须依次对子集执行操作，因为没有包含所有子集的最终结果。

我的代码使用类似变量的同名变量，就像示例中一样，以便更容易地比较它们。我相信它可以通过优化来提高性能，但我只想展示这个想法。

- Wacław Borowiec