問題タブ [cartesian-product]

次の文字列を指定します。

"foo bar-baz-zzz"

文字 " " と "-" で分割して値を保持したいのですが、入力のすべての組み合わせを取得します。

を含む二次元配列を取得したい

この方法で文字列を分割するための Java の組み込みメソッドはありますか? たぶん、Apache Commons のようなライブラリでしょうか? または、for ループの壁を作成する必要がありますか?

次の SQL は、すべて Null を返しBT.Bt_NameますL.date_back。が重複しているBT.Bt_Namesのみを選択したいL.Bc_id

Is NULLCOUNT(L.Bc_id)のすべてのレコードで >1 になるのは結合ですか? L.Date_back参考までに、1 つだけを返す必要があります (意図的な入力エラー)。

Javaで任意の数の空でないセットのデカルト積を計算したいと思います。

私はその反復コードを書きました...

...しかし、私はそれがかなりエレガントではないと感じました。誰かがより良い、まだ反復的な解決策を持っていますか？いくつかの素晴らしい機能のようなアプローチを使用するソリューション？そうでなければ...それを改善する方法についての提案？エラー？

誰かが私のために、私が現在使用しているものよりも効率的なデカルト積アルゴリズムを示してくれませんか（あると仮定して）。私はSOを見回して少しググったが、明らかなものが何も見えないので、何かが足りない可能性がある。

これは、コードで行うことの非常に単純化されたバージョンです。2つの整数は、1つ以上のオブジェクトを取得するために使用されるルックアップキーであり、2つのルックアップからのすべてのオブジェクトがペアになって新しいオブジェクトになります。

はるかに大規模で複雑なシステムのこの小さなコードブロックは、データセットがスケールを超えて動作しているため、パフォーマンスの大きなボトルネックになります。これの一部は、オブジェクトの格納に使用されるデータ構造と関連するルックアップを改善することで軽減できる可能性がありますが、私が感じる主な問題は、デカルト積自体の計算です。

編集

そこで、Marcのコメントに応えて使用できるトリックがあるかどうかを確認するために、アルゴリズムの特定の使用法に関するもう少し背景を説明します。システム全体は、グラフデータのセットに対してSPARQLクエリを処理するSPARQLクエリエンジンです。SPARQLはパターンベースの言語であるため、各クエリは、グラフと照合される一連のパターンで構成されます。後続の2つのパターンに共通の変数がない（互いに素である）場合、クエリ全体の可能なソリューションのセットを取得するには、2つのパターンによって生成されたソリューションのデカルト積を計算する必要があります。パターンはいくつでも存在する可能性があり、クエリが一連の互いに素なパターンで構成されている場合、可能なソリューションでかなり指数関数的な拡張につながる可能性のあるデカルト積を複数回計算する必要があります。

どういうわけか、既存の回答から、適用できるトリックがあるかどうか疑問に思います

アップデート

そのため、デカルト積を実行する必要性を最小限に抑え、クエリエンジンを全体的に最適化するために、実装した内容に関する更新を投稿すると思いました。製品の必要性を完全に排除できるとは限らないことに注意してください。ただし、ほとんどの場合、最適化できるため、結合される2つのセットのサイズははるかに小さくなります。

トリプルパターンのセットである各BGP（基本グラフパターン）はブロックとして（本質的に）実行されるため、エンジンは最適なパフォーマンスを得るために、BGP内でパターンを自由に並べ替えることができます。たとえば、次のBGPについて考えてみます。

最初のパターンの結果は2番目のパターンと互いに素であり、最初の2つのパターンの結果は個々の結果のデカルト積であるため、クエリをそのまま実行するにはデカルト積が必要です。3番目のパターンは最初のパターンの可能な結果を​​制限するため、この結果には実際に必要な結果よりもはるかに多くの結果が含まれますが、この制限はその後まで適用されません。しかし、そのように再注文した場合：

2番目と3番目のパターンはまだばらばらであるため、最終結果を得るにはデカルト積が必要ですが、並べ替えることにより、2番目のパターンの結果のサイズを制限します。つまり、デカルト積のサイズははるかに小さくなります。

他にもさまざまな最適化がありますが、SPARQLエンジンの内部についてかなり詳細に説明し始めているので、ここではそれらを投稿しません。詳細に興味のある方は、コメントを残すか、ツイートを送ってください@RobVesse

