在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

回答

相關問題