CODEWITHSUNDEEP
arraysrubyalgorithm
max pleaner
max pleaner

Reputation: 26788

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? 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%

Upvotes: 1

Views: 115

Answers (1)

max pleaner
max pleaner

Reputation: 26788

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
      elem_to_push = (priority_run_result ? arr2 : arr1).shift
      # if arr2 is empty, push from arr1 instead 
      results << elem_to_push || 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 / a1.length.to_f
end
puts result.mean
# => is 0%

Upvotes: 1

Related Questions