次の形式の順列 (順序に関連する組み合わせ) のリストを考えてみましょう。

この順列グループの生成セットの最小数を見つける必要があります。たとえば、上記の順列を考えると、

最適解ではありません。最適解は (1,5 2 3,4) です。

この解にはセット A={1, 5} B={2} および C={3,4} が含まれていることがわかります。順列の元のリストは、これらのセットの順序付けられたデカルト積です: AXBX C.

順列のリストを、セット A、B、および C として表される可能な限り少ないグループに分割したいと思います。その積には、リスト内のすべての順列が含まれます。順列のリストを生成セットの単一のリストに減らすことが常に可能であるとは限らないため、最終的な答えは通常、セットのリストのリストですが、常にではありません。つまり、セット A、B、および C の積がリスト内の順列の一部を説明するのが通常のケースですが、セット D、E、および F はリスト内の他の順列を説明する必要があります。 .

この問題を解決するための私の大まかな試みは、リスト内の 2 つの順列スロットのいずれかに一致するかどうかを確認し、それらを再帰的にマージすることでした。もしそうなら、私はそれらの2つの組み合わせをマージしました。

生産

残念ながら、このような組み合わせのマージ順序は関連付けられていません。理想的な解決策は、セットの最終的なリストが可能な限り多くの順列を含むように、これらの組み合わせをマージすることです。

結合性の問題を示すために、次の例を取り上げます。これは、生成セットのリストを 2 つ未満に減らすことはできません。

これらを次のルールに従って再帰的にマージするとします。次に、3 番目の列で 2 つのセットをマージして、新しいセットを作成します。この 2 つの行を結合した後、元の 2 つの行を破棄するので、それらが再結合されたり、二重にカウントされたりすることはありません。」これらのマージの順序は重要です。上記の順列のリストが与えられた場合、(1 2 3) と (1 2 4) をマージすると、(1 2 3,4) が得られます。では、次のマージを実行して生成セットを最適化するにはどうすればよいでしょうか? (1 2 5) を見て、2 つの列で (1 2 3,4) と一致することがわかったとします。マージを実行して (1 2 3,4,5) を取得します。すべて順調に見えます。ただし、(5 2 3) と (5 2 4) をマージすると、(5 2 3,4) になります。(5 2 3,4) と (1 2 3,4,5) を比較します。2 列の一致がないので、マージを停止します。

ここで、別の順序でマージしたとします。(1 2 3) と (1 2 4) をマージして (1 2 3,4) を生成します。次に、(5 2 3) と (5 2 4) をマージして (5 2 3,4) を生成します。これら 2 つの製品が一致していることがわかります。次に、(1 2 3,4) と (5 2 3,4) をマージして (1,5 2 3,4) を生成します。生成セットの最終的なリストは (1,5 2 3,4) と (1 2 5) です。したがって、マージ順序が 2 つの異なる回答を生成したことがわかります: (1,5 2 3,4) と (1 2 5) 対 (5 2 3,4) と (1 2 3,4,5)。

この場合、同じ数 (2) の生成セットのリストが各回答で発生するため、おそらくどちらかの回答に落ち着くでしょう。ただし、(1,5 2 3,4) と (1 2 5) の方がやや好ましいです。これは、(1,5 2 3,4) が可能な最大数の組み合わせを含むためです。ただし、900 の組み合わせのリストがあるとします。問題に対するボトムアップ ソリューションのマージ順序により、最適化がセットのリストのリストで可能な最小数である最適化されていない方法で問題を減らすことになります。可能性のあるすべてのマージ パスを事前に調べずに、マージ順序が何であるかを知ることは困難です。これは、私も試した一致を見つける力ずくの方法よりも効率的ではありません。

力ずくの方法も試してみました。ブルートフォース方式の効率が受け入れられないのはなぜですか? このメソッドは、最初にすべての列で一意の整数のリストを見つけます。次に、これらの整数の可能なすべての組み合わせの累乗セットを生成します。列/セット A、列/セット B、および列/セット C についても同様です。次に、これらのセットをサイズ (最大から最小) で並べ替え、他の列の他のすべてのセットの各セットのデカルト積を計算します。これらのデカルト積をループします。これらのデカルト積は、生成セットによってキー付けされ、デカルト積が入力からの順列のリストと一致するかどうかを確認します。これはおおよそ O(n^3) で、n は入力リスト内の組み合わせの数です。これがO(n^2)でもできれば、今より勝てると思います。

