今さらながら、Rubyで順列・組み合わせを実装してみた

プログラミング問題に登場する「最短経路問題」とかさっぱりわからなかったので、いろいろ調べてみた。
どうやら、中学受験とか高校数学とかで出てくる、順列・組み合わせを勉強しとくと良いらしい。
そこで、Rubyの組み込みメソッドを使わずに、パターンを列挙するコードを再帰呼び出しで実装した。

階乗

factorial
5! = 5 * 4 * 3 * 2 * 1
n! = n * (n - 1) * (n - 2) ・・・* 3 * 2 * 1
n! = n * (n - 1)! 　　　と再帰で定義できる
「0! = 1」と定義しておく

# 階乗を計算：ループ

def factorial(number, result = 1)
    return result if number <= 1
    factorial(number - 1, result * number)
end

puts factorial(10)

paiza.IO
https://paiza.io/projects/6Ic-z9ulnG7Ygxk4wUuR8Q

順列

permutation
n個の物を並べるパターン
とりあえず、物は、ひとつずつ別のもの。
順番が違えば、違うパターンと考える
パターン数は、n!になる

n個の物からr個を選んで並べるパターン
n[** P]r = n! / (n - r)!

例
1, 2, 3 の順列を列挙すると、123, 132, 213, 231, 312, 321 の6パターン

# 順列の列挙：再帰
def permutation(array, number, temp = "", result = [])
    return result << temp if temp.size >= number

    array.each_with_index do |value, i|
        copy_array = array.clone
        copy_array.delete_at(i)
        permutation(copy_array, number, temp + value, result)
    end
    return result
end

result = permutation(["A", "B", "C", "D"], 3)
puts result.size
p result

paiza.IO
https://paiza.io/projects/OthkafOwgKZwcF9OCrkOqA

Ruby 組み込みメソッド
Array#permutation (Ruby 2.7.0 リファレンスマニュアル)
https://docs.ruby-lang.org/ja/latest/method/Array/i/permutation.html

0の階乗を1と定義する理由 | 高校数学の美しい物語
https://mathtrain.jp/0nokaijo

同じものを含む順列

「同じものを含む順列」と、これでひとつの手法になっている。
最短経路問題に、これを使う。
たとえば、a,a,b,b,b,c,d の７つの文字を一列に並べて順列を作る
この場合、並べる物に同一の物が含まれていて区別できない
既に選ばれたものを並べ替える、とも言える

𝑛 個の中に同じものが 𝑝 個、𝑞 個、𝑟 個・・・ずつあるとき、その並べ方の総数は
n! / p! * q! * r!

例
"A", "B", "B", "C"から2つ選んで並べる
"AB", "AC", "BA", "BB", "BC", "CA", "CB"

# 同じ物を含む順列：再帰
def mults_permutation(array, number, temp = "", result = [])
    if temp.size >= number
        
        if !result.include?(temp) then
            result << temp
        end
        
        return
    end

    array.each_with_index do |value, i|
        
        copy_array = array.clone
        copy_array.delete_at(i)
        mults_permutation(copy_array, number, temp + value, result)
        
    end
    
    return result
end


# result = mults_permutation(["O", "O", "O", "I", "I"], 5)
result = mults_permutation(["A", "B", "B", "C"], 2)
puts result.size
p result

paiza.IO
https://paiza.io/projects/RwoyHv2T36svGflpP7nupg

同じものを含む順列の公式　意味と使い方 | | 高校数学の知識庫
http://math-souko.jp/%E5%90%8C%E3%81%98%E3%82%82%E3%81%AE%E3%82%92%E5%90%AB%E3%82%80%E9%A0%86%E5%88%97%E3%81%AE%E5%85%AC%E5%BC%8F%E3%80%80%E6%84%8F%E5%91%B3%E3%81%A8%E4%BD%BF%E3%81%84%E6%96%B9/

重複順列

sequence with repetition
重複を許して、n個の物からr個を選んで並べるパターン
通常の順列は、ひとつずつ別の物と考える
重複順列は、同じ物が複数回、選ばれてもいい。ゼロ回でもいい。
1から4までの番号が付いた異なる箱が4つあるとき、赤、白のボールを1個ずつ入れるパターンは何通りあるか。

重複順列のパターン数 = n ^ r

例
ABCから、2文字選ぶ重複順列
"AA", "AB", "AC", "BA", "BB", "BC", "CA", "CB", "CC"

