Ruby, equally distribute elements and interleave/merge multiple arrays

Question

I have multiple arrays with unknown element count like

a = []
a << [:a, :c, :e]
a << [:b, :f, :g, :h, :i, :j]
a << [:d]

result should be something like ~ (I don't really care details due rounding etc)

r = [:b, :a, :f, :g, :d, :c, :h, :i, :e, :j]

This is how I think it could be done

First we need to expand/distribute equally elements in each array to same length, so we get something like

a << [nil, :a, nil, :c, nil, :e]
a << [:b, :f, :g, :h, :i, :j]
a << [nil, nil, :d, nil, nil]

Next we interleave them as typically would do

r = a.shift
a.each { |e| r = r.zip(e) }
r = r.flatten.compact

My current problem is how to equally (as much as it's possible) distribute those elements across array? There could be one array with 4 elements and other with 5, but probably biggest should go first.

Of course would be nice to see if there's any other way to achieve this :)

Answer 1

I would use a sort to do this, based on element index postion, divided by size of array, plus some offset based on array id, to keep things consistent (if you don't need consistency, you could use a small random offset instead).

a = [:a,:b]
b = [:c]
c = [:d,:e,:f]
d = [:g:,:h,:i,:j]

def sort_pos array, id
  (1..array.size).map { |i| (i - 0.5 + id/1000.0)/(array.size + 1e-6) }
end

# Combine all the arrays with their sort index, assigning ids to each array for consistency.
# Depending on how you receive these arrays, this structure can be built up programatically, 
# as long as you add an array plus its sort index numbers at the same time
combined = (a + b + c + d).zip( sort_pos(a, 1) +  sort_pos(b, 2) +  sort_pos(c, 3) +  sort_pos(d, 4) )


# Extract the values from the original arrays in their new order
combined.sort_by { |zipped| zipped[1] }.map { |zipped| zipped[0] }

=> [:g, :d, :a, :h, :e, :i, :b, :f, :j, :c]

There might be a cleaner way of doing this in Ruby . . . but I think the end result is what you are after - an "even" mix of multiple arrays.

If you only care about even-ness of mix from a statistical perspective (i.e. over time it is "fair"), you could just do this:

(a+b+c+d).shuffle

=> [:g, :b, :i, :c, :a, :h, :e, :j, :f, :d]