C#で重複している配列同士をまとめたい

Question

前提・実現したいこと

配列同士比べて、１つでも重複している要素があれば、配列同士をまとめるという事をしたいです。

該当のソースコード

HashSet<int> A = new HashSet<int> { 1, 2, 6 };
HashSet<int> B = new HashSet<int> { 6, 8 };
HashSet<int> C = new HashSet<int> { 9, 5 };
HashSet<int> D = new HashSet<int> { 1, 3, 8 };
HashSet<int> E = new HashSet<int> { 7, 9 };
HashSet<int> F = new HashSet<int> { 4 };

/*欲しい結果
[配列A[1,2,3,6,8],配列B[4],配列C[5,7,9]]
のように、ダブりなく組み分けしたい。
ちなみに配列の中の数字はは毎回ランダムに変わります。
*/

試したこと

HashSetで重複しない配列を作れるというのはわかったのですが、
判定して結合していくループをどう作ったら良いのかが全くわかりません。
ご教授いただければ幸いです。

新たに試してみたソースコード

    //ランダムな数字を持ったハッシュセット
    HashSet<int> A = new HashSet<int> { 1, 2, 6 };
    HashSet<int> B = new HashSet<int> { 6, 8 };
    HashSet<int> C = new HashSet<int> { 9, 5 };
    HashSet<int> D = new HashSet<int> { 1, 3, 8 };
    HashSet<int> E = new HashSet<int> { 7, 9 };
    HashSet<int> F = new HashSet<int> { 4 };

    //上記のハッシュセットをまとめたリスト
    List<HashSet<int>> listA;

　　//最終でダブりのないハッシュセットをもつリスト
    List<HashSet<int>> listB;
　　//補佐のリスト
    List<HashSet<int>> listC;
    //listBに追加するか否かのフラグ
    private bool NA = false;

    void Start () {
    //初期化
        listA = new List<HashSet<int>> { A, B, C, D, E, F };
        listB = new List<HashSet<int>> { };
        listC = new List<HashSet<int>> { };
    }

    public void Union()
    {
　　//listAの中身を総当たりして、要素が被ってたら一番最初のハッシュセットにまとめる
        for (int i = 0; i < listA.Count; i++)
        {
            for (int j = 1; j < listA.Count; j++)
            {
                if (listA[i].Overlaps(listA[j]))
                {
                    listA[i].UnionWith(listA[j]);
                }
            }
            NA = true;
            if(listC.Count!=0){
                foreach(var k in listC){
                    //すでに要素が被ってるものがある場合はlistBに追加しない
                    if (listA[i].Overlaps(k)){
                        NA = false;
                    }
                 }
            }
            if(NA==true){listB.Add(listA[i]);}
            listC.Add(listA[i]);
        }

        print("最終チェック"+listB.Count);
        foreach (var l in listB)
        {
            print(l + "の中の数字は");
            foreach (var m in l)
            {
                print(m);
            }
        }
    }
    

Comments

[pepperleaf]

HashSet.Contains() と HashSet.RemoveWhere() を使えば、出来そう。参考まで (時間が取れれば、確認してみたい)

[uecky]

ありがとうございます！ 
恥ずかしながら、プログラムがかなりの初心者で、HashSet.Contains() と HashSet.RemoveWhere() を使う方法が考えてみたもののわからずじまいでした。 
overlapというのとUnionWithというのを使ってとりあえずやってみました。新たに試してみたソースコードというところに載せております。
とりあえずの結果が取れたっぽいのだけど、このソースだと例外でうまいこといかない場合があるのでは、、、と不安です。
間違っていたり、もう少し賢いやり方があればあればご指摘いただけると幸いです。。

[papinianus]

欲しいものについて詳しい条件を伺いたいのですが、[1,3][3,5,][5,7]の3つは1つになってよいのでしょうか。つまり、1つめと3つめは互いに共通要素はないのですが、2つ目がいることによって連結される？それとも[1,3,5]と[3,5,7]の2つでしょうか？

[uecky]

はい、2つ目がいることによって連結される　が正しいです！
SNSのつながりみたいな感じで、繋がってたらそのグラフを１グループにするイメージです。
 [1,3][3,5,][5,7]の3つは1つにしたいです。 サンプルの例だと、Fだけ4は誰とも被ってないので１グループとなります。

