c# - 与えられた数のペアから対になっていない数を見つける

Question

ペアになっている数の特定のリストからペアになっていない数を見つけるアルゴリズムはありますか。たとえば、{（1,2）、（2,3）、（3,4）}では、ペア（1,3）と（2,4） ）ペアリングされたことはありません。

Answer 1

これは次のように行うことができます。

1. すべてのペアを繰り返し、セットに表示されるすべての数字のセットを作成します。
2. 可能なすべての数値のペアを作成し、結果を別のセットに格納します。
3. 元のリストからすべてのペアを繰り返し処理し、すべてのペアのセットから見つけた各ペアを削除します。
4. これで、元のセットに表示されなかったすべてのペアが残ります。

もちろん、これは、元のセットの値のペアのみを気にすることを前提としています。たとえば、ペア（1、5）もあなたの例にはありませんでした。どちらも（猫、犬）ではありませんでした。

これは時間O（n ²）で実行されます。ここで、nは元のペアのセットで表される数値の数です。

お役に立てれば！

Answer 2

LINQと、（1,3）と（3,1）が同一であるという事実を利用した対称トリックを使用して、2番目の数値が最初の数値よりも大きい場合を無視します。

public static IEnumerable<Tuple<int, int>> GetUnpairedNumbers(IEnumerable<Tuple<int, int>> existingPairs ) {
    var uniqueNumbers = existingPairs.SelectMany(p => new[] {p.Item1, p.Item2}).Distinct().ToList();
    var isUsed = uniqueNumbers.ToDictionary(n => n, n => uniqueNumbers.Where(inner => n < inner).ToDictionary(inner => inner, inner => false));

    foreach(var currentPair in existingPairs) {
        isUsed[currentPair.Item1][currentPair.Item2] = true;
    }

    return isUsed.Keys.SelectMany(n => isUsed[n].Where(kvp => !kvp.Value).Select(kvp => Tuple.Create(n, kvp.Key)));
}
public static void Main(string[] args) {
    var unpairedNumbers = GetUnpairedNumbers(new[] { P(1, 2), P(2, 3), P(3, 4) });
}

private static Tuple<int, int> P(int a, int b) {
    return Tuple.Create(a, b);
}