問題タブ [powerset]

リストのパワーセットを取得するために、次を実装しました。

これは、再帰を使用してリストの累乗を取得する最適な方法ですか? これをインターネット上で実装する方法については、さまざまな方法を見てきましたが、私のものよりも多くのコピー (new の使用) を行っているようです。

たとえば、このStackOverlow の投稿は私の Google 検索で出てきましたが、彼の実装 (Joao Silva) は多くのコピーを使用しており、最適ではないようです。しかし、私は彼の実装をかなり頻繁に見ていて、私を困惑させています。その実装は、私が使用しているものよりも優れていますか (もちろん、彼がジェネリックを使用しているという事実以外)?

彼のコード:

S(w) を単語の集合とする。これらのサブセットの和集合が常に S(w) に等しくなるように、サブセット s の可能な n 個の組み合わせをすべて生成したいと考えています。

したがって、セット（a、b、c、d、e）があり、3つの組み合わせすべてが必要なわけではありません：

((a, b, c), (d), (e))

((a, b), (c, d), (e))

((a)、(b、c、d)、(e))

((a)、(b、c)、(d、e))

など...

組み合わせごとに 3 つのセットがあり、それらのセットの結合がオリジナルのセットです。空のセットも欠落した要素もありません。

itertools.combination + collection.Counter を使用してそれを行う方法があるはずですが、どこかから始めることさえできません...誰か助けてくれますか?

ルーク

編集:次のようなすべての可能な組み合わせをキャプチャする必要があります。

((a, e), (b, d) (c))

など...

これに対する答えがどこにも見つからなかったので、ここに私の解決策があります。

問題は、R の累乗をどのように計算できるかということです。

これは、ライブラリ「sets」のコマンドを使用して実行できます。2^as.set(c(1,2,3,4))これにより、出力が得られます{{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}。ただし、これはかなり遅い再帰アルゴリズムを使用します。

これが私が思いついたアルゴリズムです。

これは非再帰的であるため、他のいくつかのソリューションよりもはるかに高速です (私のマシンでは、「sets」パッケージのアルゴリズムよりも約 100 倍高速です)。速度はまだ O(2^n) です。

このアルゴリズムの概念的な基礎は次のとおりです。

Rコードは次のとおりです。

編集:これは、同じ概念のやや高速なバージョンです。私のオリジナルのアルゴリズムは、この投稿への 3 番目のコメントにあります。これは、私のマシンでは長さ 19 のセットで 30% 高速です。

このバージョンでは、最初に最終的な長さでベクトルを開始し、新しいサブセットを保存する位置の「カウンター」変数を追跡することで時間を節約します。分析的に位置を計算することも可能ですが、それは少し遅くなりました。

ジェネレーターを使用して、Python で特定のセットのサブセットのリストを作成しようとしています。私が持っていると言う

set([1, 2, 3])

入力として、私は持っているべきです

[set([1, 2, 3]), set([2, 3]), set([1, 3]), set([3]), set([1, 2]), set([2]), set([1]), set([])]

出力として。どうすればこれを達成できますか？

プログラムに実行させたいことを正確に実行するコードを以下に示します。唯一の問題は、メソッドを再帰的にするためにどこから始めればよいかさえわからないことです。階乗やその他の問題に再帰を使用することは理解していますが、これは少し頭を悩ませています。誰かが私を正しい方向に向けるのを手伝ってくれますか?

セットのパワーセットを再帰的に見つけて、結果を出力しようとしていますが、非常に困っています。