如何在Ruby中使用循環輸出所有可能的組合？

Question

我剛開始學習編程，並試圖編寫一個輸出所有可能組合的函數。到目前爲止，我已經能夠找到所有可能的大小2的組合，但我不確定如何讓代碼開放以處理更大尺寸的組合。某種遞歸會有用嗎？

我知道我可以使用內置的組合方法，但我只是想弄清楚如何從頭開始編寫它。任何意見將不勝感激。謝謝！

def two_combos(input) 
    list = [] 
    for index1 in (0...input.length) 
     for index2 in (0...input.length) 
      if input[index1] != input[index2] 
       if list.include?([input[index2],input[index1]])==false 
        list << [input[index1],input[index2]] 
       end 
      end 
     end 
    end 
    return list 
end 


two_combos(["A","B","C"]) 
#outputs 
=> [["A", "B"], ["A", "C"], ["B", "C"]] 
#Missing 
["A","B","C"] 

Answer 1

該實現是像在二進制計數遞歸：

def combinations(items) 
    return [] unless items.any? 
    prefix = items[0] 
    suffixes = combinations(items[1..-1]) 
    [[prefix]] + suffixes + suffixes.map {|item| [prefix] + item } 
end 

> combinations(%w(a b c)) 
=> [["a"], ["b"], ["c"], ["b", "c"], ["a", "b"], ["a", "c"], ["a", "b", "c"]] 

在每一個階段中，所述組合是一個concate國家：

• 單獨的第一元件
• 的以下元件的組合（元件1..N-1）
• 第一元件具有以下元件的組合組合

Answer 2

這裏是遞歸算法

def combinations(array, size) 
    fail "size is too big" if size > array.size 

    combination([], [], array, size) 
end 

def combination(result, step, array, size) 
    steps = size - step.size 
    array[0..-steps].each_with_index do |a, i| 
    next_step = step + [a] 
    if next_step.size < size 
     combination(result, next_step, array[i+1..-1], size) 
    else 
     result << next_step 
    end 
    end 
    result 
end 

a = ("A".."E").to_a 
p combinations(a, 1) 
# [["A"], ["B"], ["C"], ["D"], ["E"]] 
p combinations(a, 2) 
# [["A", "B"], ["A", "C"], ["A", "D"], ["A", "E"], ["B", "C"], ["B", "D"], ["B", "E"], ["C", "D"], ["C", "E"], ["D", "E"]] 
p combinations(a, 3) 
# [["A", "B", "C"], ["A", "B", "D"], ["A", "B", "E"], ["A", "C", "D"], ["A", "C", "E"], ["A", "D", "E"], ["B", "C", "D"], ["B", "C", "E"], ["B", "D", "E"], ["C", "D", "E"]] 
p combinations(a, 4) 
# [["A", "B", "C", "D"], ["A", "B", "C", "E"], ["A", "B", "D", "E"], ["A", "C", "D", "E"], ["B", "C", "D", "E"]] 

Answer 3

我能想到的方法來計算給定大小的組合，而無需使用遞歸，但它不是特別有效。但是，如果您想獲得所有尺寸的所有組合（有時稱爲「功率」），則效率非常高。 [編輯：顯然不是。看基準。 ]我的理解是這個問題涉及後者，但我會給每個方法。

如果index具有n元素，每個組合可以由n - 元素數組，其元素各自爲0或1，這意味着1組合包括索引處的元素，意思表示「0」（一個空格或）它不是。因此，我們可以通過簡單地產生長度n的所有二進制數，從它的字符串representatation將每個（與前導零）至"0"陣列產生該組所有尺寸的所有組合的年代和"1" S，取代"1"的用他們的索引位置，刪除"0"並在給定索引位置提取index的元素。

代碼

def all_combos(sz) 
    [*(0..2**sz-1)].map { |i| ("%0#{sz}b" % i).chars } 
       .map { |a| a.each_with_index 
          .select { |n,ndx| n=="1" }.map(&:last) } 
end 

def combos(input, n, all_combos) 
    all_combos.select { |c| c.size == n }.map { |c| input.values_at(*c) } 
end 

def power(input, all_combos) 
    all_combos.map { |c| input.values_at(*c) } 
end 

例

input = %w{b e a r s} 
    #=> ["b", "e", "a", "r", "s"] 
ac = all_combos(input.size) 
    #=> [[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4], 
    # [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4], [1, 2, 3], 
    # [1, 2, 3, 4], [0], [0, 4], [0, 3], [0, 3, 4], [0, 2], [0, 2, 4], 
    # [0, 2, 3], [0, 2, 3, 4], [0, 1], [0, 1, 4], [0, 1, 3], [0, 1, 3, 4], 
    # [0, 1, 2], [0, 1, 2, 4], [0, 1, 2, 3], [0, 1, 2, 3, 4]] 

