Finding all permutations of numbers plucked from an array which sum to 16

Question

I would like to find all the permutations of plucking 3, 4 or 5 numbers from [2,3,4,5,6,7,8], repeats allowed, such that their sum is 16. So [8,5,3], [8,3,5] and [4,3,3,3,3] are valid permutations. Also circular permutations should be removed so [3,3,3,3,4] wouldn't also be added to the answer. I can do this in Ruby without allowing repeats like this:

d = [2,3,4,5,6,7,8]
number_of_divisions = [3,4,5]
number_of_divisions.collect do |n|
  d.permutation(n).to_a.reject do |p|
    p[0..n].inject(0) { |sum,x| sum + x } != 16
  end
end

How could I allow repeats so that [3,3,3,3,4] was included?

[`Array#repeated_permutation`](https://ruby-doc.org/core/Array.html#method-i-repeated_permutation). — Aleksei Matiushkin, Jul 05 '17 at 13:45

Aleksei Matiushkin · Accepted Answer · 2017-07-06T05:13:53.580

5

For all permutations, including duplicates, one might use Array#repeated_permutation:

d = [2,3,4,5,6,7,8]
number_of_divisions = [3,4,5]
number_of_divisions.flat_map do |n|
  d.repeated_permutation(n).reject do |p| # no need `to_a`
    p.inject(:+) != 16
  end
end

or, even better with Array#repeated_combination:

number_of_divisions.flat_map do |n|
  d.repeated_combination(n).reject do |p| # no need `to_a`
    p.inject(:+) != 16
  end
end

edited Jul 06 '17 at 05:13

answered Jul 05 '17 at 13:48

Aleksei Matiushkin

119,336
10
100
160

You can avoid using `map(&:sort)` and `uniq` by using `repeated_combination` instead. – Sagar Pandya Jul 05 '17 at 15:24
`repeated_permutation` and `repeated_combination` are just the ticket! Thanks guys – thenapking Jul 05 '17 at 15:27
@iceツ indeed. Updated an answer. – Aleksei Matiushkin Jul 05 '17 at 15:31
1

On second thoughts... The OP is clearly interested in permutations (where position matters i.e. `[8,3,5]` and `[8,5,3]` are valid) but your answer converts to combinations i.e. `[8,3,5]` and `[8,5,3]` are considered the same. So it may be best to leave your original answer except remove the `map` and `uniq`. – Sagar Pandya Jul 05 '17 at 16:43
With `d = [2,3,4,5]; number_of_divisions = [3]` and the desired sum `12` (rather than `16`), both snippets return `[[2, 5, 5], [3, 4, 5], [4, 4, 4]]`, which is missing `[3,5,4]`. In #1 the problem is that `sort` followed by `uniq` removes too much, and in #2, `repeated_combination` will return arrays `a` such that if `i < j`, `d[i]` will always precede `d[j]` in the elements returned by `repeated_combination` that contain both of those elements of `d`. If, for example, `d` is sorted, all of the combinations will be sorted. – Cary Swoveland Jul 05 '17 at 19:49

Cary Swoveland · Answer 2 · 2017-07-05T20:21:14.230

There are far fewer repeated combinations than repeated permutations, so let's find the repeated combinations that sum to the given value, then permute each of those. Moreover, by applying uniq at each of several steps of the calculation we can significantly reduce the number of repeated combinations and permutations considered.

Code

require 'set'

def rep_perms_for_all(arr, n_arr, tot)
  n_arr.flat_map { |n| rep_perms_for_1(arr, n, tot) }
end

def rep_perms_for_1(arr, n, tot)
   rep_combs_to_rep_perms(rep_combs_for_1(arr, n, tot)).uniq
end

def rep_combs_for_1(arr, n, tot)
  arr.repeated_combination(n).uniq.select { |c| c.sum == tot }
end

def rep_combs_to_rep_perms(combs)
  combs.flat_map { |c| comb_to_perms(c) }.uniq
end

def comb_to_perms(comb)
  comb.permutation(comb.size).uniq.uniq do |p| 
    p.size.times.with_object(Set.new) { |i,s| s << p.rotate(i) } 
  end
end

Examples

rep_perms_for_all([2,3,4,5], [3], 12)
  #=> [[2, 5, 5], [3, 4, 5], [3, 5, 4], [4, 4, 4]]
rep_perms_for_all([2,3,4,5,6,7,8], [3,4,5], 16).size
  #=> 93
rep_perms_for_all([2,3,4,5,6,7,8], [3,4,5], 16)
  #=> [[2, 6, 8], [2, 8, 6], [2, 7, 7], [3, 5, 8], [3, 8, 5], [3, 6, 7],
  #    [3, 7, 6], [4, 4, 8], [4, 5, 7], [4, 7, 5], [4, 6, 6], [5, 5, 6],
  #    [2, 2, 4, 8], [2, 2, 8, 4], [2, 4, 2, 8], [2, 2, 5, 7], [2, 2, 7, 5],
  #    [2, 5, 2, 7], [2, 2, 6, 6], [2, 6, 2, 6], [2, 3, 3, 8], [2, 3, 8, 3], 
  #    ...
  #    [3, 3, 3, 7], [3, 3, 4, 6], [3, 3, 6, 4], [3, 4, 3, 6], [3, 3, 5, 5], 
  #    [3, 5, 3, 5], [3, 4, 4, 5], [3, 4, 5, 4], [3, 5, 4, 4], [4, 4, 4, 4],
  #    ...
  #    [2, 2, 4, 5, 3], [2, 2, 5, 3, 4], [2, 2, 5, 4, 3], [2, 3, 2, 4, 5],
  #    [2, 3, 2, 5, 4], [2, 3, 4, 2, 5], [2, 3, 5, 2, 4], [2, 4, 2, 5, 3],
  #    ...
  #    [2, 5, 3, 3, 3], [2, 3, 3, 4, 4], [2, 3, 4, 3, 4], [2, 3, 4, 4, 3],
  #    [2, 4, 3, 3, 4], [2, 4, 3, 4, 3], [2, 4, 4, 3, 3], [3, 3, 3, 3, 4]]

Explanation

rep_combs_for_1 uses the method Enumerable#sum, which made its debut in Ruby v2.4. For earlier versions, use c.reduce(:0) == tot.

In comb_to_perms, the first uniq simply removes duplicates. The second uniq, with a block, removes all but one of the p.size elements (arrays) that can be obtained by rotating any of the other p-1 elements. For example,

p = [1,2,3]
p.size.times.with_object(Set.new) { |i,s| s << p.rotate(i) }
  #=> #<Set: {[1, 2, 3], [2, 3, 1], [3, 1, 2]}>

This is very interesting. I had wondered if the previous solutions were including too few results but couldn't spot one that was missing. — thenapking, Jul 06 '17 at 19:34

Finding all permutations of numbers plucked from an array which sum to 16

2 Answers2