erlang - 在 Erlang 中生成没有堆栈的幂集

Question

注意:这是我之前有关幂集的问题的续集。

我对之前的 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} block 我已经用 Erlang 编写了很大一部分工作代码(它对每个生成的子集做了一些事情)。

虽然我对 Erlang 有一些经验(我已经阅读了所有 2 本书:))，但我对 example 感到非常困惑以及评论 sepp2k请回答我之前关于幂集的问题。我不理解示例的最后一行 - 我唯一知道的是这是一个列表理解。我不明白如何修改它以便能够对每个生成的子集执行某些操作(然后将其扔掉并继续处理下一个子集)。

如何在 Erlang 中重写这个 Ruby 迭代幂集生成？或者也许提供的 Erlang 示例已经几乎满足需要了？

Answer 1

所有给定的examples具有 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 编译器优化并在幕后转换为简单迭代。仅当递归调用是函数执行流程中的最后一个调用时，才可以通过这种方式优化递归。另请注意，每个生成的子集都可以用来代替注释，并且此后它将被遗忘(垃圾收集)。由于堆栈和堆都不会增长，但您还必须对子集一个又一个地执行操作，因为没有包含所有子集的最终结果。

我的代码对类似变量使用相同的名称，如示例中所示，以便更轻松地比较它们。我确信它可以针对性能进行改进，但我只想展示这个想法。