CODEWITHSUNDEEP
rubyarrays
jasonjasonjason
jasonjasonjason

Reputation: 25

How can I combine elements of an array that have a common element?

I want to take an array of number pairs:

[[2, 3], [2, 15], [3, 15], [7, 8], [8, 7], [11, 15]]

and if two of these number pairs have a number in common, combine them and display the unique values, ultimately creating this array:

[[2, 3, 15, 11], [7, 8]]

Order of the numbers in the output array is not important. What would be the best solution?

Upvotes: 2

Views: 215

Answers (4)

pguardiario
pguardiario

Reputation: 54984

It's really just another mapping and sorting problem,:

array = [[2, 3], [2, 15], [3, 2], [3, 15], [7, 8], [8, 7], [11, 15], [15, 2], [15, 3], [15, 11]]
array.map{|a| array.each{|x| a |= x if (x & a).any?}; a.sort}.uniq
#=> [[2, 3, 11, 15], [7, 8]]

Upvotes: 1

Cary Swoveland
Cary Swoveland

Reputation: 110675

A recursive solution:

def doit(a,b)
  return a unless b
  h = b.group_by {|e| (a[-1] & e).any?}
  h[true] ? a[-1] |= h[true].flatten : a << h[false].pop
  doit(a, h[false])
end

arr = [[2, 3], [2, 15], [3, 2], [3, 15], [16, 21], [7, 8], [8, 7], \
       [21, 44], [11, 15], [15, 2], [15, 3], [15, 11], [8, 9]]
doit([arr.pop], arr) # => [[8, 9, 7], [15, 11, 2, 3], [21, 44, 16]]

Upvotes: 0

sawa
sawa

Reputation: 168081

The answer was corrected following Howard's comment.

[[2, 3], [2, 15], [3, 2], [3, 15], [7, 8], [8, 7], [11, 15], [15, 2], [15, 3], [15, 11]]
.each_with_object([]) do |e1, a|
  a.select{|e2| (e1 & e2).any?}.each{|e2| e1.concat(a.delete(e2))}
  e1.uniq!
  a.push(e1)
end
# => [[8, 7], [15, 11, 3, 2]]

Upvotes: 3

Nir Alfasi
Nir Alfasi

Reputation: 53525

Not as elegant as @sawa's solution - but works for all the cases:

def includes? item, groups
  groups.each{|sub|
    return true if sub.include?(item)
  }
  false
end

def add groups, match, item
  groups.each{|sub|
    if sub.include?(match)
      sub << item
      sub.uniq!
      return
    end
  }
end

def iterate arr  
  groups = []
  grp = []
      arr.each do |a,b|
        grp = [a,b] if grp.empty?
        if includes? a, groups
          add groups, a, b
        elsif includes? b, groups
          add groups, b, a
        else
          groups << [a,b]
        end
      end
  groups
end

arr = [[2, 3], [2, 15], [3, 2], [3, 15], [7, 8], [8, 7], [11, 15], [15, 2], [15, 3], [15, 11]]
p iterate(arr)

OUTPUT

[[2, 3, 15, 11], [7, 8]]

Upvotes: 0

Related Questions