3

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

我有一个很好的 Ruby 解决方案来解决我之前关于在不需要保留堆栈的情况下生成集合的 powerset 的问题：

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对我之前关于 powersets 的问题的示例和评论感到非常困惑。我不明白示例的最后一行 - 我唯一知道的是列表理解。我不明白如何修改它以便能够对每个生成的子集执行某些操作（然后将其丢弃并继续下一个子集）。

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

4

1 回答 1

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 编译器优化并在幕后转换为简单的迭代。仅当递归调用是函数执行流程中的最后一个调用时，才能以这种方式优化递归。还要注意，每个生成的子集都可以用来代替评论，之后就会被遗忘（垃圾收集）。由于堆栈和堆都不会增长，但是您还必须一个接一个地对子集执行操作，因为没有包含所有子集的最终结果。

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

于 2011-12-29T07:34:03.450 回答