問題タブ [powerset]

P(S)セットのべき集合を生成したいと思いSます。P(S)特定のサイズに等しいサブセットのみが必要です。

たとえば、があればS = [1,2,3,4]、limited_powerset(S,3)[[1,2,3],[2,3,4],[1,3,4],[1,2,4]].

Hynek Pichi Vychodilは、Erlangでの一般的なパワーセット生成の良い例を提供しました（ありがとう！）：

特定のサイズのサブセットのみを持つように変更するにはどうすればよいですか？Limit変数を導入し、最後の行を次のように変更します

助けにはなりません。

PSサブセットの数はN！未満になると思いますが、正確に計算するにはどうすればよいですか？

セットのべき集合を計算したい。一度にすべてのパワーセットを必要としないので、それを怠惰に生成する方が良いです。

例えば：

結果はシーケンスなので、上記の順序で優先します。F＃でどのようにイダマティックな方法でそれを行うことができますか？

編集：

これは私が使用するものです（BLUEPIXYの回答に基づく）：

素晴らしいご意見をありがとうございました。

かなり大きなセット（約30〜50要素）のパワーセットを生成したいのですが、パワー2^nセットを格納するのに時間がかかることを知っています。

一度に1つのサブセットを生成することは可能ですか？

つまり、反復を使用してセットのべき集合を生成し、生成された各サブセットをディスク/データベースに保存し、スタック/メモリから削除してから、他のサブセットの生成を続行しますか？

残念ながら、ErlangとRubyの例を自分のニーズに合わせて変更できませんでした。

注: これは、パワーセットに関する以前の質問の続編です。

スタックを保持する必要なしにセットのパワーセットを生成することについての以前の質問に対する素晴らしい Ruby ソリューションがあります。

それは仕事をし、うまく機能します。

しかし、同じソリューションを Erlang で書き直してみたいと思います。なぜなら、{|item| p item}ブロックの作業コードの大部分がすでに Erlang で書かれているからです (生成された各サブセットでいくつかのことを行います)。

私は Erlang の経験がありますが (2 冊の本すべてを読みました :))、例と、パワーセットに関する以前の質問に対してsepp2kが親切にくれたコメントにかなり混乱しています。例の最後の行がわかりません - 私が知っている唯一のことは、それがリスト内包表記であることです。生成された各サブセットで何かを実行できるように変更する方法がわかりません（その後、それを破棄して次のサブセットに進みます）。

この Ruby の反復的な powerset 生成を Erlang で書き直すにはどうすればよいですか? あるいは、提供されている Erlang の例は、すでにほとんどニーズに合っているのでしょうか?

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

( Hynek -Pichi- Vychodil )

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

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

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

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

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

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

Sいくつかのサブセットを含むSetがあるとします。

また、S には 6 つの固有の要素が含まれているとしましょう:a, b, c, d, eとf.

Sの一意の要素をそれぞれ 1 回だけ含むの可能なサブセットをすべて見つけるにはどうすればよいSでしょうか?

関数/メソッドの結果は次のようになります。

1. [[a,b,c], [d,e,f]];
2. [[a,b,c], [d,f], [e]];
3. [[a,b], [c], [d,e,f]];
4. [[a,b], [c], [d,f], [e]].

それを達成するためのベストプラクティスまたは標準的な方法はありますか?

疑似コード、Ruby、または Erlang の例に感謝します。

特定の方法でセットのパーティションを生成したいと思います。これらのパーティションを生成するプロセスで、サイズが N でないすべてのパーティションを除外する必要があります。一般的な解決策は、「セットのすべての「一意の」サブセットを生成する（パワーセットではない）」です。

S次のサブセットを含むセットの場合:

および次の「一意の」要素:

引数で実行された関数/メソッドの結果は次のN = 2ようになります。

次のパーティションは、関数/メソッドによって除外する必要があります。

基礎となるデータ構造は重要ではなく、配列、セットなどの可能性があります。

理由: すべてのパーティションを生成する関数/メソッドはかなり計算量が多いため、すべてのパーティションの完全なセットを取得する前に、いくつかのパーティションを除外する必要があります。

「セットのパーティションの生成」によると、可能なパーティションの数は非常に多くなる可能性があります: 23 要素の場合、44152005855084346 です。私のデータは開始セットで 50 ～ 300 要素なので、どこかに保存する前に、N と等しくないサイズのパーティションを確実に除外する必要があります。

たとえば、シーケンス [1,2,3] がある場合、サブシーケンスを生成するアルゴリズムは次のようになります。

だがしかし

または

次に、値を形成するデータベースでこれらの一意のサブセットを検索した結果とともに、これらをキーとして辞書に挿入したいと考えています。それを手伝っていただけないでしょうか？

どうもありがとう！

ナップサック問題のブルートフォース実装を作成する必要があります。擬似コードは次のとおりです。

アルゴリズムの実装はかなり簡単ですが、Sのべき集合を生成し、そのべき集合のサブセットをwhileループの各反復にフィードする方法については少しもわかりません。

私の現在の実装では、ペアのリストを使用してアイテムの重量と利益を保持しています。

そして、computeMaxProfit関数用にこのリストのべき集合を生成したいと思います。リストのサブセットを生成するためのアルゴリズムはありますか？リストは使用するのに適切なコンテナですか？

私は一連の数字を持っています：

後者の番号がペアの最初の番号と同じ場合にのみ、新しいペアを追加できるというルールで、それらから組み合わせを取得する必要があります。

たとえば、ペア {15,1} がある場合、次は {1,46} と次の {46,45} のみであり、最後のペアはセット全体の最初の数字で終わる必要があります。この場合、たとえば {45,1} になります。

したがって、4 セット制限のあるセットの最終結果は次のようになります。

基本的な累乗セットを実行して、一連の数値から可能なすべての組み合わせを生成できますが、これは私には高度すぎるようです。

私はC、Javascript、またはPHPを実行できるので、これに対するすべてのヘルプまたはソリューションは高く評価されています。明確にするために、これは宿題ではありません。これは、私が学び、理解したいことです。