問題タブ [cartesian-product]

私は次の情報を与えられたすべての組み合わせを見つける方法を理解しようとしています：

JSONデータセットから始めます。

私が理解しようとしているのは、このデータセットを取得し、各行の「Q」、「R」、「W」、または「T」要素のいずれかを選択するときに可能なすべての組み合わせを生成する方法です。

だから私の最終結果がこのようなものになることを願っています

視覚化するのが最も簡単だと思うのでJSONを使用しましたが、C＃でこれを実現する方法を知っている人はいますか？

これが十分に明確でない場合は、この質問を正確に行う方法を理解するのに苦労していることを知らせてください。

Factorに手を出し始めたところです。2 つのシーケンスのデカルト積を計算したい:

私が見たいのは、シーケンスのシーケンスです:

この単語を使用するとcartesian-product、シーケンスのシーケンスのシーケンスが得られます。

私も試しまし[ 2array ] cartesian-mapたが、同じことが得られます。最後に を試み[ 2array ] cartesian-eachましたが、各ペアが別々にスタックにプッシュされます。少なくともフラットですが、それらをすべて 1 つの配列にまとめたいと思います。

どうすればいいですか？

1 つのテーブルのデカルト積を実行する必要がありますが、同じ行はありません。今私が持っています：

しかし、1300 行の T_Car テーブルの場合、ほぼ 2 分かかります。OPTION (HASH JOIN) と OPTION (MERGE JOIN) を使用しようとしましたが、これはエラーになります:

このクエリで定義されたヒントのため、クエリ プロセッサはクエリ プランを作成できませんでした。ヒントを指定せず、SET FORCEPLAN を使用せずに、クエリを再サブミットしてください。

このクエリを最適化する可能性はありますか?

inputArray = Object[n][]を受け入れ、 n は任意の整数であり、n 個の部分配列のすべての値の間で可能な n サイズの組み合わせのリストを出力するJava メソッドを作成したいと考えています。以下に例を示します。

入力配列: (Object=String および n=3)

望ましい出力:

n明らかに、事前にわからないため、メソッド内にネストされたループを固定することはできません。だから、それを解決する唯一の方法は再帰的な方法だと思いますか? 推奨事項はありますか？

PS: Web サイトに単純な組み合わせに関する投稿があることは承知しています。

私は一種の2次元の組み合わせアルゴリズムを探しています..それが正しい言い回しである場合。私はPHPの経験は豊富ですが、アルゴリズムや高度な数学の経験はありませんので、ご容赦ください。

別の要素のセットと組み合わせて、後で分析できるようにすべての可能な組み合わせを計算したい要素のセットがあります。セット内の要素の数は決して変更されません。両方のセットには常に5つの要素があります。

これが正しい言い回しかどうかはわかりませんが、セット2のアイテムに分割されたセット1のアイテムのすべての組み合わせを確認したいと思います。両方のセットのすべての要素は、可能性ごとに1回だけ使用する必要があり、セット1の要素はセット2の要素内でグループ化できるため、次のような結果の配列が得られます（例としていくつかのランダムな値）。

など。そのような値。これに関するあらゆる種類のフィードバックを歓迎します。特に、次の点に注意してください。

• PHPでこのようなものをコーディングする方法は？再帰関数を介して？デカルト積アルゴリズムを使用しますか？
• いくつの組み合わせが可能ですか？5 ^ 10？
• 前のポイントに応じて：Webアプリ内でこのデータをリアルタイムで操作することは可能ですか？おそらく事前に計算を行う必要があると思われるよりも1,000万の組み合わせがある場合は、結果の分析を保存して、ライブアプリの実行中にそれを処理しますか？
• いくつかの制限があります（例：セット2のアイテム「1」、「2」、「3」には常にセット1のアイテムが少なくとも1つ必要です）が、その後の分析中に不要な組み合わせが削除されるため、それをに含める必要はありません。その時点でこれらを組み込むことによって計算時間を短縮できない限り、組み合わせアルゴリズム？

私の質問はあまり明確ではないかもしれないので、もっと多くの、またはより良い情報を提供する必要があるかどうか尋ねてください。

前もって感謝します

2012年2月28日更新

インターネットで見つけたべき集合とデカルト積関数のPHP実装を試しました（この種のものは、自分でコーディングするのは少し遠いです）。したがって、このコードを実行すると、次のようになります。

これは、powerSet関数が$powersetに入れるものです。

そして、これはデカルト関数が返すものです：

ですから、それは私が望んでいたことを実行しますが、最も難しい部分ではありません。組み合わせを「個別に」考慮し、Set1をSet2内に配布せず、すべてのSet1アイテムが3つのSet2アイテムすべてで使用されるようにします。

• これら2つの関数の使用を誤解していますか？パワーセットとデカルト積を組み合わせて結果を出す方法について、私は正しく理解していないと思います。デカルト（）関数内でpowerSet（）関数を呼び出す必要がありますか？
• たぶん、それらの特定のPHP関数は私の目的を正確に果たしていないのでしょうか？私はここでそれらを見つけました：
  • べき集合： http： //bohuco.net/blog/2008/11/php-arrays-power-set-and-all-permutations/
  • デカルト積：PHP連想配列を使用したデカルト積の検索

別の更新：プログラミング参照なしで問題を修正する

