問題タブ [cartesian-product]

数字の2つのグループがあるとしましょう：

次の 6 つの組み合わせを出力するアルゴリズムを (Java で) 作成したいと思います。

任意の数のグループと、各グループ内の任意の数のメンバーが存在できます。上記の例では、2 つのグループがあり、最初のグループには 3 人のメンバーがいて、2 番目のグループには 2 人のメンバーがいます。別の例は次のとおりです (3 つのグループ、最初のグループに 3 人のメンバー、2 番目と 3 番目のグループに 2 人のメンバー):

これにより、次の 12 の組み合わせが生成されます。

Javaでこれを行うにはどうすればよいですか? 再帰を使用しようとしていますが、すでに同様の質問を見てきましたが、まだ不足しています。助けてくれてありがとう！（PSこれは宿題のためではありません）

デカルト積を計算するためのより良い方法はありますか？デカルト積は特殊なケースであるため、ケースごとに異なります。何を達成する必要があるのか​​、なぜデカルト積を実行するのかを説明する必要があると思います。デカルト積が私の問題の唯一の解決策である場合は、私を助けてください。もしそうなら、どのようにパフォーマンスを向上させるのですか？

バックグラウンド：

私たちは、お客様がより安く製品を購入できるように支援しようとしています。

顧客が5つの製品（prod1、prod2、prod3、prod4、prod5）を注文したとします。

注文した各製品は、さまざまなベンダーから提供されています。

表現形式1：

• ベンダー1-prod1、prod2、prod4を提供します
• ベンダー2-prod1、prod5を提供します
• ベンダー3-prod1、prod2、prod5を提供
• ベンダー4-prod1を提供
• ベンダー5-prod2を提供
• ベンダー6-prod3、prod4を提供

言い換えると

表現形式2：

• 製品1-vendor1、vendor2、vendor3、vendor4によって提供されます
• 製品2-vendor5、vendor3、vendor1によって提供されます
• prod3-vendor6が提供
• 製品4-vendor1、vendor6によって提供されます
• 製品5-vendor3、vendor2によって提供されます

次に、価格に基づいて最適なベンダーを選択します。価格で商品を並べ替えて、最初の商品を購入することができます。

その場合、

• ベンダー1の製品1
• ベンダー5の製品2
• ベンダー6の製品3
• ベンダー1の製品4
• ベンダー3の製品5

複雑：

4つのユニークなベンダーを選んだので、4つの送料を支払う必要があります。

また、各ベンダーには最小の発注書があります。それを満たさない場合は、その料金も支払うことになります。

製品の最適な組み合わせを選択するには、提供された製品のデカルト積を使用して合計価格を計算する必要があります。

私たちの場合には

• {vendor1、vendor2、vendor3、vendor4}
• {vendor1、vendor3、vendor5}
• {vendor6}
• {vendor1、vendor6}
• {vendor2、vendor3}

4 * 3 * 1 * 2 * 2 = 48の組み合わせを計算して、最適な組み合わせを見つける必要があります。

• {vendor1、vendor1、vendor6、vendor1、vendor2} = totalprice1
• {vendor1、vendor3、vendor6、vendor1、vendor2} = totalprice2、
• *
• {vendor4、vendor5、vendor6、vendor6、vendor3} = totalprice48

次に、計算された合計価格を並べ替えて、最適な組み合わせを見つけます。

実際の問題：

顧客が15を超える製品を注文し、各製品が8つの固有のベンダーによって提供されていると仮定すると、8 ^ 15 = 35184372088832の組み合わせを計算することになり、数時間以上かかります。顧客が20を超える製品を注文した場合、数日以上かかります。

この問題に別の角度で取り組むための解決策はありますか？

Cで静的な配列数のデカルト積を実現できますが、入力配列の数を動的に取得するコードを作成したいと思います。誰かがこれを「配列のみを使用して」行う方法を教えてもらえますか。それが不可能な場合配列を使用する場合は、他の解決策を提案してください。ありがとうございます。3つの配列のデカルト積のコードを以下に示します。