Answer 1

こんにちは。
なんだか面白そうな問題だったので回答してみます。

(下のコードにはバグがみつかったので、さらに下に追記してます。↓↓↓)

自分はIEqualityComparerを悪用してさっぱり実現してみました。たぶんこれが一番短いと思います(?)

{
    var data = new[] { A, B, C, D, E, F };

    var result = data
        .GroupBy(x => x, new HashSetOverlapEqualityComparer<int>())
        .Select(x => x.Aggregate(Enumerable.Empty<int>(), (set, set2) => set.Union(set2)));
}
class HashSetOverlapEqualityComparer<T> : IEqualityComparer<HashSet<T>>
{
    public bool Equals(HashSet<T> x, HashSet<T> y) => x.Overlaps(y);
    public int GetHashCode(HashSet<T> obj) => 0;
}

HashSet<T>のOverlapsメソッドによる重複検知を「イコールである」と判定してしまうようなIEqualityComparerを実装することで、GroupByのグルーピング機能に丸投げしています。
大分斜め上なハックですけど、おそらく可読性とメンテナンス性という意味では優れている方なんじゃないかなーと思います。
要素の順序などは特に考慮していないので、必要なら好きにOrderByするなりしてください。

foreach (var set in result)
    Console.WriteLine(string.Join(", ", set.OrderBy(x => x)));

/* output:
1, 2, 3, 6, 8
5, 7, 9
4
*/

---

追記
はわわ……上の実装にはバグがありました……OrderByは一度取ったキーが以後更新されないので「2つ目以降のSetとのみ重複している場合」のマージ処理が行われません……
筋肉(再帰)で解決！！！

public static class UnionExtension
{
    public static IEnumerable<IEnumerable<T>> GroupUnion<T>(this IEnumerable<IEnumerable<T>> source)
    {
        var result = source
            .GroupBy(x => x, new OverlapsEqualityComparer<T>())
            .Select(x => x.Aggregate((set, set2) => set.Union(set2)))
            .ToArray();
        return (result.Length == source.Count()) ? result : result.GroupUnion();
    }
    class OverlapsEqualityComparer<T> : IEqualityComparer<IEnumerable<T>>
    {
        public bool Equals(IEnumerable<T> x, IEnumerable<T> y) => x.Intersect(y).Count() != 0;
        public int GetHashCode(IEnumerable<T> obj) => 0;
    }
}

// つかう
var data = new[] { A, B, C, D, E, F };
var result = data.GroupUnion();

Answer 2

逆に素直に実装してみましたがどうでしょうか

HashSet<int> A = new HashSet<int> { 1, 2 };
HashSet<int> B = new HashSet<int> { 3, 4 };
HashSet<int> C = new HashSet<int> { 2, 3 };
HashSet<int> D = new HashSet<int> { 5, 6, 8 };
HashSet<int> E = new HashSet<int> { 7, 9 };
HashSet<int> F = new HashSet<int> { 4 };

var allList = new List<HashSet<int>> { A, B, C, D, E, F, };

for (int i = 0; i < allList.Count; i++)
{
    for (int j = 0; j < allList.Count; j++)
    {
        if (i != j && allList[i].Where(d => allList[j].Contains(d)).Any())
        {
            allList[j].ToList().ForEach(d => allList[i].Add(d));
            allList[j].Clear();
        }
    }
}

//result
var result = allList.Where(d => d.Any());

//print
foreach (var set in result)
{
    System.Diagnostics.Debug.WriteLine(string.Join(",", set));
}

最初は、こんな感じで

