私はちょうど別のアルゴリズムを試しています。私はこの問題を遭遇しました。そのために、与えられたセットのすべてのサブセットを生成する必要があります。私はビットマスキングを使用してこれを行う方法を知っています。しかし、セットが非常に大きい、すなわちO（2^n）のときには時間がかかりすぎる。私はO（n^2）でこれを解決できる他の時間効率的なアルゴリズムがあるかどうか疑問に思っていましたか？これで私を助けてください。O（n^2）時間に与えられた集合のすべての部分集合を生成するアルゴリズムはありますか？
たとえば、すべての部分集合を印刷したり、どこに明示的に格納したりする場合は、そのようなアルゴリズムはありません。 n要素のセットの2^nサブセットがあり、単純に列挙するにはexponential timeが必要です。
ありがとうございます。それは私の疑いを明らかにした。 – ashwani
n要素集合のすべての部分集合を生成するための多項式時間の方法は明らかにありませんが、いくつかの方法が他の方法より効率的です。特に、Gray codeを使用する場合は、連続するサブセットから1つの要素を追加または削除することで、1つのサブセットから別のサブセットに移動できます。これは例えばブルートフォースナップザックソリューションは、（例えば、約30またはそれ以下のnに対して）はるかに効率的である。
グレイコードの方法を教えてください。 – ashwani
@userこれは多少関わっていますが、私がリンクしているWikipediaの記事では、それらを生成するアルゴリズムについて説明しています。多くの目的で、グレイコードはベース2の方法で0から2^n-1までの純粋な数よりも優れていますが、フリーランチはなく、1つのサブセットから次のサブセットに行くのは簡単なアルゴリズムではありません。グレイコードを使用すると、余分なプログラミング作業をする価値がある場合、サブセットを使って何をしたいかによって、実際には異なります。 –
あなたはn^2ステップで2^nものを生成する方法はありますか？多分魔法で。 –
本当の質問は、あなたが2^nセットでしたいことです。実際に出力する必要がある場合は、明らかに2^n時間未満を費やすことはできません。しかし、それらのいくつかの集約を計算したい場合、つまり特定のプロパティを最大化/最小化するサブセットを見つける場合は、 –
@ NiklasBが可能です。さて、ライブコンテストからの私は、不正行為をしたくないので、私は全体の問題を伝えることはできません。 Btw、あなたの説明に感謝します。 – ashwani