問題タブ [powerset]

与えられたセット

サブセットを作成するにはどうすればよいですか？

のべき集合{1, 2, 3}は次のとおりです。

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

Set私がJavaを持っているとしましょう：

可能な限り複雑な順序で関数getPowersetを作成するにはどうすればよいですか？（O（2 ^ n）かもしれないと思います。）

これは、言語にとらわれない/役立つ回答である可能性があり、疑似コードである可能性があります。

さまざまな入力でテストしたいプログラムがあります。このプログラムは一連のファイルを受け取り、そのうちの 1 つがルートとして指定されます。考えられるすべてのファイルのサブセットでプログラムを実行したいと考えています。(同じファイルを含むがルートが異なる 2 つのサブセットは、異なるものと見なされます。)

これは同じ例です。ファイル A、B、C があるとします。次のようにテストしたいと思います。

等々。これがパワーセットになると思います。

ファイルでいっぱいのディレクトリを指定して、Java でこのセットを生成する最良の方法は何ですか?

next_permutation のような一連の値の次の組み合わせを提供する同等のライブラリまたは関数はありますか?

数字の最初のリストに基づいて、数字の組み合わせの一意のリストを効率的に生成したいと思います。

例は開始list = [1,2,3,4,5]しますが、アルゴリズムは次のように機能するはずです[1,2,3...n]

ノート。重複した組み合わせは必要ありませんが、一緒に暮らすことはできます。たとえば、上記の例では、[1,2,3]として既に存在するため、組み合わせ[1,3,2]は実際には必要ありません。

可能な重複:数字または単語を取り、可能なすべての組み合わせを見つける
文字列アルゴリズムの可能な組み合わせを表示します

次のような 3 つの文字列がある場合:

そして、これらの文字列を並べ替えることで生成できる組み合わせの最大数を見つけたいと思います。

• abc xyz デフ
• def xyz abc
• xyz abc def

これを計算するための式/アルゴリズムは何ですか?

私が現在取り組んでいる問題については、与えられたセットのべき集合から適度に均一なランダムな選択をしたいと思います。残念ながら、これは私がまったく研究していない統計（実際のプログラミングに取り掛かっている今、修正する必要があるもの）にぶつかるので、それを知っている何人かの人々を超えてソリューションを実行したかったのです。

与えられたセットのサイズがnの場合、サイズkの（nk）= n！/ [k！（nk）！]サブセットがあり、べき集合の合計サイズNは、からのkに対する（nk）の合計として与えられます。 0からn。^{（2 n}としても与えられますが、ここでは役に立たないと思います。明らかに間違っていた可能性があります）。

したがって、私の計画は、[0、1]を間隔に分割することです。

アルゴリズム的には、間隔は、前の間隔の最大要素を新しい間隔の最大下限として取得し、それに（nj）/ Nを追加して、最大要素を取得することによって構築されます。それがはっきりしていることを願っています。

次に、[0、1]で均一なフロートを選択し、それが属する区間のインデックスにマッピングすることで、ランダムサブセットに含まれる要素の数を把握できます。そこから、適切なサイズのランダムなサブセットを選択できます。

1. 私のスキームは、サブセットのサイズ（サブセットの総数に対して均一です。セット{1、2、..、）では明らかに均一ではありません。サイズのn}）。

2. 私はライブラリ（python random.sample）を使用して、指定されたサイズのサブセットを取得しているので、それが均一になると確信しています。

だから私の質問は、私が説明している方法で2つを組み合わせると、ランダムサイズのランダムサブセットの選択が均一になるかどうかです。答えが大変な作業である場合、これがどのように証明されるかについての指針を受け入れ、自分で作業を行うことができてうれしいです。また、これを行うためのより良い方法があれば、もちろん私はそれに満足しています。

次のセットが与えられます：

セットを定義します：

組合のためのu

結果として得られるべき集合演算のセットは次のとおりです。

空のセットの場合は0

私の質問は、unio操作に関するものです。0とYを結合するにはどうすればよいですか？

実際には、確率のあるオブジェクトのセットがあり、それらが独立していると仮定して、それらがすべて真である可能性が高い順に、つまり、次の降順で、それらの可能な各グループを調べたいと思います。サブセットの要素の積-または確率が同じ場合は長さの順に（（1、0.5）が（0.5）の後に来るように）。

例：[ 1, 0.5, 0.1 ]必要な場合[ (), (1), (0.5), (1, 0.5), (0.1), (1, 0.1), (0.5, 0.1), (1, 0.5, 0.1) ]

本質的に、これは、要素のセットのべき集合を順番に反復したいことを意味し、これをかなり簡単に生成し、並べ替えて、実行することができます。ただし、べき集合はかなり速く大きくなります。通常、最初のサブセットの1つが必要になると思います。何千ものサブセットのリストを生成して並べ替えてから、3番目のサブセットを超えないようにします。これは、Pythonジェネレーターが1日を節約できる場所です。

問題のより正式な仕様sorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True)として、ジェネレーターとして、またはリスト全体の作成と並べ替えを回避できるその他の方法を検討する必要があります。

これは、サブセット製品の問題とともに、ナップサック問題に関連していると合理的に確信していますが、機能する優れたアルゴリズムを取得するのに本当に苦労しています。助けていただければ幸いです:-)。最悪の場合（最後まで繰り返す）で全体を構築+並べ替えるよりも遅くなることは問題ではありません。必要なのは、はるかに優れた最良の場合（たとえば、最初の10％以内）のパフォーマンスだけです。

0 から 2^n までのすべてのビットを使用して、セットのパワーセットを計算するアルゴリズムがあります。

私の質問は: このアルゴリズムの実行時間は? ループは 2^n 回実行され、各反復で while ループは lg(i) 回実行されます。だから私は実行時間は

T(n) = the sum from i=0 to i=2^n of lg(i)

しかし、これをさらに単純化する方法がわかりません。これは O(2^n) 時間 (空間ではない) で再帰的に解決できることを知っているので、上記の方法がこれよりも良いか悪いか、時間的に宇宙の方がいいです。