問題タブ [cartesian-product]

テーブルAとテーブルBの2つのテーブルがあります。これらは同じ列を持ち、データは実質的に同じです。どちらも自動インクリメントされたIDを持っていますが、2つの違いは、同じレコードに対して異なるIDを持っていることだけです。

列の中には、一意ではないIDENTIFIER列があります。つまり、両方のテーブルに同じIDENTIFIERを持つレコードが（非常に少数）あります。

ここで、テーブルAのIDとテーブルBのIDの間の対応を見つけるために、次のようにIDENTIFIER列でこれら2つのテーブルを結合する必要があります（すべての目的で自己結合です）。

しかし、IDENTIFIERは一意ではないため、IDENTIFIERの繰り返し値の可能なすべての組み合わせが生成されるため、これは望ましくありません。

理想的には、IDENTIFIER値が繰り返されるID間で、その順序に基づいて1対1の関連付けを生成したいと思います。たとえば、テーブルA（したがってテーブルB）に異なるIDと同じIDENTIFIER値を持つ6つのレコードがあるとします。

それが理想的です。とにかく、IDの順序に関係なく、1対1の関連付けを生成する方法は、引き続き問題ありません（ただし、推奨されません）。

御時間ありがとうございます、

シルヴィオ

Rubyで、Cのような言語、または擬似コードを使用して、長さがそれぞれ異なる整数の可変数の配列の直積を作成し、結果を特定の順序でステップ実行する方法の例を探しています。 ：

したがって、[1,2,3]、[1,2,3]、[1,2,3]：

私が見た典型的な結果の代わりに（以下に示す例を含む）：

この例の問題は、最初の2つの組み合わせがすべて試行されるまで、3番目の位置がまったく探索されないことです。これを使用するコードでは、正しい答えは一般に（はるかに大きい）1,1,2ですが、それを見つける前に、数千ではなく数百万の可能性を調べます。

私は100万から数億の結果セットを扱っているので、それらを生成してから並べ替えることはここでは実行できず、最初の例でそれらを注文する理由を無効にします。以前のデカルト積生成から。

上記のいずれかを明確にするのに役立つ場合に備えて、これを今すぐ行う方法を示します（これは正しい結果と正しいパフォーマンスを示しますが、希望する順序ではありません。つまり、上記の2番目のリストのように結果を作成します）。

更新：私は、3が追加される前に、1、2のすべての組み合わせが調べられ、次に3と1がすべて、次に3と2と1がすべて、次に3がすべてが調べられる解決策を求めていることを明確にしませんでした、2。言い換えれば、「垂直」の前に「水平に」以前のすべての組み合わせを探索します。これらの可能性が探求される正確な順序、つまり1,1,2または2,1,1は重要ではなく、3に混合する前に2と1すべてが探求されるということです。

特定の問題に遭遇し、そのためのアルゴリズムを探していました。解決すべき問題は以下のとおりです。

以下のような組み合わせがあるとしましょう

1 - 3 - 5

1 - 4 - 5

1 - 8 - 5

2 - 4 - 5

3 - 4 - 5

2 - 4 - 7

これらの組み合わせは、特定のセットから生成されました。この特定のケースでは、

{1},{3,4,8},{5}

{2,3}、{4}、{5}

{2}、{4}、{7}

私がやりたいのは、これらの組み合わせからセットを再作成することです。これらの組み合わせには、複数のソリューションがあることを知っています。

最初の解決策

{1}、{3、4、8}、{5}

{2, 3}, {4}, {5}

{2}、{4}、{7}

2番目のソリューション

{1}、{3、8}、{5}

{1, 2, 3}, {4}, {5}

{2}、{4}、{7}

3番目のソリューション

{1}、{3、4、8}、{5}

{3}、{4}、{5}

{2}、{4}、{5、7}

しかし、最終的な (最適な) 解決策は、可能な限りセット数の少ないものか、セット数に関してすべてが同等である場合のランダムなものです。

