查找从总和为 16 的数组中提取的所有数字排列

Question

我想找出从[2,3,4,5,6,7,8]中取出3、4或5个数字的所有排列，允许重复，使得它们的和为16。所以[ 8,5,3]、[8,3,5] 和 [4,3,3,3,3] 是有效排列。还应删除循环排列，这样 [3,3,3,3,4] 也不会添加到答案中。我可以在 Ruby 中执行此操作，而不允许像这样重复：

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

如何允许重复以便包含 [3,3,3,3,4]？

Answer 1

对于所有排列，包括重复排列，可以使用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

或者 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

Answer 2

与重复排列相比，重复组合要少得多，所以让我们找出总和为给定值的重复组合，然后对每个组合进行排列。此外，通过在计算的几个步骤中的每一步应用 uniq，我们可以显着减少考虑的重复组合和排列的数量。

代码

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

例子

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]]

说明

rep_combs_for_1 使用 Enumerable#sum 方法，该方法在 Ruby v2.4 中首次亮相。对于早期版本，请使用 c.reduce(:0) == tot。

在 comb_to_perms 中，第一个 uniq 只是删除重复项。第二个 uniq，带有一个块，删除除一个 p.size 元素（数组）之外的所有元素，这些元素（数组）可以通过旋转任何其他 p-1 元素获得。例如，

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]}>

查找从总和为 16 的数组中提取的所有数字排列

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

ruby

arrays

circular-permutations