for (int i = 0; i < allList.Count - 1; i++)
{
    for (int j = i + 1; j < allList.Count; j++)
    {

一方向だけ見てたら
A {1,2} B {2,3} C {3,4} はよくても
A {1,2} B {3,4} C {2,3} がダメで
結局両方向になりました。

追記：
インデクサはやっぱり嫌なので、ごり押しで短くしました

var allList = new List<HashSet<int>> { A, B, C, D, E, F, };
            
allList.ForEach(outer => allList.ForEach(inner => {
    if (outer != inner && outer.Where(d => inner.Contains(d)).Any()) {
        inner.ToList().ForEach(d => outer.Add(d));
        inner.Clear();
    }
}));

//result
var result = allList.Where(d => d.Any());

Answer 3

書換えてみました。
他の方ほど、シンプルでありませんが、一応。

List<HashSet<int>> hashList = new List<HashSet<int>>() {A, B, C, D, E, F };	// 全リスト
List<HashSet<int>> orgList = new List<HashSet<int>>();
bool exitFlag = false;
while (!exitFlag) {		// 重複データがある間、ループする
	orgList = hashList;
	hashList = new List<HashSet<int>>();
	exitFlag = true;
	// orgList --> hashList へコピーしながら、検査
	foreach (var item in orgList) {
		bool found = false;
		foreach (var newitem in hashList) {
			if (item.Overlaps(newitem)) {		// 重複データがあるか
				newitem.UnionWith(item);		// あれば、マージ
				found = true;
				break;
			}
		}
		if (!found)	hashList.Add(item);		// 重複が見つからないので、追加
		exitFlag &= !found;		// 重複があったか?
	}
}

-------- 最初のコード ----------------------------
以下のコードではどうでしょうか?

List<HashSet<int>> hashList = new List<HashSet<int>>() {A, B, C, D, E, F };	// 全リスト

HashSet<int> allSet = new HashSet<int>();	// 全てのデータを格納する
foreach (var hash in hashList) {
	hash.ExceptWith(allSet);	// 重複データを除く
	~~foreach (var item in hash) {	// 確認済みデータに追加
		allSet.Add(item);
	}~~
	allSet.UnionWith(hash);	// これで良かった。
}

もう少しスマートにできるかと思ったのですが、、、。

Comments

[uecky]

す、すごい！！！！！めちゃめちゃ短くなってる！！！！！
初質問で緊張していたのですが、ここで質問して本当によかったです！
ご回答ありがとうございます！

[uecky]

上記コード試してみました！
全てのHashSetのintの中身が被らないように、
新たにHashSet<int> を生成してくださったのですね。

書き方がややこしかったのですが、
実現したい形式がちょっと違っておりました。
[ハッシュセットA[1,2,3,6,8] , ハッシュセットB[4], ハッシュセットC[5,7,9]]
のように、共有している数同士を結合し、ダブりなく組み分けした状態にしたかったのです。
こちらもスマートなやり方でなんとか解決できないでしょうか・・・(; _ ;)

[uecky]

元の自分で試したソースと比べて、こういう風にループを組めばいいのか！！！とすごく勉強になりました。こういう出力がすぐできるように、勉強頑張りたいと思います。ありがとうございます！

[pepperleaf]

少しは役に立ったようで良かったです。
他の方の方法も確認したいのですが、只今、その余裕無しの状態。
(暑さ+その他で)

Answer 4

Linq大好きLinqerの私としてはループを使わず書きたかったのですが、ちょっと骨ですね。

static void Main(string[] args)
{
    HashSet<int> A = new HashSet<int> { 1, 2, 6 };
    HashSet<int> B = new HashSet<int> { 6, 8 };
    HashSet<int> C = new HashSet<int> { 9, 5 };
    HashSet<int> D = new HashSet<int> { 1, 3, 8 };
    HashSet<int> E = new HashSet<int> { 7, 9 };
    HashSet<int> F = new HashSet<int> { 4 };

    var hashQueue = new Queue<HashSet<int>>(new[] { A, B, C, D, E, F });

    var result = new List<HashSet<int>>();

    while(hashQueue.Count > 0)
    {
        HashSet<int> current = hashQueue.Dequeue();

        var count = hashQueue.Count;
        for (int i = 0; count > i; i++)
        {
            var target = hashQueue.Dequeue();

            if(current.Where(c => target.Contains(c)).Any())
            {
                current = new HashSet<int>(current.Union(target).OrderBy(idx => idx));
            }
            else
            {
                hashQueue.Enqueue(target);
            }
        }
        result.Add(current);
    }

    result.ForEach(r => Console.WriteLine(r.Select(i => i.ToString())
        .Aggregate((a,b) => a + "," + b)));
}

Comments

[papinianus]

こういうことを考えたのですが、やっぱり2段階ループするしかないですよね。2回目のループをforにして、queueが残っていても終了させる点が大変参考になりました。