Возьмите массив пар строк и верните массив массивов всех связанных элементов.

Question

У меня есть массив пар имен, таких как:

[
  ['alison', 'jason'],
  ['alison', 'chris'],
  ['john', 'bill'],
  ['bill', 'alex'],
  ['alex', 'jack']
]

, и я пытаюсь написать метод, который может принять это и вернуть

[
  ['alison', 'jason', 'chris'],
  ['john', 'bill', 'alex', 'jack']
]

лучше, чемO (N ^ 2) время.Моя попытка была такой:

def teams(arr)
  pair_hash = {}
  arr.each do |pair|
    if pair_hash[pair[0]].nil?
      pair_hash[pair[0]] = [pair[1]]
    else
      pair_hash[pair[0]].push(pair[1])
    end
  end
  teams = []
  pair_hash.map do |leader, team|
    teams.push(find_teammates(pair_hash, leader, team))
  end
  teams
end

def find_teammates(hash, leader, team)
  result = [leader]
  team.each do |member|
    if hash[member].nil?
      result += [member]
    else
      result += find_teammates(hash, member, hash[member])
    end
  end
  result
end

, но у этого решения есть дополнительные команды в результате, и каждое решение, которое я могу придумать, включает в себя очень низкую сложность времени.Если у вас есть идеи, как решить эту проблему, не прибегая к грубому форсированию всех пар, я хотел бы знать.

Answer 1

Вам повезло, что disjoint-set - моя любимая структура данных.Вот краткая и быстрая реализация:

pairs = [['alison', 'jason'], ['alison', 'chris'], ['john', 'bill'], ['bill', 'alex'], ['alex', 'jack'], ['steve', 'alex']]

parents = {}

pairs.each do |x, y|
  # each person starts as their own set, and their own representative
  parents[x] ||= x
  parents[y] ||= y

  # find representative of x set
  x_parent = parents[x]
  loop do
    break if parents[x_parent] == x_parent
    x_parent = parents[x_parent]
  end

  # find representative of y set
  y_parent = parents[y]
  loop do
    break if parents[y_parent] == y_parent
    y_parent = parents[y_parent]
  end

  # union by changing y's representative
  parents[y_parent] = x_parent
  # path compression to speed up later unions
  parents[x] = x_parent
  parents[y] = x_parent
end

# group by set representative (some paths might not be compressed)
groups = parents.each_key.group_by do |person|
  parent = parents[person]
  loop do
    break if parents[parent] == parent
    parent = parents[parent]
  end
  parent
end

p groups.values
[["alison", "jason", "chris"], ["john", "bill", "alex", "jack", "steve"]]

Это примерно O (N + M), где N - количество людей, а M - количество пар.Обратите внимание на повторение, например, при поиске представителя набора.Алгоритм выглядит намного чище, если вы определите правильный класс для выполнения поиска.

Также мое сжатие пути не идеально, вы можете ускорить его еще больше, если поместите сжатие в репрезентативный поиск, а не всоюз.