(0..input.size).each { |i| puts "size #{i}"; p combos(input, i, ac) } 
    # size 0 
    # [[]] 
    # size 1 
    # [["s"], ["r"], ["a"], ["e"], ["b"]] 
    # size 2 
    # [["r", "s"], ["a", "s"], ["a", "r"], ["e", "s"], ["e", "r"], 
    # ["e", "a"], ["b", "s"], ["b", "r"], ["b", "a"], ["b", "e"]] 
    # size 3 
    # [["a", "r", "s"], ["e", "r", "s"], ["e", "a", "s"], ["e", "a", "r"], 
    # ["b", "r", "s"], ["b", "a", "s"], ["b", "a", "r"], ["b", "e", "s"], 
    # ["b", "e", "r"], ["b", "e", "a"]] 
    # size 4 
    # [["e", "a", "r", "s"], ["b", "a", "r", "s"], ["b", "e", "r", "s"], 
    # ["b", "e", "a", "s"], ["b", "e", "a", "r"]] 
    # size 5 
    # [["b", "e", "a", "r", "s"]] 

power(input, ac) 
    #=> [[], ["s"], ["r"], ["r", "s"], ["a"], ["a", "s"], ["a", "r"], 
    # ["a", "r", "s"], ["e"], ["e", "s"], ["e", "r"], ["e", "r", "s"], 
    # ["e", "a"], ["e", "a", "s"], ["e", "a", "r"], ["e", "a", "r", "s"], 
    # ["b"], ["b", "s"], ["b", "r"], ["b", "r", "s"], ["b", "a"], 
    # ["b", "a", "s"], ["b", "a", "r"], ["b", "a", "r", "s"], ["b", "e"], 
    # ["b", "e", "s"], ["b", "e", "r"], ["b", "e", "r", "s"], ["b", "e", "a"], 
    # ["b", "e", "a", "s"], ["b", "e", "a", "r"], ["b", "e", "a", "r", "s"]] 

Answer 4

先生們，開啓你的引擎吧！

方法相比

module Methods 
    def ruby(array) 
    (0..array.size).each_with_object([]) { |i,a| 
     a.concat(array.combination(i).to_a) } 
    end 

def todd(input) 
    permutations(input) << [] 
    end 

    private 

    def permutations(items) 
    return [] unless items.any? 
    prefix = items[0] 
    suffixes = permutations(items[1..-1]) 
    [[prefix]] + suffixes + suffixes.map {|item| [prefix, item].flatten } 
    end 

public 

    def fl00r(array) 
    (1..array.size).each_with_object([]) { |i,a| 
     a.concat(combinations(array, i)) } << [] 
    end 

    private 

    def combinations(array, size) 
    fail "size is too big" if size > array.size 
    combination([], [], array, size) 
    end 

    def combination(result, step, array, size) 
    steps = size - step.size 
    array[0..-steps].each_with_index do |a, i| 
     next_step = step + [a] 
     if next_step.size < size 
     combination(result, next_step, array[i+1..-1], size) 
     else 
     result << next_step 
     end 
    end 
    result 
    end 

public 

    def cary(input) 
    ac = all_combos(input.size) 
    ac.map { |c| input.values_at(*c) } 
    end 

    private 

    def all_combos(sz) 
    [*0..2**sz-1].map { |i| ("%0#{sz}b" % i).chars } 
       .map { |a| a.each_with_index.select { |n,ndx| n=="1" }.map(&:last) } 
    end 
end 

個

測試數據

def test_array(n) 
    [*1..n] 
end 

助手

def compute(arr, meth) 
    send(meth, arr) 
end 

def compute_sort(arr, meth) 
    compute(arr, meth).map(&:sort).sort 
end 

包括模塊

include Methods 
@methods = Methods.public_instance_methods(false) 
    #=> [:ruby, :todd, :fl00r, :cary] 

確認方法返回相同的值

arr = test_array(8) 

a = compute_sort(arr, @methods.first) 
puts @methods[1..-1].all? { |m| a == compute_sort(arr, m) } 
    #=> true 

基準碼

require 'benchmark' 

@indent = methods.map { |m| m.to_s.size }.max 

[10, 15, 20].each do |n| 
    puts "\nn = #{n}" 
    arr = test_array(n) 
    Benchmark.bm(@indent) do |bm| 
    @methods.each do |m| 
     bm.report m.to_s do 
     compute(arr, m).size 
     end 
    end 
    end 
end 

測試（秒）

n = 10 
           user  system  total  real 
ruby       0.000000 0.000000 0.000000 ( 0.000312) 
todd       0.000000 0.000000 0.000000 ( 0.001611) 
fl00r      0.000000 0.000000 0.000000 ( 0.002675) 
cary       0.010000 0.000000 0.010000 ( 0.010026) 

n = 15 
           user  system  total  real 
ruby       0.010000 0.000000 0.010000 ( 0.010742) 
todd       0.070000 0.010000 0.080000 ( 0.081821) 
fl00r      0.080000 0.000000 0.080000 ( 0.076030) 
cary       0.430000 0.020000 0.450000 ( 0.450382) 

n = 20 
           user  system  total  real 
ruby       0.310000 0.040000 0.350000 ( 0.350484) 
todd       2.360000 0.130000 2.490000 ( 2.487493) 
fl00r      2.320000 0.090000 2.410000 ( 2.405377) 
cary      21.420000 0.620000 22.040000 (22.053303) 

我只畫一個明確的結論。