0

假设我有一个像这样的二维数组：

[ [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，所以会分开

4

2 回答 2

2

这可能不是形成不相交数组的最有效方法，但它确实产生了所需的结果。通过矛盾很容易证明它有效。

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]]
于 2018-11-11T17:42:38.937 回答
0

如果我明白你的要求，也许你可以分组：

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]]

如果结果大小为 1 或更少，请随意.unshift [0]。

于 2018-11-11T12:54:07.127 回答