メモリに関する考慮事項に関する限り。各スロットのドメインが 1 ～ 12 の整数であると仮定しましょう。3 つのスロットにわたる異なる組み合わせの数は 12!/3! です。7,900 万を超える生の組み合わせを見ています。それは、Google の Guava Collection API によってセットに分割される前のことです (ところで、これを強くお勧めします)。どうにかしてセットを遅延生成することもできます。Google がそうしているように感じますが、メモリの制約は依然として大きいです。

この問題を解決するアルゴリズムを本当に探しています。ただし、最小限の負担でこれを処理する Java ライブラリまたはメソッドがあれば、それも歓迎します。ありがとう。

上級

文のリストで一般的な部分文字列を折りたたんで、それらが異なる領域のみを提示しようとしています。だからこれを取る：

そしてこれを返します：

詳細

• Longest Common Substring アルゴリズムを見てきましたが、それは 2 つの文字列しか比較していないようです。
• 文字列内の単語全体を比較することにのみ関心があります。
• 文字列を左から右に評価するだけです。
• 珍しい部分文字列の長さは、同じ単語数にはなりません (「猫」と「庭のヘビ」)

アルゴリズムのヘルプを探しています。これは LCS 問題の変種だと思います。ある種のサフィックス ツリーの処理だと思います。説明と実装の可能性がある疑似コードが理想的です。

もう一つの例

になる：

たぶん、このアプローチ

このアプローチはどうですか...

First Common Substring の実装を探しています

Longest Common Substring の実装を使用すると (句読点を無視すると)、「I think you are great」となりますが、この例では、最初に出現する共通部分文字列を探しています。

おそらく、最初の部分を取得できるすべての一般的な部分文字列のリストを生成して順序付けた実装です。

編集

比較されるトークンは完全な単語になります。単語全体の最初の最長シーケンスの貪欲な一致を探します。(接尾辞ツリーがアプローチで使用されたと仮定すると、ツリーの各ノードは単語になります)

集合論から：

A∩B = {} の場合、セット A、B は正確に互いに素です

ここで、{} は空のセットです。

参照:普遍的な集合を持つ初等集合論、 Randall Holmes 著

さらにそれは言う;

互いに素な集合 A と B に「交差がない」と言うのは正しくありません。それらには交差、つまり空のセットがありますが、この交差には要素がありません

また、A と B が互いに素である場合、A∩B = B∩A = {}

C# の場合:

なんで？

オブジェクト==の Id を比較するだけの場合 (代わりに、C# の演算子ではない場合)、実際を表す方法はありaますbか?isEmpty Set

valueを長さ lengthのnewBase番号に変換するメソッドがあります。

英語のロジックは次のとおりです。

以下の方法は完全に機能しますが、非常に大きな数が使用されるため、完了するまでに長い時間がかかる場合があります。

たとえば、value=(((65536^480000)-1)/2), newbase=(65536), length=(480000) は、64 ビット アーキテクチャのクアッド コア PC で完了するのに約 1 時間かかります)。

私の質問は、このメソッドを複数のスレッドが数値の一部を処理できるように変更するにはどうすればよいですか?

私は C# で作業していますが、それに慣れていない場合は、疑似コードでも問題ありません。

注: メソッドはこの質問からのものです:ほとんど 0 のセットを返すデカルト積サブセット

可変数のキーで zunionstore を呼び出す必要がある lua スクリプトがあります。次のコードを実行しようとしています。

重要な行は次のとおりです。

キーのリストと実際の呼び出しを作成します。

ただし、実行すると次のエラーが発生します。

では、lua スクリプト内で計算された可変数のキーを redis.call("zunionstore"...) コマンドに渡すにはどうすればよいでしょうか?

前もって感謝します！

子のセットに複数の特定のレコードが含まれている親だけを返そうとしています。このテーブルを考えると：

他のレコードがある場合でも、子レコードと子レコードのProduct両方を持つリストを見つけたいです。どちらが返されますか...AZCA