0

「パワーセットは単に0から2 ^ N-1の間の任意の数であり、Nはセットメンバーの数であり、バイナリ表現の1は対応するメンバーの存在を示します」ことを私は知っています。

( Hynek -Pichi- Vychodil )

バイナリ表現から実際のセット要素へのこのマッピングを使用して、パワーセットを生成したいと思います。

Erlangでこれを行うにはどうすればよいですか?

これを変更しようとしましたが、成功しませんでした。

UPD:私の目標は、スタックを保持せずにセットのパワーセットを生成する反復アルゴリズムを作成することです。私は、バイナリ表現がそれを助けることができると考える傾向があります。

これは Ruby で成功したソリューションですが、Erlang で記述する必要があります。

UPD2:これが疑似コードでの解決策です 。Erlang で同様のものを作成したいと思います。

4

1 に答える 1

3

まず第一に、Erlangの場合、再帰的ソリューションは必ずしも余分なスタックを消費することを意味するわけではないことに注意してください。メソッドが末尾再帰である場合（つまり、メソッドが最後に行うのは再帰呼び出しです）、コンパイラーはパラメーターを変更するようにメソッドを書き直し、その後メソッドの先頭にジャンプします。これは関数型言語ではかなり標準です。

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

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

数値を2進表現に分割する代わりに、2の累乗のリストを生成して、それを元に戻し、対応するビットが各M値（0から2 ^ N-1）に設定されているかどうかを確認することを検討してください。 -ビットマスク。次に、バイナリ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を実行する代わりにリストを末尾に配置しAcc ++ [generate_subset(...)]ます。この場合、カウントアップではなくカウントダウンしているので、すでに逆方向に進んでいるので、同じ順番で出てきます。

したがって、結論として、

  1. Erlangでのループは、末尾再帰関数を介して、またはのバリエーションを使用して、慣用的に行われlists:mapます。
  2. Erlangを含む多くの（ほとんど？）関数型言語では、末尾再帰はジャンプを使用して実装されているため、余分なスタックスペースを消費しません。
  3. リストの作成は通常[NewElement | ExistingList]、効率上の理由から逆方向（つまり）で行われます。
  4. リストは単一リンクであるため、通常、リスト内のN番目のアイテムを（を使用して）検索することは望ましくありませんlists:nth。リストを何度も繰り返す必要があります。代わりに、上記のビットマスクを前処理した方法など、リストを1回繰り返す方法を見つけてください。
于 2011-12-27T04:33:45.233 に答える