私はしばらくの間、これに頭を悩ませようとしてきましたが、良い解決策を思いつくことができませんでした. ここに行きます：

セット数が与えられた場合:

セットのリストから可能なすべてのシーケンスを生成したいと考えています。この例では、シーケンスの長さは 5 ですが、約 20 までの長さにすることができます。位置 1 の場合、考えられる候補はそれぞれ「A」と「T」であり、位置 2 の場合、唯一のオプションは「C」です。の上。

上記の例の答えは次のようになります。

ACATG, ACCTG, ACGTG, TCATG, TCCTG, TCGTG

私はこれをルビーで行っており、マスター配列内の配列としてさまざまなセットを持っています:

最初は再帰的な解決策が最善だと思っていましたが、適切に設定する方法がわかりませんでした。

私の 2 番目のアイデアは、各セットのインデックスを持つ同じサイズの別の配列を作成することでした。したがって、00000 は「ACATG」の上の最初のシーケンスに対応し、10200 は「TCGTG」に対応します。00000 から始めて、最後のインデックスを 1 増やし、問題のセットの長さ (上記の set1 の場合は 2、set2 の場合は 1) でそれをモジュロします。

しかし、このソリューションについて考えれば考えるほど、この非常に小さな問題には複雑すぎるように思えました。私が見逃しているもっと簡単な解決策があるはずです。誰か助けてくれませんか？

/ニック

リスト L = [a, b, c] があり、タプルのリストを生成したい:

L * L を実行しようとしましたが、うまくいきませんでした。誰かがPythonでこれを取得する方法を教えてもらえますか.

この質問は、与えられた数のベクトルのデカルト積を計算する方法を尋ねます。ベクトルの数は事前にわかっていてかなり少ないため、ネストされたforループを使用して解を簡単に取得できます。

ここで、選択した言語で、ベクトルのベクトル（またはリストのリスト、セットのセットなど）が与えられたとします。

デカルト積を計算するように求められた場合、それは

再帰を続行します。たとえば、quick＆dirty pythonでは、

それを繰り返し計算する簡単な方法はありますか？

（注：答えはPythonである必要はありません。とにかく、この質問のように、Pythonではitertoolsの方がうまく機能することを認識しています。）

Perlで順列をやりたいです。たとえば、私は 3 つの配列を["big", "tiny", "small"]持ってい["red", "yellow", "green"]ます["apple", "pear", "banana"]。

入手方法:

これは順列と呼ばれることを理解しています。しかし、私はそれを行う方法がわかりません。また、いくつの配列を使用できるかわかりません。3 つまたは 4 つある可能性があるため、ネストされたループは実行したくありません。

n セットのデカルト積を返す関数を実行しようとしましたが、Dr Scheme では、セットはリストのリストとして与えられます。私は一日中これで立ち往生しています。いくつかのガイドラインが必要です。始めること。

----後で編集-----

これが私が思いついた解決策です。これが最も効率的でもきちんとしたものでもないと確信していますが、私はSchemeを3週間しか勉強していないので、簡単にしてください。

seqClojureで3つのデカルト積を同時に計算するための優れたアルゴリズムはありますか？

私は主に言語とその並行性機能を学ぶ手段として、Clojureで小さな趣味のプロジェクトに取り組んでいます。私のプロジェクトでは、3seq秒のデカルト積を計算する必要があります（そして結果を使って何かをする必要があります）。

cartesian-productで関数を見つけましたclojure.contrib.combinatorics。これはかなりうまく機能します。ただし、デカルト積の計算がプログラムのボトルネックであることが判明しました。そのため、同時に計算を行いたいと思います。

さて、関数については、魔法のように物事を並行させるmap便利な代替手段があります。pmapかっこいいです:)。残念ながら、そのようなものは存在しませんcartesian-product。ソースコードを見てきましたが、自分で並行させる簡単な方法が見つかりません。

また、自分でアルゴリズムを実装しようとしましたmapが、アルゴリズムのスキルは以前とは違うと思います。私はなんとか2秒間醜いものを思いついたseqが、3つは間違いなく遠すぎる橋だった。

それで、誰かがすでに並行しているアルゴリズム、または私が自分自身を並列化できるアルゴリズムを知っていますか？

編集

別の言い方をすれば、私が実際に達成しようとしているのは、このJavaコードに似たものを達成することです。