そのような問題のアルゴリズムは存在しますか? この種の問題を扱ってきた人が私にヒントを与えることができれば幸いです。

編集:私が探しているのは、n-ary積(Nのデカルト積)の分解であるように見えます

編集: このトピックについてさらに調査した結果、この問題は「グラフ理論」で「最小クリークカバー」問題として知られていることがわかりました

よろしく、バズ

MySQL 結合コマンドのドキュメントを読むと、デカルト積を見つけてその結果から選択するだけで、すべてjoinsが類似しているように見えます。 これは正確な仮定ですか？ 代わりに、独自のサブクエリを作成し、それらから選択する必要がありますか?,

ジャグ配列のデカルト積を生成する方法を理解するのに問題があります。私はグーグルで検索しましたが、反復言語の意味を見つけることができないようです。だから私は自分でそれを理解しようとしていますが、私は障害にぶつかりました。問題をもう少し明確に定義しましょう

このような配列の配列があるとしましょう

どうすればそこから

編集：これは単なる例です。最初の配列には動的な数の配列を含めることができ、各配列は動的なサイズです。

xが外部配列の要素数であり、y []が長さxの動的配列である場合、要素には内部配列の要素数が含まれます。次に、AのxはBのyになり、BのxはAのyの乗法和になります（証明されていない、例から推測）

Aのxは動的であるため、関数は再帰的である必要があります。これが私の試みです。

これは私が得た限りです。再帰関数は、[recursionの深さ]の1つの要素の一時配列を構築し、maxdepthになると、そのBを割り当て、Bsイテレーターを増やし、バックトラックして、[recursionの深さ]の次の要素を選択します。 c。

問題はsegfaultsであり、その理由がわかりません。

親愛なる皆さん、たとえば3つの値をとる変数が与えられた場合、私はこれらの変数のたとえばトリプレットのすべての可能な組み合わせを生成しようとしています。

このコードはトリックを行いますが、

それはやや、うーん、不器用で、3つ以上の変数の組み合わせに対して同じことをしようとした場合にのみ悪化します

したがって、私のPython101の質問は次のとおりです。

1. イテレータを使用して上記のコードを書き直すにはどうすればよいですか？つまり、上記の「状態」の要素を生成するイテレータを持つことは可能ですか？

2. トリプレットだけでなく、4プレット、5プレットなどを生成するためにこれを拡張することは可能ですか？

タイトルが示すように、Ruby はデカルト積型を許可しますか? どこにも何も見つかりません。

ありがとう

私は次のようなクラス構造を持っています：

一人です。彼は1..n匹の犬を飼っています。各犬には1..n匹の子犬がいます。

各犬から1匹の子犬を取り出して、可能なすべての子犬の組み合わせのリストが必要です。例えば：

犬1子犬A、犬2子犬A犬1子犬A、犬2子犬B犬1子犬B、犬2子犬A犬1子犬B、犬2子犬B

SQLテーブルにある場合は、次のようにしてテーブルを「乗算」します。

このようなことを行うためのlinqっぽい方法はありますか？

本当にありがとう

Haskellで2つのリストのデカルト積を作成したいのですが、その方法がわかりません。デカルト積は、リスト要素のすべての組み合わせを提供します。

これは実際の宿題の質問ではなく、そのような質問とは関係ありませんが、この問題を解決する方法は、私が立ち往生している問題に役立つ可能性があります。

指定された数のベクトルの要素の可能な組み合わせをすべて生成したいと思います。

たとえば、 for [1 2]、[1 2]および[4 5]要素を生成したい:

[1 1 4; 1 1 5; 1 2 4; 1 2 5; 2 1 4; 2 1 5; 2 2 4; 2 2 5]

問題は、組み合わせを計算する必要があるベクトルの数がわからないことです。この場合のように 3 つある場合もあれば、10 つある場合もあり、一般化が必要です。MATLABでこれを手伝ってもらえますか? このタスクを実行できる定義済みの関数は既にありますか?