問題タブ [powerset]

私はリストを言っlis1 = [1,2,3] て、上記のリストのサブセットのリストを言う

lis1 のすべてのアイテムが組み合わせに存在するように、lis2 のすべての組み合わせを生成したいと考えています。

たとえば。これは有効な組み合わせです

そのような組み合わせの 1 つは( ie[[1,2],[2,3]]のすべての項目がその中に存在する) です。lis1[1,2,3]

一方、これはそうではありません

私がしたことは、この関数を介してlis2のパワーセットを生成することでした

しかし、明らかなように、返されるセットには型の組み合わせが含まれています

lis1 のすべてのアイテムを含む組み合わせを確認するにはどうすればよいですか

したがって、次のような配列が与えられた場合

与えられた部分配列 (連続していないものを含む) は次のとおりであることがわかっています (これはべき集合を表します)。

また、これらのサブセットは、バイナリでカウントすることで表すことができることも知っています。

このメソッドを使用してすべてのサブセットを生成できることは知っていますが、これを c++ でどのように実装できるかはよくわかりません

したがって、基本的に私が求めているのは、バイナリカウントを使用してパワーセットを生成するにはどうすればよいかということです。

パワーセットを生成する他の方法も大歓迎です!

セットの実際の累乗セットを生成する方法に関する例はたくさんありますが、累乗セットを (図のようにstd::iterator) 反復的に生成する方法については何も見つかりません。このようなアルゴリズムを高く評価する理由は、基本セットのサイズです。n 要素セットの累乗セットには 2^n 要素があるため、実際にセットを計算するとすぐにメモリ不足になります。では、特定のセットのパワー セットのイテレータを作成する方法はありますか? それは可能ですか？

• より簡単であれば、ints のセットを作成するイテレータで問題ありません。それらを実際のセット/ベクトルのインデックスとして使用できます。
• 私は実際に作業しているので、必要に応じてstd::vectorランダムアクセスが可能です

ユーザーがテーブルに有効な組み合わせレコード (つまり、Powerset またはサブセット) を作成するトリガーを使用してテーブルに個々のアイテムを入力するという要件があります。私が抱えている課題は、レコードが親子関係を持つことができ、そのような状況では、2^n の値セットで有効にならないサブセットがあることです。

簡単な例を次に示します。

データ：

望ましい出力:

A
B
C
D
A、B
A、C
B、C
A、D
A、B、C
A、B、D
A、C、D
A、B、C、D

データに親子関係があることに気付く前に、次のコードを使用するつもりでした。

しかし、この共通テーブル式を使用すると、12 の有効な/必要な組み合わせだけでなく、15 の可能な組み合わせすべてを取得できます。

私は初心者の SQL プログラマーであり、1 週間以上解決策を見つけようとしてきましたが、まったく成功しませんでした。どんな助けでも大歓迎です（これが不可能な仕事だと私に言うことであっても）。うまくいけば、私は十分な情報を提供し、誰かが私を助けることができます.

私が次のものを持っているとしましょう：

または、グループを簡単に確認できるように、わずかに再フォーマットします。

次のグループ化を生成するための最も一般的または最も効率的なアルゴリズムは何ですか?

すぐにグーグルで調べたところ、上記のキーは「パワーセット」を表しているようです。だから私は次の実装を計画していました：

1) パワーセット {{j, b, m}, {j, m}, {j, b} {b, m}, {m}, {j}, {b}} を生成 // j = john, b = ボブ、m = メアリー

2) すべての文字のセットを生成: {a, b, c, d, e, f}

3) サブセットを反復し、各文字について、サブセットのすべての要素に文字が存在するかどうかを確認します

そう...

より良い解決策はありますか？

EDIT : 上記のアルゴリズムには欠陥があります。たとえば、{j, m} には "a" も含まれますが、これは望ましくありません。各反復で、この文字がこのセットにない要素に「含まれていない」かどうかも確認するように、単純に変更できると思います。したがって、この場合、次のことも確認します。