問題タブ [powerset]

n 個の要素のセットが与えられた場合{1,2,3,4,5...n}、長さ k のすべてのサブセットを見つける必要があります。

たとえば、n = 4 で k = 2 の場合、outputは になります{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}。

どうやって始めればいいのかさえわからない。next_permutation などの組み込みライブラリ関数を使用する必要はありません。

C/C++ または Java でのアルゴリズムと実装が必要です。

文字列のパワーセットを出力する Python コードを作成しようとしていますが、いくつかのバグが発生しています。これが私が持っているものです：

私の予想される出力は次のようになります。

私の実際の出力は次のとおりです。

何が起こっているのかを理解するのを手伝ってくれる人はいますか? これは Python のニュアンスですか、それとも私のコードにバグがありますか? 私のコードは問題ないと思います -- Cracking thecoding インタビューの第 5 版を終了します

ありがとうございました！

MySQL には製品テーブルがあり、各行にはコンマで区切られたオプションの値を持つフィールドがあり、組み合わせてこの製品になります。以下のスキームでは、両方のテーブルを見ることができます。カンマ区切りの値を持つフィールドは option_ids です。これは、たとえば 2,5,6,23 または 4,2,76 のようになります。これらの番号は、オプション テーブルに存在するオプションです。

製品：
|product_id|name|description|option_ids|price|

オプション：
|option_id|type_id|label|group|pos|count|price|

取得する入力は、一意のオプションの配列です。このオプションのセットまたはそのサブセットを持つすべての製品を option_ids で見つけたいと考えています。

これを行う方法は、オプションの配列のすべての可能な組み合わせを得るために、オプションの配列のべき集合を生成することです。次に、「OR WHERE」ステートメントでこれらすべての組み合わせを照会する mysql クエリを生成します。

ここでの問題は、累乗が指数関数的に増加することです。そのため、16 個の一意のオプションの配列がある場合、累乗は 65536 の可能性の配列を提供します。これを適切に機能させるには、php のメモリ使用量を増やす必要がありましたが、クエリが非常に膨大になるため、MySQL の問題が発生しました。

この問題に取り組む別の方法はありますか?

十分な情報を提供したことを願っています。そうでない場合は、質問してください。

編集: サブセットを見つける必要があるため、3 番目のテーブルでも同じ問題が発生します... オプションの配列が 1 つの製品であるとは言いません。1 つの製品である場合もありますが、2 つまたは 3 つの製品である場合もあります。例: オプション 1,2 は製品 A を作成し、オプション 2,3 は製品 B を作成し、オプション 4,5,6 は製品 C を作成します。オプション配列 [1,2,4,5,6] がある場合、製品 A と C を見つけます。

パワーセットをファイルに書き込もうとしていますが、開始配列がサイズ 6 よりも大きいとヒープが破損し、その理由がわかりません。配列 6 以下の任意のサイズで問題なく動作します。これを理解することはできません。

また、test.txt は、配列を読み取った場所です。ファイルに「1,2,3,4,5,6」が含まれている場合は正常に動作しますが、「1,2,3,4,5,6,7」が含まれている場合、ヒープが破損します。

ここで問題が発生し、オブジェクトの可能なすべての組み合わせを生成し、後で分析するためにそれらをリストに保存する必要があります。

インターネットでの検索には、組み合わせを保存するというこの要件を満たしていない多くのアルゴリズムが含まれています。最も一般的な検索では、組み合わせのリストを印刷するだけで生成されますが、他の検索では、オブジェクトではなく文字列のみを処理します。

一部のアルゴリズムはビットを使用してさまざまな組み合わせを表しますが、このソリューションは最大32個のオブジェクトに制限されているため、十分ではありません。

全体として、可能なすべての組み合わせ（べき集合）を生成し、オブジェクト（32以上）を処理し、組み合わせを印刷するだけでなく、これらの組み合わせをリストに格納できるアルゴリズムを探しています。アレイ。

パワーセットでセットを見つけようとしていますn-th。つまり、べき集合は次の順序で生成されます。n-th最初はサイズで、次に辞書式順序で生成されます。したがって、のべき集合の集合のインデックスは次のようになります[a, b, c]。

解決策を探しているときに見つけたのは、要素のリストのn番目の順列を返すアルゴリズムだけでした。たとえば、ここにあります。

コンテキスト：

要素のベクトルのべき集合全体を取得しようとしていますVが、一度に1つのセットでこれを行う必要があります。

要件：

