CODEWITHSUNDEEP
ruby
6ft Dan
6ft Dan

Reputation: 2445

Merging inner arrays of indices if they contain the same content

I'm generating an array of grouped indexes. The indexes are points within an array that meet my grouping requirements. For example I'm grouping indexes from a grid where things are horizontally "close" to each other. This is kind of what I'll be working with.

[[0,1,2],[3],[4,5],[5,6],[7,8],[8,9]]

I would like to merge by common indexes. So the result should look like.

[[0,1,2],[3],[4,5,6],[7,8,9]]

It feels like it should be an inject :+ on pairs if any inner items match. But I don't see the Ruby way to do this.

Upvotes: 0

Views: 73

Answers (4)

Cary Swoveland
Cary Swoveland

Reputation: 110725

The solutions so far seem overly-complicated to me. I suggest this (assuming each element of arr is non-empty and contains only integers):

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

arr.each_with_object([]) do |a,b|
  if b.any? && b.last.last == a.first
    b[-1] += a[1..-1]
  else
    b << a
  end
end
  #=> [[0, 1, 2], [3], [4, 5, 6], [7, 8, 9, 10, 11], [12, 13, 14]]

You could alternatively do it by stepping through arr with an enumerator:

enum = arr.each
b = [enum.next]
loop do
  a = enum.next
  if b.last.last == a.first
    b[-1] += a[1..-1]
  else
    b << a
  end
end
b

Upvotes: 1

Hew Wolff
Hew Wolff

Reputation: 1509

x.sort.inject([]) do |y, new|
  (((y.last || []) & new).length > 0) ? y[0..-2].push(y.last | new) : y.push(new)
end.map(&:sort)

Upvotes: 1

SteveTurczyn
SteveTurczyn

Reputation: 36860

Someone might find a more compact method, but this works...

array = [[0,1,2],[3],[4,5],[5,6],[7,8],[8,9]]
(0...array.length).each do |a|
  (a+1...array.length).each do |b|
    unless array[a].to_a  & array[b].to_a == []
      array[a].push(array[b]).flatten!.uniq!.sort!
      array.delete_at(b)
      b -= 1
    end
  end
end

p array
=> [[0, 1, 2], [3], [4, 5, 6], [7, 8, 9]]

Upvotes: 1

DreadPirateShawn
DreadPirateShawn

Reputation: 8412

Knowing Ruby, there's probably a more concise way to do this, but this should give you what you want:

foo = [[0,1,2],[3],[4,5],[5,6],[7,8],[8,9]]

foo.inject([]) {|result,element|
  if (result and existing = result.find_index{|a| !(element & [*a]).empty?})
    tmp = result[existing]
    result.delete_at(existing)
    result << (tmp | element).sort
  else
    result << element
  end
}.sort

Output:

=> [[0, 1, 2], [3], [4, 5, 6], [7, 8, 9]]

Logic:

For each element in the original array, check the newly-built array-so-far (result) for any entry which contains any of the same numbers as the next element using array intersection -- !(element & [*a]).empty? ...

  • if found, remove said entry from the result, union it with the new element from the original array -- (tmp | element) -- then add it back to the result
  • if not found, simply concatenate the element from the original array to the result

Upvotes: 1

Related Questions