CODEWITHSUNDEEP
rubyarrayssorting
ddinchev
ddinchev

Reputation: 34673

How do I merge the items of two arrays in Ruby based on the order of a third array?

I have three arrays.

My main list contains a mix of different entities which are verified in a DB: 

ab = ["a:555", "b:222", "a:333", "b:777", "a:777", "a:999", "b:111"]

I have two more arrays of a and b entities separated, but ordered (some are missing):

# notice that some of the items from the initial list are missing, but the order is preserved!
a = [{id}, "a:777", "a:999"]
b = ["b:222", "b:111"]

What is an efficient way to merge a and b in array c preserving the order in ab where the items are present? My expected result from the procedure is:

c = ["a:555", "b:222", "a:777", "a:999", "b:111"]

I'm a Ruby newbie and everything I came up with is utterly ugly.

Edit:

I did know it matters, and would be confusing, but a and b are complex objects (AR) that represent the strings in ab. To clarify with my code:

ab = ["a:555", "b:222", "a:333", "b:777", "a:777", "a:999", "b:111"]
a = [{:id => 555}, {:id => 777}, {:id => 999}]
b = [{:id => 222}, {:id => 111}]
c = []

ab.each { |item|
parts = item.split(":")
if parts[0] == "a"
  if a[0][:id].to_s() == parts[1]
    c << a.shift()
  end
else
  if b[0][:id].to_s() == parts[1]
    c << b.shift()  
  end
end

}

puts c

Upvotes: 0

Views: 180

Answers (2)

dbenhur
dbenhur

Reputation: 20408

If the value's id are not distinct between a and b, one can do this

c = (
  a.map { |e| [ "a:#{e[:id]}", e ] } +
  b.map { |e| [ "b:#{e[:id]}", e ] }
).
sort_by { |e| ab.index(e.first) }.
map(&:last)

Since you now state they are distinct and that there's a method on the objects that produces your ab key, this is simpler:

c = (a + b).sort_by { |e| ab.index(e.get_ab_string) }

ab.index is an O(N) operation on ab, so it escalates what's ordinarily a NlnN sort to N^2. To bring the whole solution back into O(NlnN) runtime, one can pre-calaculate the indexes of ab into a hash (an O(N) operation allowing O(1) lookups in the sort_by):

ab_idx = Hash[ ab.map.with_index { |e,i| [e, i] } ]
c = (a + b).sort_by { |e| ab_idx(e.get_ab_string) }

Upvotes: 3

the Tin Man
the Tin Man

Reputation: 160551

Here's the basis for how to sort an array into the same order as another. Starting with two arrays:

ary_a = %w[one four three two]
ary_b = [1, 4, 3, 2]

Merge them, sort, then retrieve the one we wanted sorted:

ary_a.zip(ary_b).sort_by{ |a, b| b }.map(&:first)
=> ["one", "two", "three", "four"]

If we want to reverse the order:

ary_a.zip(ary_b).sort_by{ |a, b| -b }.map(&:first)
=> ["four", "three", "two", "one"]

or:

ary_a.zip(ary_b).sort_by{ |a, b| b }.map(&:first).reverse
=> ["four", "three", "two", "one"]

If there are three arrays and two need to be ordered in concert with the third:

ary_c = %w[a-one a-four a-three a-two]
ary_a.zip(ary_c).zip(ary_b).sort_by{ |a, b| b }.map(&:first)
=> [["one", "a-one"], ["two", "a-two"], ["three", "a-three"], ["four", "a-four"]]

Getting the arrays into the form needed prior to merging and sorting is the problem. Once you have those, and they have equal numbers of elements, it's a pretty simple pattern.

Upvotes: 0

Related Questions