アイテムを含むn個のinputListがあります。次に、元のinputLists内のアイテムのすべての組み合わせを含むresultLists（長さn）を計算します（各inputListの1つのアイテムを取得します）。

ここに例を示す必要があると思います（n = 3）：

私はちょっとばかげていると感じていますが、任意のnと任意のinputListの長さに対してこれらの結果を作成する関数（C ++）を実装する方法がわかりません。ある種の再帰を使うべきだと思いますが、その方法がわかりません。
何か案は？

文字列など、いくつかのアイテムのリストのリストを提供しているとしましょう。

（実際のユースケースは文字列などとは関係ありません。これは単なるモックアップです）

私はそれを行うための再帰的なメソッドを作成しましたが、それが投げられる一時的なセットをたくさん作成するので、私はそれに満足していません（ええ、オブジェクトの作成はJavaで安価であり、通常はCのmallocよりもCPU命令が少ないことを知っています（ソース：Java Concurrency in Action、p241）、eden GCは安い、何とか何とか何とか。ユーモアを交えて:)。

それで、あなたはこれについてどうしますか？

編集：明確にするために、私は順列を作成したくありません。sizeof（リストのリスト）が大きいセットを作成したい。

次のデータがあるとします。

したがって、各製品には 1 つ以上のパーツがあり、各パーツには 1 つ以上のタイプがあります。

製品、その部品、およびそのタイプを選択したいと考えています。何千ものエントリがある可能性があると仮定すると、通常は選択と同時にフィルタリングしたいと思います。これらの 3 つのテーブルは、多くの場合、デカルト製品クエリにつながります。そのシナリオを考えると、「(パーツがインクであるタイプ名) で注文された上位 2 つの製品を教えてください」と同等のクエリを実行する必要があります。一部は料理）」

誰にもアイデアはありますか？よろしくお願いします

次のようにデカルト積を使用して 2 つのテーブルを結合しています。

もちろん、これはそれぞれの値を含む 2 つの列を表示します。

ただし、COUNT/GROUP BY および SUM/GROUP BY を使用してデータをさらに操作したいのですが、2 つのテーブルを使用して作業できる関連例を見つけることができませんでした。（それらをすべて個別に行うことは問題ありませんが、それらを一緒に機能させることだけが問題です）。

最終結果として、4 つのタイプのグループ化を示す 3 つの列を表示したいと思います。エントリの数は各タイプに分類され、各タイプの合計金額/SUM が表示されます。

タイプ - タイプの数 - 合計値

あ - 5 - 500

B - 6 - 1000

C - 1 - 50

D - 2 - 100

2つのテーブルがcustassetsありtagsます。INSERT INTOいくつかのテストデータを生成するために、それぞれからランダムな行を取得する多対多のテーブルを作成したいと思いSELECTます（1つのテーブルのランダムな主キーが2番目のテーブルのランダムな主キーとペアになるようにします）。驚いたことに、これは私が最初に思ったほど簡単ではないので、私は自分自身を教えるためにこれを続けています。

これが私の最初の試みです。10custassetsと3を選択しますtagsが、どちらも同じです。最初のテーブルを修正しても問題ありませんが、割り当てられたタグをランダム化したいと思います。

これにより、次のものが生成されます。

次に、次のアプローチを試しました。列リストの2番目のRANDOM()呼び出しを実行します。SELECTただし、これは1つのタグPKを選択し、それに固執するため、さらに悪化しました。

結果：

これはスクリプト言語では簡単であり、ストアドプロシージャまたは一時テーブルを使用すると非常に簡単に実行できると確信しています。しかし、私はそれをただで行うことができINSERT INTO SELECTますか？

ランダム関数を使用して整数の主キーを選択することを考えましたが、残念ながら、両方のテーブルの主キーには増分シーケンスにギャップがあります（したがって、各テーブルで空の行が選択される可能性があります）。そうでなければそれは大丈夫だっただろう！

6 つの配列があり、それぞれに 8 つの要素があります。次のように、すべての配列のすべての要素のすべての可能な組み合わせを明らかにするメソッドを書きたいと思います。

最も効率的な方法で、最もパフォーマンスに適した方法でこれを行うにはどうすればよいですか?