Эта проблема известна как разделение набора в эквивалентность . Классы , с входным файлом, списком парных эквиваленте. Это может быть решено с помощью неразмерной структуры .

Менее абстрактный пример - это E.g. Разделение слов на группы синонимов приведенные пары синонимов:

large big
big great
great vast
small little
little tiny

становится:

large big great vast
small little tiny

RUBY-раствор

Разнообразие набор недоступен в библиотеке Ruby Standard, поэтому я эмулирую его с помощью Ruby хеш ( известный в другом месте как «ассоциативный массив», «словарь», «карта»).

#!/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(" ")}

Использование

Это ожидает имена файлов в командной строке или данные на STDIN:

$ 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

SWUR

, возможно, более подходит для этого сайта.

Здесь я использую немного разную реализацию дископринации: каждое подмножество представлено одним из его элементов («лидер»). Это делает операцию Union медленнее, но легче реализовать с простыми типами данных 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

он работает, когда остаток Teake_Minute / 13 равен нулю. Так что в этом случае это будет каждые 13 минут, примерно. Это означает, что когда минуты получают сброс (от 59 до 0) он начинается. Таким образом, например * / 13 всегда будет работать 0 13 26 39 52.