3

C＃では、私は持っています

class Pair{

  int val1;
  int val2;
}

次のようなソースからのペアのリストがあります:-

List<Pair> sList = new List<Pair>();

   1 | 2
   2 | 3
   1 | 4
   4 | 6

私はそれを次のタイプの構造に変換する必要があります:-

 [1, [2, 3, 4, 6]]  
 [2, [3]]
 [3, [2]]
 [4, [1,6]]
 [6, [4]]

これを行う最善の方法は何ですか(LINQなし)?

4

2 に答える 2

5

を使用ILookup<int, int>しますが、逆の関連付けも含める必要があります。

var result = sList.Union(sList.Select(p => new Pair { val1 = p.val2, val2 = p.val1 }))
                  .ToLookup(p => p.val1, p => p.val2);

これを使用して、Linq なしで同様の結果を得ることができます。

var dict = new Dictionary<int, List<int>>();
foreach(var pair in sList)
{
    if (!dict.ContainsKey(pair.val1))
    {
        dict[pair.val1] = new List<int>();
    }
    if (!dict.ContainsKey(pair.val2))
    {
        dict[pair.val2] = new List<int>();
    }

    dict[pair.val1].Add(pair.val2);
    dict[pair.val2].Add(pair.val1);
}

上記の両方の方法でAdjacency Listが生成されますが、コメントからは、 Connected Component Labelingのようにやりたいことのように思えます 

var groups = new List<HashSet<int>>();
foreach (var p in sList)
{
    var merge = new List<HashSet<int>>();
    foreach(var g in groups)
    {
        if (g.Contains(p.val1) || g.Contains(p.val2))
        {
            merge.Add(g);
        }
    }

    if (merge.Count == 0)
    {
        var h = new HashSet<int>();
        groups.Add(h);
        merge.Add(h);
    }

    merge[0].Add(p.val1);
    merge[0].Add(p.val2);
    for(int i = 1; i < merge.Count; i ++)
    {
        foreach(int v in merge[i])
        {
            merge[0].Add(v);
        }

        groups.Remove(merge[i]);
    }
}

入力が

sList = 
    1 | 2
    4 | 6
    2 | 3
    1 | 4
    9 | 10

これにより、次の出力が生成されます。

groups = 
    [ 1, 2, 3, 4, 6 ]
    [ 9, 10 ]

これを必要な形式に変換するのはそれほど難しくありません。

var dict = new Dictionary<int, List<int>>();
foreach(var g in groups)
{
    foreach(var v in g)
    {
        var list = new List<int>(g);
        list.Remove(g);
        dict.Add(v, list)
    }
}

前の例を使用します。

dict =
    1 | [ 2, 3, 4, 6 ]
    2 | [ 1, 3, 4, 6 ]
    3 | [ 1, 2, 4, 6 ]
    4 | [ 1, 2, 3, 6 ]
    6 | [ 1, 2, 3, 4 ]
    9 | [ 9 ]
    10 | [ 10 ]
于 2013-06-28T00:42:24.943 に答える
1

次のように、LINQ のGroupByメソッドでこれを行うことができます。

var adj = sList
    .GroupBy(p => p.val1)
    .ToDictionary(g => g.Key, g => g.Select(p => p.val2).ToList());

これはグラフの推移閉包を計算しないことに注意してください。つまり、直接リンクのみが存在します。

.NET 4 以降では、独自のクラスTuple<int,int>を作成する代わりに を使用することもできます。Pair

于 2013-06-28T00:39:40.633 に答える