주어진 숫자 쌍에서 연결되지 않은 숫자 찾기

Question

주어진 쌍의 숫자 목록에서 연결 해제 번호를 찾는 알고리즘이 있습니까? 예를 들어 {(1,2), (2,3), (3,4)} 쌍 (1,3)과 (2,4)는 한 번도 쌍을 이루지 못했습니다.

Answer 1

당신은 다음과 같이이 작업을 수행 할 수있는 모든 쌍 이상

1. 반복 처리를하고 세트에 나타나는 모든 숫자의 집합을 구축 할 수 있습니다.
2. 숫자의 가능한 모든 쌍을 구성하여 결과를 다른 집합에 저장합니다.
3. 원래 목록에서 모든 쌍을 반복하고 모든 쌍의 집합에서 찾은 각각을 제거하십시오.
4. 이제 원래 세트에 표시되지 않은 모든 쌍이 남았습니다.

물론 이것은 원래 세트의 값 쌍에만 관심이 있다고 가정합니다. 예를 들어, 쌍 (1, 5)도 귀하의 예가 아닙니다. 어느 쪽도 아니었다 (고양이, 개).

이것은 시간 O (n)에서 실행됩니다. 여기서 n은 원래 쌍의 쌍에 표시된 숫자의 수입니다.

희망이 도움이됩니다. LINQ와 사실상 대칭 트릭 촬영을 이용하여

Answer 2

(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); 
} 

은