読者です 読者をやめる 読者になる 読者になる

順列をすべて舐める

以下のように複数の集合があった場合に

sets = [
  [1,2,3,4],
  [5,6,7],
  [8,9],
]

すべての順列を舐める関数を定義してみる。

def permutation(stack, ary = [], &block)
  list = stack.shift

  list.each do |i|
    if stack.empty?
      block.call(ary + [i])
    else
      permutation(stack, ary + [i], &block)
    end
  end

  stack.unshift(list)
end

permutation(sets) do |seq|
  p seq
end
# => [1, 5, 8]
#    [1, 5, 9]
#    [1, 6, 8]
#    [1, 6, 9]
#    [1, 7, 8]
#    [1, 7, 9]
#    [2, 5, 8]
#    [2, 5, 9]
#    [2, 6, 8]
#    [2, 6, 9]
#    [2, 7, 8]
#    [2, 7, 9]
#    [3, 5, 8]
#    [3, 5, 9]
#    [3, 6, 8]
#    [3, 6, 9]
#    [3, 7, 8]
#    [3, 7, 9]
#    [4, 5, 8]
#    [4, 5, 9]
#    [4, 6, 8]
#    [4, 6, 9]
#    [4, 7, 8]
#    [4, 7, 9]