c# - ジャグ配列の一意の行を見つける

Question

文字列のジャグ配列があり、一意のすべての行を見つける必要があります。たとえば、

[ 
 ["A","B"] , 
 ["C","D","E"], 
 ["B", "A"],
 ["E","A"] 
]

行0と行2が重複しているため、これにより行1と行3が返されます。これはどのように行うことができますか？ハシェットを利用できますか？

Answer 1

順序を無視したい場合は、重複（すでに言及しているためHashSet）と結果には、重複のない配列のみが含まれている必要があります。

カスタムIEqualityComparer<String[]>を実装して、Enumerable.GroupBy一意の配列のみを選択できます（group-count == 1）：

class IgnoreOrderComparer : IEqualityComparer<string[]>
{
    public bool Equals(string[] x, string[] y)
    {
        if (x == null || y == null) return false;
        return !x.Distinct().Except(y.Distinct()).Any();
    }

    public int GetHashCode(string[] arr)
    {
        if (arr == null) return int.MinValue;
        int hash = 19;
        foreach (string s in arr.Distinct())
        {
            hash = hash + s.GetHashCode();
        }
        return hash;
    }
}

残りは簡単です：

String[][] uniques = arrays.GroupBy(arr => arr, new IgnoreOrderComparer())
                           .Where(g => g.Count() == 1)
                           .Select(g => g.First())
                           .ToArray();

編集：同じ比較器を使用した、おそらくより効率的なバージョンは次のとおりです。

IEqualityComparer<string[]> comparer = new IgnoreOrderComparer();
String[][] uniques = arrays.Where(a1 =>
    !arrays.Any(a2 => a1 != a2 && comparer.Equals(a1, a2)))
                           .ToArray();

Answer 2

まず、配列として、行0と行2は重複していません。それらは同じ要素のセットを持っています。ただし、これらの種類の行を削除したいだけの場合は、次のようにすることができます。

string[][] GetNonDuplicates(string[][] jagged)
{
  //not a hashset, but a dictionary. A value of false means that the row 
  //is not duplicate, a value of true means that at least one dulicate was found
  Dictionary<string[], bool> dict = 
          new Dictionary<string[], bool>(new RowEqualityComparer());

  foreach(string[] row in jagged)
  {
    //if a duplicate is found - using the hash and the compare method
    if (dict.ContainsKey(row)) 
    {
       dict[row] = true;  //set value to true
    }
    else
    {
      dict.Add(row, false);  //first time we see this row, add it
    }
  }

  //just pop out all the keys which have a value of false
  string[][] result = dict.Where(item => !item.Value)
                          .Select(item => item.Key)
                          .ToArray();
  return result;
}

...
string[][] jagged = new []{new []{"A","B"} , 
                           new []{"C","D","E"}, 
                           new []{"B", "A"},
                           new []{"E","A"}};

string[][] nonDuplicates = GetNonDuplicates(jagged);

ここRowEqualityComparerで：

class RowEqualityComparer : IEqualityComparer<string[]>
{
    public bool Equals(string[] first, string[] second)
    {
        // different legths - different rows
        if (first.Length != second.Length)
          return false;

        //we need to copy the arrays because Array.Sort 
        //will change the original rows
        var flist = first.ToList();
        flist.Sort();
        var slist = second.ToList();
        slist.Sort();

        //loop and compare one by one
        for (int i=0; i < flist.Count; i++)
        {
            if (flist[i]!=slist[i])
              return false;
        }
        return true;
    }

    public int GetHashCode(string[] row)
    {
       //I have no idea what I'm doing, just some generic hash code calculation
       if (row.Length == 0)
         return 0;
       int hash = row[0].GetHashCode();
       for (int i = 1; i < row.Length; i++)
         hash ^= row[i].GetHashCode();
       return hash;
    }

}

Answer 3

アルゴリズムの解決策に関する限り、私は

1. 行を並べ替えます（2つの異なる行を区別する限り、任意の並べ替えメトリックを使用できます）。
2. 隣接する行が同一でない行を選択します。

これを行うと、 O（m * n * lg（n））で要件を完了することができるはずです。 ここで、mは行の長さ、nは行の数です。

値のセットが等しいことを意味する場合、各行のセルを並べ替えて、行のリストを並べ替えることができます。これにより、O（n * m * lg（m）+ m * n * lg（n））になります。

Answer 4

次のように各行のハッシュを計算します。

[ 
 ["A","B"] , // hash of this row :10 as example 
 ["C","D","E"], // hash of this row  : 20
 ["B", "A"], // hash of this row would be 10 as well
 ["E","A"] 
]

これらはすべて文字列であるため、ハッシュ値を計算して行ごとにハッシュを作成できます。

HashSetを使用する方法は次のとおりです。行ごとにハッシュセットを作成し、1行おきに差を見つけます。差が空の場合、それらは同じです。

交差が空でない場合、その行は一意ではないため、交差を使用することもできます。