max pleaner max pleaner - 2 months ago 7
Ruby Question

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

Say I have two arrays:

Arr1 = ["1-a", "1-b", "1-c"]
Arr2 = ["2-a", "2-b", "2-c"]


I know how to combine them into an array, preserving their order:

Arr1.zip(Arr2).flatten(1)
# => ["1-a", "2-a", "1-b", "2-b", "1-c", "2-c"]


In this example I'd consider Arr1 to be 'prioritized' over Arr2 because "1-a" appears before "2-a" and "1-c" appears before "2-c".

Here's what happens if Arr2 is 'prioritized':

Arr2.zip(Arr1).flatten(1)
# => ["2-a", "1-a", "2-b", "1-b", "2-c", "1-c"]


With these examples, 'priority' is a binary state. But what if I wanted to use a decimal? Something like this:

# Arr1's order is 50% as important as Arr2's order

Arr1_priority = 0.5
results = []
Arr2.each_with_index do |element, index|
results << element
if (1.to_f - (index.to_f / results.length.to_f)) <= Arr1_priority
# only push Arr1 item if the iterator is 50% done
results << Arr1.shift
end
end

results
# => ["2-a", "2-b", "1-a", "2-c", "1-b"]


With this implementation,Arr1 will only start to be included in the results after 50% of Arr2's elements are added.

But I'm not confident this gets the job done as well as possible.
Does
.5
priority mean really mean that Arr1 only starts appearing halfway through? My hunch is no. It'd be better if Arr1's elements gradually started to appear.

Right now this graph describes what's happening in this attempt to achieve "50% priority"

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

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


But the result array will only be 25% Arr1. It should be 50%. This is what I want to happen:

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%

Answer

Here's what I wrote

class Array

  # helper method to help with testing
  def mean
    map(&:to_f).reduce(&:+) / length.to_f
  end

  # target is another array
  # priority is a number between 0 and 1
  #   if 0, then target will not be merged in at all
  #   if 1, then the result will be ~50% composed of target
  # returns array with the same length as self
  # Note that the result will not contain all of self.concat(target)

  def priority_merge(priority, target)
    # clone the arrays to avoid side-effects
    arr1, arr2 = [self, target].map(&:clone)
    # get the original length to determine the results length
    arr1_len = arr1.length.to_f
    # convert priority to float
    priority = priority.to_f
    # initialize a results set
    results = []
    # populate the results set
    arr1_len.to_i.times do |arr1_idx|
      # determine the percentage completed through iteration
      pct_iterated = arr1_idx.to_f / arr1_len.to_f
      # calculate per-run likelihood of favoring target
      per_run_priority = pct_iterated * priority
      # conclusively determine which array this iteration will pull from
      num_true_cases = (100.0 * per_run_priority).to_i
      cases = num_true_cases.times.map { true }.concat((100 - num_true_cases).times.map { false })
      priority_run_result = cases.sample
      # push from arr2 if the priority run result is true, otherwise push from arr1
      results << (priority_run_result ? arr2 : arr1).shift
    end
    results
  end
end

and testing it

a1 = 50.times.map { 1 }
a2 = 50.times.map { 2 }

puts "MERGE CASE 1"
result = 50.times.map do
  result = a1.priority_merge(1.0, a2)
  result.select { |item| item == 2 }.count.to_f / a1.length.to_f
end
puts result.mean
# => is around 50%

puts "MERGE CASE 0.5"
result = 50.times.map do
  result = a1.priority_merge(0.5, a2)
  result.select { |item| item == 2 }.count.to_f / a1.length.to_f
end
puts result.mean
# => is around 25%
puts "MERGE CASE 0"
result = 50.times.map do
  result = a1.priority_merge(0.0, a2)
  result.select { |item| item == 2 }.count
end
puts result.mean
# => is 0%
Comments