Show only the combinations of two permutated arrays that have a sum less than or equal to target num-CodePudding

I have two arrays: teams = [1,2,3] and drivers = [4,5,6]. Using permutations I have managed to show all combinations of the two arrays, but have managed to define what number of values I'd like to use from each array. So from 'Teams' I have used 1 value and 'Drivers' I have used two. I would like to only show the combinations where the sum is less than or equal to 10 and remove any duplicates.

    teams = [1,2,3]
    drivers = [4,5,6]
    team = teams.permutation(1).to_a
    driver = drivers.permutation(2).to_a
    array = team.product(driver)
    target = 11

This is successfully outputting all combinations of the two arrays using 1 number from teams and 2 from drivers as follows:

[[1], [4, 5]], [[1], [4, 6]], [[1], [5, 4]], [[1], [5, 6]], [[1], [6, 4]], [[1], [6, 5]], [[2], [4, 5]], etc...

To only show values less than or equal to 10 my expected outcome would be: [[1], [4, 5]], [[1], [5, 4]],

and then no duplicates would leave me with just: [[1], [4, 5]]

I have tried adding the below line of code but am getting an undefined method `<=' error:

@array = array[0].product(*array[1..-1]).select { |a| a.reduce(: ) <= target }

I have also tried this with no luck:

result = array.combination(1).select{|combi| combi.sum <= target}

@array = result

I'm guessing it's something to do with the permutation?

CodePudding user response：

Here's an approach

target = 11

res = array.select {|i| i.map(&:sum).sum <= target}.compact
==> [[[1], [4, 5]], [[1], [4, 6]], [[1], [5, 4]], [[1], [6, 4]], 
    [[2], [4, 5]], [[2], [5, 4]]]

Getting the unique items

res.map {|i| i.flatten.sort}.uniq.map {|i| [i.slice(0..0), i.slice(1..2)]}
==> [[[1], [4, 5]], [[1], [4, 6]], [[2], [4, 5]]]

CodePudding user response：

teams = [1,2,3]
drivers = [2,5,4,5,6,4,5,7]
max_driver_sum = 10

As a first step let's partition drivers between values that are repeated and those that are not.

counts = drivers.tally
  #=> {2=>1, 5=>3, 4=>2, 6=>1, 7=>1}

dup_drivers, uniq_drivers = counts.partition { |_d,n| n > 1 }
                                  .map { |arr| arr.map(&:first) }
  #=> [[5, 4], [2, 6, 7]]

Therefore,

dup_drivers
  #=> [5, 4]

uniq_drivers    
  #=> [2, 6, 7]

See Enumerable#tally and Enumerable#partition.

Here,

counts.partition { |_d,n| n > 1 } 
 #=> [[[5, 3], [4, 2]], [[2, 1], [6, 1], [7, 1]]]

First compute the unique combinations in which the two drivers are equal:

dup_drivers = dup_drivers.select { |d| d <= max_driver_sum/2 }
  #=> [5, 4]

In this example all drivers d that appeared as duplicates satisfied the requirement that d d <= max_driver_sum.

dup_combos = teams.product(dup_drivers).map { |t,d| [t,[d,d]] }
  #=> [[1, [5, 5]], [1, [4, 4]],
  #    [2, [5, 5]], [2, [4, 4]],
  #    [3, [5, 5]], [3, [4, 4]]]

See Array#product. Here,

teams.product(dup_drivers)
  #=> [[1, 5], [1, 4], [2, 5], [2, 4], [3, 5], [3, 4]]

We now turn to the construction of the combinations involving pairs of uniq driver values:

all_uniq = uniq_drivers   dup_drivers
  #=> [2, 6, 7, 5, 4]

teams.product(
  all_uniq.combination(2).select { |d1,d2| d1 d2 <= max_driver_sum }
)
  #=> [[1, [2, 6]], [1, [2, 7]], [1, [2, 5]], [1, [2, 4]], [1, [6, 4]], [1, [5, 4]],
  #    [2, [2, 6]], [2, [2, 7]], [2, [2, 5]], [2, [2, 4]], [2, [6, 4]], [2, [5, 4]],
  #    [3, [2, 6]], [3, [2, 7]], [3, [2, 5]], [3, [2, 4]], [3, [6, 4]], [3, [5, 4]]]

The steps are as follows.

enum = all_uniq.combination(2)
  #=> #<Enumerator: [2, 6, 7, 5, 4]:combination(2)>

We can see the values that will be generated by converting it to an array:

enum.to_a
  #=> [[2, 6], [2, 7], [2, 5], [2, 4],
  #    [6, 7], [6, 5], [6, 4],
  #    [7, 5], [7, 4],
  #    [5, 4]]

See Array#combination.

Contining,

arr = enum.select { |d1,d2| d1 d2 < max_driver_sum }
  #=> [[2, 6], [2, 7], [2, 5], [2, 4], [5, 4]]

uniq_combos = teams.product(arr)
  #=> (return value above)

The final step is to combine the two groups of combinations:

arr = dup_combos   uniq_combos
  #=> [[1, [5, 5]], [1, [4, 4]], [2, [5, 5]], [2, [4, 4]], [3, [5, 5]],
  #    [3, [4, 4]], [1, [2, 6]], [1, [2, 7]], [1, [2, 5]], [1, [2, 4]],
  #    [1, [6, 4]], [1, [5, 4]], [2, [2, 6]], [2, [2, 7]], [2, [2, 5]],
  #    [2, [2, 4]], [2, [6, 4]], [2, [5, 4]], [3, [2, 6]], [3, [2, 7]],
  #    [3, [2, 5]], [3, [2, 4]], [3, [6, 4]], [3, [5, 4]]]

Sorted, this result is as follows.

arr.sort
  #=> [[1, [2, 4]], [1, [2, 5]], [1, [2, 6]], [1, [2, 7]], [1, [4, 4]],
  #    [1, [5, 4]], [1, [5, 5]], [1, [6, 4]],
  #    [2, [2, 4]], [2, [2, 5]], [2, [2, 6]], [2, [2, 7]], [2, [4, 4]],
  #    [2, [5, 4]], [2, [5, 5]], [2, [6, 4]],
  #    [3, [2, 4]], [3, [2, 5]], [3, [2, 6]], [3, [2, 7]], [3, [4, 4]],
  #    [3, [5, 4]], [3, [5, 5]], [3, [6, 4]]]

Notice that Array#uniq was not used in the foregoing. If desired, one could of course substitute out some of the variables above.