有限制的重复排列

Question

我正在尝试生成 15 个数组中某些值的所有可能组合，这些组合加起来为 50。

$a = [3, 4, 1, 2, 5]
print $a.repeated_permutation(15).to_a

在这种情况下，

[2,2,2,2,4,4,4,4,4,4,4,4,4,3,3]
[2,2,2,4,2,4,4,4,4,4,4,4,4,3,3]
[2,2,4,2,2,4,4,4,4,4,4,4,4,3,3]

都是可能的答案。

经过一些调查，我意识到执行此操作的代码有点难以理解，但如果它可能对其他人有帮助，我会留下这个问题。

关于我正在做的事情的一些参考，欧拉项目，问题 114。这非常困难，所以我试图只解决一个案例，我的 50-space-长网格是仅填充 3 个单位长的块。块必须至少由一个空格分隔，所以我将块数为 4。这（经过一些调整，我已经省略了，因为这已经很混乱了）允许 12 个块加上三个单个空格，或者最多十五个元素。

Answer 1

接近

我认为递归是解决问题的方法，您的递归方法如下所示：

def recurse(n,t)

哪里

n是需要的元素个数；和
t 是要求的总数。

如果我们让 @arr 是给定的整数数组，recurse(n,t) returns 来自 @arr 的 n 个元素的所有排列的数组总和 t.

假设

我假设 @arr 的元素是非负整数，按大小排序，但如果它包含负整数，则可以轻松修改该方法（尽管性能会受到影响）。不失一般性，我们可以假设 @arr 的元素是唯一的，按大小递增排序。

代码

def recurse(n,t)
  if n == 1
    @arr.include?(t) ? [[t]] : nil
  else
    @arr.each_with_object([]) do |i,a|
      break if i > t # as elements of @arr are non-decreasing
      if (ret = recurse(n-1,t-i))
        ret.each { |b| a << [i,*b] }
      end
    end
  end
end

例子

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

recurse(1,4)
  #=> [[4]]
recurse(2,6)
  #=> [[1, 5], [2, 4], [3, 3], [4, 2], [5, 1]] 
recurse(3,10)
  #=> [[1, 4, 5], [1, 5, 4], [2, 3, 5], [2, 4, 4], [2, 5, 3],
  #    [3, 2, 5], [3, 3, 4], [3, 4, 3], [3, 5, 2], [4, 1, 5],
  #    [4, 2, 4], [4, 3, 3], [4, 4, 2], [4, 5, 1], [5, 1, 4],
  #    [5, 2, 3], [5, 3, 2], [5, 4, 1]] 
recurse(3,50)
  #=> []

改善

但是，我们可以做得更好，首先计算所有组合，然后计算每个组合的排列。

def combo_recurse(n,t,last=0)
    ndx = @arr.index { |i| i >= last }
    return nil if ndx.nil?
    arr_above = @arr[ndx..-1] 
  if n == 1
    arr_above.include?(t) ? [[t]] : nil
  else
    arr_above.each_with_object([]) do |i,a|
      break if i > t # as elements of @arr are non-decreasing
      if (ret = combo_recurse(n-1,t-i,i))
        ret.each { |b| a << [i,*b] }
      end
    end
  end
end

combo_recurse(1,4)
  #=> [[4]]
combo_recurse(2,6)
  #=> [[1, 5], [2, 4], [3, 3]] 
combo_recurse(3,10)
  #=> [[1, 4, 5], [2, 3, 5], [2, 4, 4], [3, 3, 4]] 
combo_recurse(3,50)
  #=> [] 
combo_recurse(15,50).size
  #=> 132 
combo_recurse(15,50).first(5)
  #=> [[1, 1, 1, 1, 1, 1, 4, 5, 5, 5, 5, 5, 5, 5, 5],
  #    [1, 1, 1, 1, 1, 2, 3, 5, 5, 5, 5, 5, 5, 5, 5],
  #    [1, 1, 1, 1, 1, 2, 4, 4, 5, 5, 5, 5, 5, 5, 5],
  #    [1, 1, 1, 1, 1, 3, 3, 4, 5, 5, 5, 5, 5, 5, 5],
  #    [1, 1, 1, 1, 1, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5]]

然后我们可以根据组合计算排列：

combo_recurse(2,6).flat_map { |a| a.permutation(a.size).to_a }.uniq
  #=> [[1, 5], [5, 1], [2, 4], [4, 2], [3, 3]] 
combo_recurse(3,10).flat_map { |a| a.permutation(a.size).to_a }.uniq
  #=> [[1, 4, 5], [1, 5, 4], [4, 1, 5], [4, 5, 1], [5, 1, 4],
  #    [5, 4, 1], [2, 3, 5], [2, 5, 3], [3, 2, 5], [3, 5, 2],
  #    [5, 2, 3], [5, 3, 2], [2, 4, 4], [4, 2, 4], [4, 4, 2],
  #    [3, 3, 4], [3, 4, 3], [4, 3, 3]]

我们可以估算出 (15,50) 的排列数（由于未应用 uniq，它会有点高）：

def factorial(n)
  (1..n).reduce :*
end

Math.log10 combo_recurse(15,50).reduce(1) { |t,a| t*factorial(a.size) }
  #=> 1599.3779486682888

也就是结果有1600位左右。您将运行放在哪个平台上？

有限制的重复排列

a repeated permutation with limitations

ruby

arrays

permutation