6

アイテムのリストがあるとしましょう。各アイテムは単純な構造で定義されています

struct simpleItem
{
    String Category1;
    String Category2;
    ...
    String CategoryN;
}

各項目には、いくつかのカテゴリに属する​​一連の値があります。カテゴリの数 N はリストの処理時に既知であり、各項目には同じ量のカテゴリがあり、カテゴリごとに値が 1 つだけあり、重複する項目はありません。ただし、各リストには異なるカテゴリ セットを含めることができます。

これらのアイテムをカテゴリごとにグループ化する方法を探しています。これらのグループが、カテゴリの各順列を組み合わせて単一のアイテムに分解された場合、重複のない元の組み合わせになります。

グループの結果は次のようになります。

struct grouped
{
    String[] Category1;
    String[] Category2;
    ...
    String[] CategoryN;
}

例

この例では、カテゴリを 3 つに制限しますが、N 個のカテゴリが存在する可能性があります。

カテゴリー

動物、目の色、毛皮

「動物」カテゴリの選択肢: 猫、犬、ネズミ、馬

「目の色」カテゴリの選択肢：青、黄、緑、赤、オレンジ

「毛皮」カテゴリの選択肢: ロング、ショート、カーリー

リストにこれら 3 つのカテゴリの順列がすべて含まれている場合、最終結果は次のようになります。

グループ 1 :
動物 [猫、犬、ネズミ、馬]
目の色 [青、黄、緑、赤、オレンジ]
毛皮 [ロング、ショート、カーリー]

たとえば、サブリストがある場合：

  1. 猫、青、長い
  2. 猫、青、短い
  3. 犬、青、長い
  4. 犬、青、短い
  5. 犬、グリーンロング
  6. ラット、レッド、ショート
  7. ラット、ブルー、ショート

このリストを入力(A)としましょう

これらの項目を group にグループ化した後、 : になる可能性があります (他の可能性がある可能性があります)。グループ化の基準は、出力グループをできるだけ少なくすることです。

グループ 1:
動物 [猫、犬]
目の色 [青]
毛皮 [長い、短い]

グループ 2:
動物 [犬]
目の色 [緑]
毛皮 [ロング]

グループ 3:
動物 [ラット]
目の色 [赤、青]
毛皮 [短い]

これらのグループを出力(B)と呼びましょう

ご覧のとおり、結果のグループの各項目を組み合わせることで、(A)の 7 つの要素の元の入力リストに戻ります。

質問

そこで、これらのグループを生成するアルゴリズムを作成しようとしています。私はLINQでこれをやろうとしていますが、他の提案も受け付けています。(A )から(B)に行く方法について何か提案はありますか?

4

1 に答える 1

3
  1. 各入力を取得し、それを独自のグループとして扱います。
    • したがって、たとえば、Cat、Blue、Long は [Cat]、[Blue]、[Long] のグループになり、各カテゴリには 1 つのアイテムが含まれます。
  2. 最初のグループから始めて、リスト内の各グループを調べます。リスト内の他のグループとペアにします。これらのグループのペアが適切な基準を満たしている場合は、1 つのグループに結合します。
    • グループをマージする基準は、n-1 個のカテゴリの値のセットが同じで、1つのカテゴリ セットだけが一致しない場合です。その場合は、n-1 個の類似カテゴリが同じであり、残りのカテゴリが集合の共通部分である新しいグループを作成します。
  3. 一致が見つかったら、ペアの比較を停止し、最初のグループの最初の項目からやり直します。(ここで遅延実行を使用すると、一致が見つかったらすぐにグループをペアリングする必要がなくなります。)
  4. 一致するものが見つからずにセット全体を調べた場合、それ以上の組み合わせはありません。

だから、あなたの例を見てみましょう。最初に、1 番目と 2 番目のグループをペアにします。最初の 2 つのカテゴリ セットは同じですが、3 番目のカテゴリ セットは異なるため、マージできます。次のようなリストが作成されました。

  1. [ネコ]、[ブルー]、[ロング、ショート]
  2. [犬]、[青]、[ロング]
  3. [犬]、[ブルー]、[ショート]
  4. [犬]、[緑]、[ロング]
  5. [ラット]、[レッド]、[ショート]
  6. [ラット]、[ブルー]、[ショート]

次に、(新しい) 1 番目と 2 番目のグループを比較します。1 番目と 3 番目のカテゴリの両方が一致せず、マージされません。次に、1 番目と 3 番目を比較します。同じ 2 つのカテゴリは一致しません。最初のグループは他のグループと一致しません。それでは、2番目のグループに進みます。3番目とペアにします。最初の 2 つのカテゴリが異なるため、マージできます。

  1. [ネコ]、[ブルー]、[ロング、ショート]
  2. [犬]、[青]、[ロング、ショート]
  3. [犬]、[緑]、[ロング]
  4. [ラット]、[レッド]、[ショート]
  5. [ラット]、[ブルー]、[ショート]

最初からやり直して、最初のグループと 2 番目のグループをペアリングします。それらは一致します。最初のカテゴリは異なり、2 番目は同じ、3 番目は同じです。それは今です：

  1. [ねこ、いぬ]、[青]、[ロング、ショート]
  2. [犬]、[緑]、[ロング]
  3. [ラット]、[レッド]、[ショート]
  4. [ラット]、[ブルー]、[ショート]

最初のものを他の 3 つのそれぞれと比較しますが、一致するものはありません。次に、2 番目を他の 2 つと比較しますが、一致するものはありません。最後に、2 番目のカテゴリのみが異なるため、3 番目と 4 番目が一致します。

  1. [ネコ、イヌ]、[ブルー]、[ロング、ショート]
  2. [犬]、[緑]、[ロング]
  3. [ラット]、[レッド、ブルー]、[ショート]

最後に、すべての組み合わせを調べますが、マージ条件に一致するグループはなく、完了です。

于 2013-08-26T15:22:28.913 に答える