在Erlang中生成没有堆栈的powerset

注意：这是我之前关于powersets的问题的续集。在Erlang中生成没有堆栈的powerset

我有一个很好的Ruby解决我以前question有关生成一组的幂，而不需要保持堆栈：

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本书:)），但我很困惑example以及sepp2k对我之前关于powersets的问题给予的评论。我不明白这个例子的最后一行 - 我知道的唯一的事情就是列表理解。我不明白我如何修改它以便能够对每个生成的子集执行某些操作（然后将其抛出并继续处理下一个子集）。

如何在Erlang中重写这个Ruby迭代powerset的生成？或者，也许提供的Erlang例子已经几乎适合需要？

来源

2011-12-24 skanatek

可能是疯狂的问题：你为什么要生成没有堆栈的家伙？ Erlang中可能最快的版本会保持与您正在设置的元素数量成正比的堆栈。请注意，在Erlang中，堆栈比其他语言的限制更少。它会自动增长，不能轻易耗尽。 – 2011-12-28 17:25:56

我想尝试生成一个相当大的集合 - 超过300个元素的powerset。但是我不需要所有的子集，所以我试图找到一个解决方案来一次生成一个子集，并根据特定标准对其进行过滤。 – skanatek 2012-01-03 18:53:11

所有给定的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.

在上面的代码中尾递归使用是由编译器二郎优化，在幕后转化为简单的迭代。只有当递归调用是函数执行流程中的最后一个调用时，才可以用这种方式优化递归。还要注意，每个生成的子集都可以用来代替评论，并且在那之后它将被遗忘（垃圾收集）。由于堆栈和堆栈都不会增长，但是你还必须对子集进行一个接一个的操作，因为没有最终的结果包含所有的子集。

我的代码对类似变量使用相同的名称，就像在例子中一样，以便比较它们。我相信它可以提高性能，但我只想展示这个想法。

来源

2011-12-29 07:34:03

在Erlang中生成没有堆栈的powerset

回答

相关问题