この問題は、私が戦略ゲーム用に作成している分析ツールに関連しています。ツールを使用するたびに、プレイヤーはユニットの大規模なコレクションから5つの異なるユニットを選択できます。これらのユニットは、さまざまな方法で他の（静的）エンティティ（これらを「プール」と呼びましょう）と組み合わせることができます。ユニットには、特定のプールと組み合わせると、プレイヤーの戦略を改善する場合と改善しない場合がある特性があります。例えば：

• ユニットAはプール1にいるのが好きですが、プール2にいるのは嫌いです
• ユニットAもそこにいる場合を除いて、ユニットBはプール1にいることを嫌います
• 等..

このツールの目的は、どのユニットがどのプールに入るのかという最適な組み合わせを見つけることです。ルールは次のとおりです。

• 約50のコレクションから常に5つの異なるユニットが選択されています。これらのユニットはすべて異なる特性を持っています。
• 常に同じ5つのプールがあります。それらには異なる特性がありますが、プールはより大きなコレクションから選択されるのではなく、常に同じです。
• 各プールには、0から5までの複数のユニットを含めることができます。
• 各ユニットは1つのプールにのみ存在できます。

入力は次のとおりです。

• 5つの可変単位のリスト：A、B、C、D、E
• 5つの静的プールのリスト：Pool1、Pool2、Pool3、Pool4、Pool5

出力は、前述のルールに基づいて、これら2つのリスト間のすべての可能な組み合わせである必要があります。いくつかの例：

組み合わせ1

• プール1：A
• プール2：B
• プール3：C
• プール4：D
• プール5：E

組み合わせ2

• プール1：A、B、C
• プール2：D
• プール3：E
• プール4：
• プール5：

組み合わせ3

• プール1：C
• プール2：
• プール3：A
• プール4：B
• プール5：D、E

組み合わせ4

• プール1：
• プール2：
• プール3：A、B、C、D、E
• プール4：
• プール5：

等...

だから私がしたいのは：

1. 存在するユニットとプールのすべての可能な組み合わせを取ります。
2. それらを調べて、ユニットとプールの間の相乗効果に基づいて、組み合わせに「戦略値」を割り当てます。
3. 「戦略的価値」が最も高い上位10の組み合わせを取り上げます

手順2と3は問題ありません。私が抱えている問題は、プール内のユニットのすべての可能な組み合わせを生成することです。

うまくいけば、これは問題のより明確な説明です

これが私が抱えている問題の簡略版です。ベクトルがあるとします

そしてもう一つ

そして、次のマトリックスを作成したいと思います。

これはデカルト積とも呼ばれます。どうやってやるの？

私はいくつかのテーブルを持っています：

私のせいにしないでください。これは既存のアプリケーションです。データベースを作成しておらず、内部にデータが多すぎてそれに応じてレポートが作成されているため、構造に触れることができません。尋ねられたとおりにレポートを変更しようとしています。

私はクエリを実行します：

デカルト積を持ってきます。が欲しいです：

（次に、レポートでsuc、dep、secの順にグループ化します）

代わりに、私は得ました：

等々。sucursALL 、ALL depart、ALLをもたらしsection、場合によっては複製されempます。

何かが足りないのですが、何がわかりません。手がかりはありますか？

私はこの問題に対する答えがあるとほとんど確信していますが、私の一生の間、それを行う方法を理解することはできません。

私が3つのセットを持っているとしましょう：

そして、デカルト/クロス積を計算する方法を知っているので（このサイトや他の場所で、あちこちでカバーされています）、ここではそれについては説明しません。

私が探しているのは、セット全体を生成したり、n番目のアイテムに到達するまで反復したりせずに、デカルト積から特定のアイテムを簡単に選択できるアルゴリズムです。

もちろん、このような小さなサンプルセットを簡単に繰り返すことはできますが、私が取り組んでいるコードは、はるかに大きなセットで機能します。

したがって、私は関数を探しています。それを「CP」と呼びましょう。ここで、

そして、答えは多かれ少なかれO（1）時間で生成されます。

私は、必要なA、B、Cから要素のインデックスを計算し、元の配列からそれらを返すことが可能であるはずだという考えに従ってきましたが、私の試みはこれを正しく機能させるには、これまでのところ、機能していません。

私はPerlでコーディングしていますが、Python、JavaScript、またはJava（およびおそらく他のいくつか）からソリューションを簡単に移植できます。

これらのタイプのアルゴリズムの言語（つまり、これをグーグルで検索する方法）がよくわからないので、探しているものを示します。

私は3つの配列を持っています（ソース配列は同じ長さではありません）：

これらの配列のすべての可能な組み合わせが必要です。

• 各ソース配列から取得される要素は1つだけです。
• array1、array2、array3の順序が崩れることはありません（ABC常に前に来るxyz常に前に来る123）。

したがって、結果は次のようになります。

結果の順序は私には関係ありません。

PHPで動作しますが、同様の言語または擬似コードはもちろん問題ありません。または、どの特定のタイプの順列/組み合わせアルゴリズムを検討する必要があるかについてのヒントを取得します。

Haskell でかなり大きいが有限のデカルト積を生成したいと思います。これを反復する必要があります (平均場モデルの分配関数を考えてください)。自然なことはsequence、次のように を使用します。

残念ながら、大きな のn場合、これはメモリに収まらず、たとえば要求するとすぐにヒープが不足しlength lます。同じことを怠惰に行う方法が必要です。このように、私は最終的に3進数の算術を「再発見」しました。

（これは機能します）しかし、車輪を再発明したような気がします。さらに、あまりにも具体的です. 製品を生成するためのより良い怠惰な方法は何でしょうか?