查找數組中所有數字的排列總和爲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，這在紅寶石V2.4首次亮相。對於早期版本，請使用c.reduce(:0) == tot。

在comb_to_perms中，第一個uniq只是刪除重複項。第二個uniq帶有一個塊，除去可以通過旋轉任何其他p-1元素獲得的所有p.size元素（數組）。例如，

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