Как использовать набор пересечения или объединения на 2D-массив в рубине?

Question

Скажем, у меня есть двумерный массив, например:

[ [0, 1], [2, 3], [0, 4] ]

Как я могу использовать пересечение или объединение этих арросов выше, чтобы получить результат:

[[0, 1, 4], [2, 3]]

Чтобы объяснить выше:

1. Причина [0, 1, 4] в том, что 0 связан с 1, а 4
2. Причина [2,3] в том, что 2 подключен только к 3

Как мы можем сделать это, используя пересечение или объединение множеств? Я довольно, это возможно.

Код

Моя текущая реализация на самом деле создает Node и ищет соседей:

def connected_neighbors(astronaut)
  graph, to_return, node_a, node_b = {}, [], nil, nil

  astronaut.each do |city_a, city_b|
    node_a, node_b = (graph[city_a] || Node.new(city_a)), (graph[city_b] || Node.new(city_b))
    node_a.connect node_b
    graph[city_a] = node_a unless graph[city_a]
  end

  graph.each do |key,_|
    node = graph[key]
    to_return << [node.key, node.neighbors.collect(&:key)].flatten
  end
  to_return
end

Приведенная выше реализация выдаст ожидаемый результат, как указано выше, но не для большинства других случаев.

Обновление

Для дела [1, 2], [2, 3]

Вывод должен быть [[0], [1,2,3]]

Это из-за диапазона в массиве от 0 до 3.

Так как 0 не существует в массиве, он будет отдельным

Answer 1

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

arr = [[0,2], [1,3], [4,6], [7,9], [6,8], [5,7], [2,4], [3,7], [10,11]]

require 'set'

sets = arr.map(&:to_set)
  #=> [#<Set: {0, 2}>, #<Set: {1, 3}>, #<Set: {4, 6}>, #<Set: {7, 9}>, #<Set: {6, 8}>,
  #    #<Set: {5, 7}>, #<Set: {2, 4}>, #<Set: {3, 7}>, #<Set: {10, 11}>]

loop do
  break if sets.size == 1
  set1, set2 = sets.combination(2).find { |set1,set2| (set1 & set2).any? }
  break if set1.nil?
  set1.replace(set1 | set2)
  sets.delete(set2)
end

sets.map(&:to_a)
  #=> [[0, 2, 4, 6, 8], [1, 3, 7, 9, 5], [10, 11]]

Я использовал наборы вместо массивов для ускорения вычислений объединения и пересечения.

Этапы могут быть проиллюстрированы включением некоторых puts операторов.

sets = arr.map(&:to_set)

loop do
  puts "(#{sets.size} sets at beginning of loop"
  puts "  #{sets}"
  puts "  break as sets.size == 1" if sets.size == 1
  break if sets.size == 1
  set1, set2 = sets.combination(2).find { |set1,set2| (set1 & set2).any? }
  if set1.nil?
    puts "    After find, set1 = nil, so break" if set1.nil?
  else
    puts "    After find, set1 = #{set1}"
    puts "                set2 = #{set2}"
  end
  break if set1.nil?
  set1.replace(set1 | set2)
  sets.delete(set2)
  puts "  sets after set1 |= set2 and sets.delete(set2)"
  puts "  #{sets}" 
end

sets.map(&:to_a)

печатает следующее.

