Combine arrays and preserve ordering - but prioritize one array's ordering over another

Question

I have two arrays and I want to combine them both in a manner similar to this:

arr1 = "1a, 1b, 1c"
arr2 = "2a, 2b, 2c"
arr1.zip(arr2).flatten(1)
# => [1a, 2a, 1b, 2b, 3b, 3c]

That is, put each arr2 element right after the arr1 element sharing an index.

Since arr1 elements come before their arr2 counterparts, arr1 can be considered 'prioritized' in this example.

The prioritization could be switched by instead using arr2.zip(arr1).

In both these cases, the priority has a binary state. Either arr1 elements always come before their arr2 counterparts or vice versa.

This can be visualized in a graph:

y axis: percentage of added nodes that are Arr1
x axis: percent completion of Arr2 iteration

   100% |                     
        |           
   75%  |                
        |
   50%  | X     X    X    X    X
        |
   25%  |       
        |
    0%  |     
        ------------------------- 
           0%  25%  50%  75%  100%

What if I wanted the graph's mean to be 50% and to have it increase in a linear fashion like so:

y axis: percentage of added nodes that are Arr1
x axis: percent completion of Arr2 iteration

   100% |                     X
        |           
   75%  |                X
        |
   50%  |           X
        |
   25%  |       X
        |
    0%  |  X        
        ------------------------- 
           0%  25%  50%  75%  100%

I ended up writing this code:

  # Merges two arrays, ordering the results based on a 'priority' between 0 and 1
  # If the priority is 0, then the results will include 100% original array
  # If the priority is 1, then the results will contain 50% original array
  # For example:
  #   input: 0.5, [1,2,3], [4,5,6]
  #   step 1: 1:0 odds in favor of array 1
  #   step 2: 1:1 tie
  #   step 3: 1:0 odds in favor of array 2
  #   possible results: [1, 2, 6] and [1, 5, 6] are equally likely
  #
  # @param priority_amt [Float] a number between 0 and 1.
  #   Represents the percentage of the result array that comes from
  #   array_to_be_merged
  # @param original_array [Array] will be at least 50% of the result
  # @param array_to_be_merged [Array]
  # @return [Array]
  def priority_merge(priority_amt, original_array, array_to_be_merged)
    original_array = original_array.clone
    array_to_be_merged = array_to_be_merged.clone
    original_array_original_length = original_array.length.to_f
    priority_amt = priority_amt.to_f
    results = []
    swapped_priority = nil
    original_array.each_index do |index|
      results << original_array.shift
      percent_completed_through_iteration = 2 * (index.to_f / original_array_original_length)
      calculated_priority_for_run = 2 * priority_amt * percent_completed_through_iteration
      if calculated_priority_for_run > 0.5
        if swapped_priority.nil?
          original_array, array_to_be_merged = array_to_be_merged, original_array
        end
        swapped_priority = 1.0 - calculated_priority_for_run
        calculated_priority_for_run = swapped_priority
      end
      priority_case_did_pass = priority_run_result(calculated_priority_for_run)
      results << array_to_be_merged.shift if priority_case_did_pass
    end
    return results
  end

  # @param success_pct [Float] the percentage of times this method will return true
  #   if called with the same argument
  # @return [Boolean]
  def priority_run_result(success_pct)
    rand(100) < (success_pct * 100.0)
  end

Here's a usage example:

Arr1 =  'a'.upto('z').map { |c| "1-#{c}" }
Arr2 = Arr1.map { |str| str.gsub("1", "2") }
result = priority_merge(0.5, Arr2, Arr1)
print "#{result}\n"

# => ["2-a", "2-b", "2-c", "2-d", "2-e", "2-f", "2-g", "1-a", "2-h", "1-b", "2-i", "1-c", "1-d", "2-j", "1-e", "2-k", "1-f", "1-g", "1-h"]

# Verifying that the result is 50% composed of the second array:

pct_is_arr1 = result.select { |str| str.include?("1") }.count.to_f / result.count.to_f
puts pct_is_arr1
# => 0.42105263157894735

Running it again shows pct_is_arr1 == 0.5714285714285714, so it's clearly staying close to 50% as expected.

Since I don't have a lot of practice with algorithms, I'm wondering how this looks and if my logic makes sense.

Answer 1

I admit I haven't gone through this in great detail, but just glancing at the code, it looks like there's just too much going on.

You already mention the #zip method. Since it's close to your desired functionality, why not use it? As far as I can tell you want to do something like this:

def priority_merge(weighting, arr_a, arr_b)
  arr_a.zip(arr_b).map.with_index do |(a, b), i|
    position = i.fdiv(arr_a.count)
    position * weighting.to_f <= rand ? a : b
  end
end

priority_merge(0, [1, 2, 3, 4], [5, 6, 7, 8]) #=> [1, 2, 3, 4]

priority_merge(1, [1, 2, 3, 4], [5, 6, 7, 8]) #=> [1, 2, 7, 8]
priority_merge(1, [1, 2, 3, 4], [5, 6, 7, 8]) #=> [1, 6, 3, 8]
priority_merge(1, [1, 2, 3, 4], [5, 6, 7, 8]) #=> [1, 6, 7, 8]

It probably doesn't completely match your current code (not sure I 100% understood what you were going for to begin with), but it's just to show a vastly simpler approach to choosing between two candidate elements.

Answer 2

I suppose that you want to sort the concatenation of the arrays (the question is really fuzzy in that sense).

You need to think in reverse, take an empty result array and fill it on purpose from one array or the other:

result = []
labels = []
until a.empty? && b.empty?
  if labels.empty? || b.empty?
    labels << :a
    result << a.unshift
  elsif a.empty?
    labels << :b
    result << b.unshift
  else
    ratio = labels.count(:b).fdiv(labels.count(:a))
    # decide depending on current ratio whether to get from a or b
  end
end

now results will have your elements, and moreover labels will mark where those come from.