バイナリ表現の助けを借りてpowersetを生成する

Question

"powersetは0と2^N-1の間の任意の数で、Nは設定されたメンバの数で、バイナリ表現では1つは対応するメンバの存在を示す"ということを知っています。

（Hynek -Pichi- Vychodil）

Iは、実際のセットの要素にバイナリ表現から、このマッピングを使用して、冪を生成したいです。

Erlangでどうすればいいですか？

thisを修正しようとしましたが、成功しませんでした。

UPD：私の目標は、スタックを維持せずにセットのパワーセットを生成する反復アルゴリズムを書くことです。私はバイナリ表現がそれに役立つと思う傾向があります。

HereはRubyの成功した解決策ですが、私はErlangに書き込む必要があります。

UPD2：Hereは疑似コードの解決法ですが、私はErlangで同様のことをしたいと思います。

Answer 1

まず、Erlangの再帰的解法は必ずしも余分なスタックを消費することを意味するわけではありません。メソッドが末尾再帰的である（すなわち、再帰呼び出しが最後のものである）場合、コンパイラはパラメータを修正してメソッドの先頭にジャンプする。これは関数型言語のためのかなり標準的です。

すべての数字AからBのリストを生成するには、ライブラリメソッドlists:seq(A, B)を使用します。

値リスト（0から2^N-1までのリストなど）を別の値リスト（バイナリ表現から生成されたセットなど）に変換するには、lists:mapまたはlist comprehensionを使用します。

数値をバイナリ表現に分割するのではなく、それを回して、対応するビットが各M値（0〜2^N-1）に設定されているかどうかを確認することをお勧めします-of-2-bitmasks。次に、ビットが設定されているかどうかをバイナリANDで確認できます。しかし、あなたはまた、スタック領域を消費することなく末尾再帰を使用して同じことを達成することができます

generate_powerset(List) -> 
    % Do some pre-processing of the list to help with checks later. 
    % This involves modifying the list to combine the element with 
    % the bitmask it will need later on, such as: 
    % [a, b, c, d, e] ==> [{1,a}, {2,b}, {4,c}, {8,d}, {16,e}] 
    PowersOf2 = [1 bsl (X-1) || X <- lists:seq(1, length(List))], 
    ListWithMasks = lists:zip(PowersOf2, List), 

    % Generate the list from 0 to 1^N - 1 
    AllMs = lists:seq(0, (1 bsl length(List)) - 1), 

    % For each value, generate the corresponding subset 
    lists:map(fun (M) -> generate_subset(M, ListWithMasks) end, AllMs). 
    % or, using a list comprehension: 
    % [generate_subset(M, ListWithMasks) || M <- AllMs]. 

generate_subset(M, ListWithMasks) -> 
    % List comprehension: choose each element where the Mask value has 
    % the corresponding bit set in M. 
    [Element || {Mask, Element} <- ListWithMasks, M band Mask =/= 0]. 

：一緒にそのすべてを置く

は、次のような解決策を得ます。また、0〜2^N-1のリストを生成したり、保持したりする必要はありません。

generate_powerset(List) -> 
    % same preliminary steps as above... 
    PowersOf2 = [1 bsl (X-1) || X <- lists:seq(1, length(List))], 
    ListWithMasks = lists:zip(PowersOf2, List), 
    % call tail-recursive helper method -- it can have the same name 
    % as long as it has different arity. 
    generate_powerset(ListWithMasks, (1 bsl length(List)) - 1, []). 

generate_powerset(_ListWithMasks, -1, Acc) -> Acc; 
generate_powerset(ListWithMasks, M, Acc) -> 
    generate_powerset(ListWithMasks, M-1, 
         [generate_subset(M, ListWithMasks) | Acc]). 

% same as above... 
generate_subset(M, ListWithMasks) -> 
    [Element || {Mask, Element} <- ListWithMasks, M band Mask =/= 0]. 

サブセットのリストを生成するときは、リストの先頭に新しい要素を追加することになります。リストは単独でリンクされ、不変なので、最初からどこにでも要素を配置したい場合は、リストをコピーする "次の"ポインタを更新する必要があります。そのため、ヘルパー関数はAcC++ [generate_subset(...)]の代わりにAccリストを末尾に置きます。この場合、アップの代わりにカウントダウンしているので、すでに逆順になっているので、同じ順序で出てきます。

だから、結論では、Erlangでループ

1. は慣用的に末尾再帰関数を介して行わまたはlists:mapのバリエーションを使用しています。
2. Erlangを含む多くの（ほとんどの）関数言語では、末尾再帰はジャンプを使用して実装されているため余分なスタック領域を消費しません。
3. リスト構築は、効率の理由から、通常、後方に行われる（すなわち、[NewElement | ExistingList]）。
4. リスト内のN番目のアイテム（lists:nthを使用）を検索したくないのは、リストが1つにリンクされているためです。リストを何度も繰り返して繰り返す必要があります。代わりに、上記のビットマスクをどのように前処理したかなど、リストを一度反復する方法を見つけてください。