• 同時に維持できるのは2つのベクトルのみです。最初のベクトルはリスト内の元のアイテムを含み、2番目のベクトルn-thはのべき集合からのセットVを持ちます。そのため、n-th setここで関数を使用します。
• これは、ソリューションの空間で線形時間ではなく実行する必要があります。つまり、すべてのセットをリストすることはできず、 n-th1つを選択します。
• 私の最初のアイデアは、ビットを使用して位置を表し、必要なものの有効なマッピングを取得することです。これは、投稿した「不完全な」ソリューションです。

Java プログラミングの課題について助けを求めています。リンクされたリストを使用して、そのパワー セットを出力する必要があります。たとえば、セット {1,2,3} は {{},{1}{1,2}{1,3}{1,2,3}{2}{2,3}{3} を出力する必要があります}。ベキ集合の要素数は 2^n です。これは、HeadNode.PrintPowerSet(); を呼び出して行う必要があります。
ここで、HeadNode はリンク リストの最初の要素です。私はいくつかのことを試しましたが、何もうまくいきません。それを行う最善の方法は、最後のセンチネルに到達するまでメソッドを再帰的に呼び出してから、残っている要素を追加して逆方向に作業することだと思います。申し訳ありませんが、これ以上コードやアイデアを投稿することはできません。前もって感謝します。

編集: これは非動作コードです。セット {{1,2,3}{2,3}{3}} を返します

EMPTY_SET はエンド センチネルです。手書きで書いてみました。助かりますが、まだ手に入りません。また、このクラス RSet は、本質的に単なるリンク リスト ノードです。

セットのパワーセットを生成しようとしていて、このコードを書きました。問題は、ユーザーがセットの 2 つの類似したメンバーを入力すると、正しく機能しないことです。私に何ができる？これが私のコードです：

すべてはタイトルにあります.. =）

3 (最小一定の長さ) から最大の長さのサブセットのみを使用して、パワーセットをすばやく作成したいと考えています。この最大値はほとんどの場合 5 ですが、可変 (3 から 5.6 まで) にしたいです。元のセットは大きい場合があります。さらに処理するために、これらのサブセットを保存する必要があります。

Java でセットのパワーセットを取得するのを見てきましたが、ここではパワーセットのすべてのサブセットを生成します。C#の最小長のサブセットに対する効率的なpowersetアルゴリズムも見ましたが、Adam Sが言ったように、実行時間のパフォーマンスとメモリの問題が発生すると思います。

これらのアイデアを組み合わせて、私の目標の理想的なアイデアにしたいと思います。私の最後の希望は、すべてのサブセットを高速に生成し（おそらくGuavaのアルゴリズムを使用して）、反復して目的の長さだけを取得することです...しかし、それを読むことさえ醜いです;）

誰でもアイデアを持っていますか？

私が作成した小さなアプリケーションを使用すると、ユーザーは2つの配列にさまざまなアイテムを追加できます。一部のロジックは、各配列の内容から数値を計算します。

配列x内のすべてのアイテムは、配列yに配置したり、元に戻したりすることができます。配列yに属するアイテムは、移動できません（配列xから移動された場合を除く）。

ユーザーは、単純なjavascript uiを使用して、これらのアイテムを2つのリストで移動できます。物事を簡単にするために、私はもともと素朴なスクリプトを作成しました。

1. アイテムをaからyに移動しました。
2. この「可能性」を使用していくつかのロジックを実行しました
3. 結果が以前よりも小さかった場合は、xをyのままにします。
4. そうでない場合、xはxに残ります。
5. xの次の項目に移動して、繰り返します。

私はこれが効果がないことを知っていました。私は読み回して、可能性または「順列」を覚えるためにビット単位の数学を使用してこれを行うように言われましたが、この段階でこの特定の問題を回避するのに苦労しています。

誰かが説明できれば（擬似コードは問題ありません）、次のことを達成するための最良の方法は何でしょうか。私は非常に感謝しています。

配列x=[100,200,300,400,500]配列y=[50,150,350,900]

これらの2つの配列を使用して、xの値ごとに、その値と他のすべての値のすべての組み合わせをxから配列yにプッシュします。それぞれについて、いくつかのロジックを実行します（つまり、テスト結果とこの「順列」を配列（xとyを表す2つの配列のオブジェクト）に格納します）。これは、大きな配列では非常に高価であり、多くのことを繰り返す可能性が高いと予測しています。組み合わせ。私はほとんどそこにいるように感じますが、この最後の段階で失われました。

長い説明でごめんなさい、そして事前に感謝します！