(9) sets at beginning of loop
  [#<Set: {0, 2}>, #<Set: {1, 3}>, #<Set: {4, 6}>, #<Set: {7, 9}>, #<Set: {6, 8}>,
   #<Set: {5, 7}>, #<Set: {2, 4}>, #<Set: {3, 7}>, #<Set: {10, 11}>]
    After find, set1 = #<Set: {0, 2}>
                set2 = #<Set: {2, 4}>
 sets after set1 |= set2 and sets.delete(set2)
   [#<Set: {0, 2, 4}>, #<Set: {1, 3}>, #<Set: {4, 6}>, #<Set: {7, 9}>,
    #<Set: {6, 8}>, #<Set: {5, 7}>, #<Set: {3, 7}>, #<Set: {10, 11}>]

(8) sets at beginning of loop
  [#<Set: {0, 2, 4}>, #<Set: {1, 3}>, #<Set: {4, 6}>, #<Set: {7, 9}>,
   #<Set: {6, 8}>, #<Set: {5, 7}>, #<Set: {3, 7}>, #<Set: {10, 11}>]
    After find, set1 = #<Set: {0, 2, 4}>
                set2 = #<Set: {4, 6}>
 sets after set1 |= set2 and sets.delete(set2)
   [#<Set: {0, 2, 4, 6}>, #<Set: {1, 3}>, #<Set: {7, 9}>, #<Set: {6, 8}>,
    #<Set: {5, 7}>, #<Set: {3, 7}>, #<Set: {10, 11}>]

(7) sets at beginning of loop
  [#<Set: {0, 2, 4, 6}>, #<Set: {1, 3}>, #<Set: {7, 9}>, #<Set: {6, 8}>,
   #<Set: {5, 7}>, #<Set: {3, 7}>, #<Set: {10, 11}>]
    After find, set1 = #<Set: {0, 2, 4, 6}>
                set2 = #<Set: {6, 8}>
 sets after set1 |= set2 and sets.delete(set2)
   [#<Set: {0, 2, 4, 6, 8}>, #<Set: {1, 3}>, #<Set: {7, 9}>, #<Set: {5, 7}>,
    #<Set: {3, 7}>, #<Set: {10, 11}>]

(6) sets at beginning of loop
  [#<Set: {0, 2, 4, 6, 8}>, #<Set: {1, 3}>, #<Set: {7, 9}>, #<Set: {5, 7}>,
   #<Set: {3, 7}>, #<Set: {10, 11}>]
    After find, set1 = #<Set: {1, 3}>
                set2 = #<Set: {3, 7}>
 sets after set1 |= set2 and sets.delete(set2)
   [#<Set: {0, 2, 4, 6, 8}>, #<Set: {1, 3, 7}>, #<Set: {7, 9}>, #<Set: {5, 7}>,
    #<Set: {10, 11}>]

(5) sets at beginning of loop
  [#<Set: {0, 2, 4, 6, 8}>, #<Set: {1, 3, 7}>, #<Set: {7, 9}>, #<Set: {5, 7}>,
   #<Set: {10, 11}>]
    After find, set1 = #<Set: {1, 3, 7}>
                set2 = #<Set: {7, 9}>
 sets after set1 |= set2 and sets.delete(set2)
   [#<Set: {0, 2, 4, 6, 8}>, #<Set: {1, 3, 7, 9}>, #<Set: {5, 7}>, #<Set: {10, 11}>]

(4) sets at beginning of loop
  [#<Set: {0, 2, 4, 6, 8}>, #<Set: {1, 3, 7, 9}>, #<Set: {5, 7}>, #<Set: {10, 11}>]
    After find, set1 = #<Set: {1, 3, 7, 9}>
                set2 = #<Set: {5, 7}>
 sets after set1 |= set2 and sets.delete(set2)
   [#<Set: {0, 2, 4, 6, 8}>, #<Set: {1, 3, 7, 9, 5}>, #<Set: {10, 11}>]

(3) sets at beginning of loop
  [#<Set: {0, 2, 4, 6, 8}>, #<Set: {1, 3, 7, 9, 5}>, #<Set: {10, 11}>]
    After find, set1 = nil, so break

sets.map(&:to_a)
  #=> [[0, 2, 4, 6, 8], [1, 3, 7, 9, 5], [10, 11]]

Answer 2

Если я понимаю, что вы просите, возможно, вы можете сгруппировать:

astr = [ [0, 1], [1, 3], [3, 4], [2, 5], [5, 6] ]

mapp = astr.map.with_index do |_, i|
  res = []
  astr[i..-1].each do |e|
    if res.empty?
      res = res && e 
    else
      res = res + e unless (res & e).empty?
    end
  end
  res.uniq
end.slice_when { |j, k| j.size <= k.size }.map(&:first)


mapp #=> [[0, 1, 3, 4], [2, 5, 6]]

В случае astr = [ [0, 1], [1, 3], [3, 4], [2, 5], [5, 0] ] возвращается

#=> [[0, 1, 3, 4, 5], [2, 5, 0]]

В случае astr = [ [1, 2], [2, 3] ] возвращается

#=> [[1, 2, 3]]

Не стесняйтесь .unshift [0], если размер результата равен 1 или меньше.