How to use set intersection or union on 2D array in ruby?

Question

Say I have a 2D array like so:

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

How can I use intersection or union of those arros above to get the result of:

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

To explain the above:

1. The reason for [0, 1, 4] is because 0 is connected to 1 and 4
2. The reason for [2,3] is because 2 is only connected to 3

How can we do this using set intersection or union? I'm pretty its possible.

Code

My current implementation is actually creating Node and looking for neighbours:

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

The above implementation will output the expected result as above, but not for most other cases.

Update

For case [1, 2], [2, 3]

The output should be [[0], [1,2,3]]

This is because of the range in the array is from 0 to 3.

So because 0 doesn't exist in the array, it will be separate

Answer 1

If I understand what you are asking for, maybe you can group:

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

In case of astr = [ [0, 1], [1, 3], [3, 4], [2, 5], [5, 0] ], it returns

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

In case of astr = [ [1, 2], [2, 3] ], it returns

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

Feel free to .unshift [0] in case result size is 1 or less.

Answer 2

This is perhaps not the most efficient way of forming the disjoint arrays, but it does produce the desired result. The proof that it works is easily established by contradiction.

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

I’ve used sets instead of arrays to speed the union and intersection calculations.

The steps can be illustrated by including some puts statements.

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)

prints the following.

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