Python에서는 입력 파일을 인수로 시작합니다.

import sys

res = []  # list of lists
for line in open(sys.argv[1]):
    try:
        x, y = line.split()  # split on space
    except ValueError:
        line = line.rstrip()
        x, y = line.split(',')  # retry with comma
    for l in res:
        if x in l:
            if y not in l:
                l.append(y)
            break
    else:
        res.append([x, y])

for line in res:
    print ' '.join(line)

테스트에서는 if y not in l:동일한 값을 두 번 추가하는 것을 건너뜁니다. 이것이 필요한지 또는 소스에 그러한 예외가 있는지 확실하지 않습니다. 테스트를 생략하고 항상 실행할 수 있습니다 l.append(y).

코드는 먼저 공백으로 분할을 시도한 다음 쉼표를 다시 시도합니다. 이는 쉼표로 구분된 줄에 공백이 없다고 가정합니다(즉 공백이 아님 A, B).

중첩 for루프는 (내가 아는 한) 파이썬의 특징을 사용합니다. 즉, break 문이 아니라 else루프가 Exhaustion 을 통해 끝날 때만 실행됩니다 . for즉 x, 찾을 수 없는 경우 해당 쌍이 새 목록으로 추가됩니다 res.

이론

이 문제는컬렉션을 나누다입력하다동등 클래스, 입력 파일에는 쌍별 동등성이 나열됩니다. 이 문제는 다음 도구를 사용하여 해결할 수 있습니다.서로소 집합데이터 구조.

덜 추상적인 예는 예를 들어 동의어 쌍이 주어진 동의어 그룹으로 단어를 분할하는 것입니다.

large big
big great
great vast
small little
little tiny

이 되다:

large big great vast
small little tiny

루비 용액

서로소 집합은 Ruby 표준 라이브러리에서 사용할 수 없으므로 Ruby를 사용하여 이를 에뮬레이트했습니다 Hash(다른 곳에서는 "연관 배열", "사전", "맵"이라고도 함).

#!/usr/bin/env ruby
# new elements end up in "singleton subsets"
subsets = Hash.new { |subsets, element| subsets[element] = [element] }
ARGF.each do |line|
  x, y = line.scan(/[^\s,]/)
  # these two emulate disjoint-set's "find" operation
  x_set = subsets[x]
  y_set = subsets[y]
  # and this loop implements disjoint-set's "union"
  y_set.each do |element, _|
    subsets[element] = x_set << element
  end unless x_set == y_set
end
puts subsets.values.uniq.map{|set| set.join(" ")}

용법

이를 위해서는 명령줄에 파일 이름이 필요하거나 표준 입력에 데이터가 필요합니다.

$ ruby so-162730.rb input.txt
A B C D E
F G

$ ruby so-162730.rb < input.txt
A B C D E
F G

이상한 솔루션

어쩌면 이 사이트에 더 적합할 수도 있습니다.

여기서는 서로소 집합의 약간 다른 구현을 사용합니다. 각 하위 집합은 해당 요소 중 하나("리더")로 표시됩니다. 이로 인해 결합 작업이 느려지지만 awk의 간단한 데이터 유형을 사용하여 구현하기가 더 쉽습니다.

{
  union(find($1), find($2));
}

END {
  format_subsets();
  for(i in subsets)
    print subsets[i];
}

function find(element) {
  if (!leaders[element])
    leaders[element] = element;
  return leaders[element];
}

function union(leader_1, leader_2) {
  for(i in leaders)
    if (leaders[i] == leader_2)
      leaders[i] = leader_1;
}

function format_subsets() {
  for(element in leaders) {
    leader = leaders[element]
    subsets[leader] = (subset = subsets[leader]) ? (subset OFS element) : element;
  }
}

용법

$ awk -f so-162730.awk < input.txt
A B C D E
F G

또는 공백이나 쉼표로 구분된 입력의 경우:

$ awk -f so-162730.awk -F '[[:space:]]+|,' input.txt
A B C D E
F G