# 重複順列の列挙：再帰
def sequence(array, number, temp = "", result = [])
    return result << temp if temp.size >= number

    array.each do |value|
        sequence(array, number, temp + value, result)
    end
    return result
end

result = sequence(["A", "B", "C"], 2)
puts result.size
p result

paiza.IO
https://paiza.io/projects/awyYFUAwo_BxdDLjO0RCEg

Ruby 組み込みメソッド
Array#repeated_permutation (Ruby 2.7.0 リファレンスマニュアル)
https://docs.ruby-lang.org/ja/latest/method/Array/i/repeated_permutation.html

重複順列＝同じものを並べられる順列。その考え方をイラストで解説 - 理数白書
https://www.risuuhakusyo.com/cyouhuku-junretu

組み合わせ

Combination
異なる n 個から r 個取り出したときのパターン
順番は考慮しない。順番が違っても、同じパターンと考える

n[** C]r = n! / (n - r)! * 1/r!
r! ：同じ要素で順番が異なるパターンで割る

例
A, B, C, Dから2個取り出す組み合わせ > AB, AC, AD, BC, BD, CD

# 組み合わせの列挙: 再帰
def combination(array, number, temp = "", result = [])
    return result << temp if temp.size >= number
    
    array.each_with_index do |top, i|
        sub_array = array[i + 1, array.size]
        # p "#{temp + top}, #{sub_array}"
        combination(sub_array, number, temp + top, result)
    end
    return result
end

result = combination(["A", "B", "C", "D", "E"], 2)
p result.size
p result

paiza.IO
https://paiza.io/projects/lmey5fFLbARUhlIsL9MUMQ

Ruby 組み込みメソッド
Array#combination (Ruby 2.7.0 リファレンスマニュアル)
https://docs.ruby-lang.org/ja/latest/method/Array/i/combination.html

順列と組み合わせの公式とその違い【問題付き】 | 理系ラボ
https://rikeilabo.com/formula-and-diferrence-of-Permutation-combination

重複組み合わせ

repeated_combination
異なる n 種類のものから[[重複]]を許して r 個取る組合せ
総数は、n+r-1[** C]r

例
たとえば、赤・白・黒の3種類の玉から、重複を許して３個をとる組み合わせは

赤赤赤、赤赤白、赤白白、赤白黒、赤赤黒、赤黒黒、白白黒、白黒黒、白白白、黒黒黒

玉3個と境2個について、 〇｜〇｜〇 を使った、[同じものを含む順列]と考えられる。
〇が玉の位置、｜が境界の位置。境界が色の境目になる。境界数は、「玉の種類数 - 1」
すると、左から、玉の位置が赤・白・黒に相当

OOOII > 赤赤赤
OOIOI > 赤赤白
OOIIO > 赤赤黒
OIOOI > 赤白白
OIOIO > 赤白黒
OIIOO > 赤黒黒
IOOOI > 白白白
IOOIO > 白白黒
IOIOO > 白黒黒
IIOOO > 黒黒黒

また、5個の場所（_ _ _ _ _）から、3個を選んだ[組み合わせ]と考えることもできる

# 重複組み合わせの列挙。同じ物を含む順列を利用した

def mults_permutation(array, number, temp = "", result = [])
    if temp.size >= number
        
        if !result.include?(temp) then
            result << temp
        end
        
        return
    end

    array.each_with_index do |value, i|
        
        copy_array = array.clone
        copy_array.delete_at(i)
        mults_permutation(copy_array, number, temp + value, result)
        
    end
    
    return result
end

def repeated_combination(array, number)
    pos = Array.new(number, "o") +  Array.new(array.size - 1, "I")
    pattern = mults_permutation(pos, pos.size)
    # p pattern
    
    result = []
    pattern.each do |value|
        value_array = value.split("I")
        item_list = ""
        value_array.each_with_index do |item, i|
            item_list += item.gsub(/(o)/, array[i])
        end
        result << item_list
    end
    
    return result    
end

result = repeated_combination(["A", "B", "C"], 4)
p result.size
p result

paiza.IO
https://paiza.io/projects/xfWb-Hulyiphdgisd2vN6g

Ruby 組み込みメソッド
Array#repeated_combination (Ruby 2.7.0 リファレンスマニュアル)
https://docs.ruby-lang.org/ja/latest/method/Array/i/repeated_combination.html

重複組合せとは – 重複組合せの公式の意味 | きぬごしのお受験ブログ
https://toufumentals-kinugoshi.com/duplicate-combination/