2

セットを考えると

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

グループを見つけるための簡単な (そしてできれば効率的な) アルゴリズムは何ですか: {1} {2,3} {4}

これはセットの最短リストであるため、次の場合:

  • すべてのメンバー (1 ～ 4) が表されます。
  • 2 と 3 は、元のセットでは常に一緒に表示されるため、グループ化されています。

実際のデータは、値型ではなく、一連の参照です。

編集:私が試みたことを要約しても質問を助けるために何もしないと思います.おそらくこれのための圏論のアルゴリズムがあるので、気を散らすものとして役立つだけですが、(娯楽上の理由から)ここに行きます:

  • ユニオン演算子を使用しようとしているハッシュ セットを集計しました。
  • gethashcode で集計に対して groupedby を実行しました。
  • 最初のエントリを候補セットとして使用してリストを反復処理し、他のメンバーと比較するときに徐々に減らすようにしました。これはうまく機能しませんでした。セットの数が可能な限り少なくなったかどうかはわかりません。
4

3 に答える 3

7

まず、問題を注意深く特徴付けましょう。

リレーションは、2 つの引数を取り、リレーションが成立するかどうかを示す bool を返す関数です。たとえば、「未満」はリレーションです。

等価関係は再帰的な関係です-- すべてのアイテムはそれ自体に関連しています --対称-- A が B に関連している場合、B は A に関連しています -- そして推移的です -- A が B に関連し、B が関連している場合C に対して、A は C に関連付けられます。

同値関係は、セットの同値分割を形成します。つまり、各サブセット内のすべての要素が互いに関連している多数のサブセットです。各サブセットは等価クラスと呼ばれます。たとえば、「A と B の差が 3 で割り切れる場合、A と B は関連している」という整数の同値関係は、次の 3 つの同値クラスを形成します。 

{0, 3, -3, 6, -6, ... }
{1, 4, -2, 7, -5, ... }
{2, 5, -1, 8, -4, ... }

あなたはすべてのセットの和集合を形成したいと考えています:

{1, 2, 3, 4} U {2, 3, 4} U {1, 4} U {1} --> {1, 2, 3, 4}

次に、そのセットを等価クラスに分割します。この等価関係は、「A と B は、元のセットのそれぞれに常に一緒に現れる場合にのみ、関係がある」です。

各要素を関連する等価クラスにマップする辞書を作成することから始めます。あなたが正しく指摘しているように、最悪のケースは、すべての同値クラスに 1 つの要素しか含まれない同値パーティショニングがあることです。そのため、それから始めましょう。(ちなみに、これは「A が B に等しい」同値関係の同値分割です。)

1 --> { 1 }
2 --> { 2 }
3 --> { 3 }
4 --> { 4 }

次に、ユニオンからすべての順序付けられていないペアのセットを作成します。

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

これらの順序付けられていないペアのそれぞれについて、「このペアに関係が成り立つか」という質問をしますか?

{1, 2}、{1, 3}、の場合{1, 4}、関係は成立しません。

{2, 3}関係が成り立つため、 と バケットを一緒にマージし2ます3。

1 -->     { 1 }
2 --\ 
     -->  { 2, 3 }
3 --/
4 -->     { 4 }

{2, 4}との関係は{3, 4}成立しません。

これで、すべての要素から対応する等価クラスへのマップが作成されました。

わかる？

このアルゴリズムを正しく理解したら、それを最適化する方法はいくつかあります。まずは正解。

私がここで何をしたかに注意してください: equivalence partitioningの一般的な問題を解決することで、特定の問題を解決しました。これをどのように書くかが賢明であれば、ロジックを再利用して、特定の問題だけでなく、等価分割の問題を解決することができます。

于 2013-05-31T15:48:17.870 に答える