どうも、木村（@kimu3_slime）です。
今回は、Julia（Combinatorics）で順列、組み合わせの問題を解く方法を紹介します。
準備
Combinatoricsを使うので、持っていなければインストールしておきましょう。
1 2 | using Pkg Pkg.add("Combinatorics") |
準備として、以下のコードを実行しておきます。
1 | using Combinatorics |
順列、組み合わせの個数
階乗\(n!\)は「factorial(n)」です。
1 | factorial(5) |
1 | 120 |
順列の個数\(_n P_k\)は、「partialderangement(n,k)」です。
1 | partialderangement(5,3) |
1 | 10 |
組み合わせの個数\(_n C _k\)は、「binomial(n,k)」です。
1 | binomial(3,2) |
1 | 3 |
階乗と組み合わせは、Combinatoricsと関係なく、基本的な関数（Base）として使えます。
順列、組み合わせの求め方
3つの文字\(a,b,c\)を使って、異なる3文字を選んで並べた文字列の順列を求めてみましょう。
文字の候補を配列として用意し、「collect(permutations(配列))」です。
1 2 | A = ["a","b","c"] collect(permutations(A)) |
1 2 3 4 5 6 7 8 9 10 11 12 | 3-element Vector{String}: "a" "b" "c" 6-element Vector{Vector{String}}: ["a", "b", "c"] ["a", "c", "b"] ["b", "a", "c"] ["b", "c", "a"] ["c", "a", "b"] ["c", "b", "a"] |
「collect(permutations(配列,サイズ))」で、サイズを指定した順列が求められます。3文字から異なる2文字を並べる順列なら次の通り。
1 | collect(permutations(A,2)) |
1 2 3 4 5 6 7 | 6-element Vector{Vector{String}}: ["a", "b"] ["a", "c"] ["b", "a"] ["b", "c"] ["c", "a"] ["c", "b"] |
順列では\(ab\)と\(ba\)が区別されています。
順番を区別しない考え方、組み合わせは「collect(combinations(配列,サイズ))」です。
1 | collect(combinations(A,2)) |
1 2 3 4 | 3-element Vector{Vector{String}}: ["a", "b"] ["a", "c"] ["b", "c"] |
与える文字列（配列）の順序を変えてみましょう。
1 2 | B = ["b","c","a"] collect(permutations(B)) |
1 2 3 4 5 6 7 8 9 10 11 12 | 3-element Vector{String}: "b" "c" "a" 6-element Vector{Vector{String}}: ["b", "c", "a"] ["b", "a", "c"] ["c", "b", "a"] ["c", "a", "b"] ["a", "b", "c"] ["a", "c", "b"] |
順列の順番も変わっています。得られる結果を辞書式にしたいならば、「sort」を使いましょう。
1 | sort(collect(permutations(B))) |
1 2 3 4 5 6 7 | 6-element Vector{Vector{String}}: ["a", "b", "c"] ["a", "c", "b"] ["b", "a", "c"] ["b", "c", "a"] ["c", "a", "b"] ["c", "b", "a"] |
重複する文字がある配列を与えると、どうなるでしょうか。
1 2 | C = ["a","a","b"] collect(permutations(C)) |
1 2 3 4 5 6 7 8 9 10 11 12 | 3-element Vector{String}: "a" "a" "b" 6-element Vector{Vector{String}}: ["a", "a", "b"] ["a", "b", "a"] ["a", "a", "b"] ["a", "b", "a"] ["b", "a", "a"] ["b", "a", "a"] |
配列に同じ文字aがあっても、順列としては区別して計算されていますね。
これらから重複しない結果を得るには「unique」を使うと良いでしょう。
1 | unique(collect(permutations(C))) |
1 2 3 4 | 3-element Vector{Vector{String}}: ["a", "a", "b"] ["a", "b", "a"] ["b", "a", "a"] |
今までの関数を利用して、次のような問題を解いてみましょう。
GAKKOUの6文字を並び替えてできる360個の文字列を辞書式に並べるとき、100番目の文字列を求めよ 数学科 若月一模
引用：電車内「答え出た時泣くかと思った」…受験生への応援メッセージに数学Aの問題 作成した予備校講師に聞いた思い – まいどなニュース
与えられた文字のリストから文字列を作るのは、順列の問題です。与える文字に重複「K」があるので、結果の重複のない順列を求めます。
1 2 | D = ["G","A","K","K","O","U"] unique(collect(permutations(D))) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | 6-element Vector{String}: "G" "A" "K" "K" "O" "U" 360-element Vector{Vector{String}}: ["G", "A", "K", "K", "O", "U"] ["G", "A", "K", "K", "U", "O"] ["G", "A", "K", "O", "K", "U"] ["G", "A", "K", "O", "U", "K"] ["G", "A", "K", "U", "K", "O"] ["G", "A", "K", "U", "O", "K"] ["G", "A", "O", "K", "K", "U"] ["G", "A", "O", "K", "U", "K"] ["G", "A", "O", "U", "K", "K"] ["G", "A", "U", "K", "K", "O"] ["G", "A", "U", "K", "O", "K"] ["G", "A", "U", "O", "K", "K"] ["G", "K", "A", "K", "O", "U"] ⋮ ["U", "O", "G", "A", "K", "K"] ["U", "O", "G", "K", "A", "K"] ["U", "O", "G", "K", "K", "A"] ["U", "O", "A", "G", "K", "K"] ["U", "O", "A", "K", "G", "K"] ["U", "O", "A", "K", "K", "G"] ["U", "O", "K", "G", "A", "K"] ["U", "O", "K", "G", "K", "A"] ["U", "O", "K", "A", "G", "K"] ["U", "O", "K", "A", "K", "G"] ["U", "O", "K", "K", "G", "A"] ["U", "O", "K", "K", "A", "G"] |
確かに360個の文字列ができるわけですが、これらを辞書式に並べ替えて、100番目の要素を取り出してみましょう。
1 2 | sort(unique(collect(permutations(D)))) sort(unique(collect(permutations(D))))[100] |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | 360-element Vector{Vector{String}}: ["A", "G", "K", "K", "O", "U"] ["A", "G", "K", "K", "U", "O"] ["A", "G", "K", "O", "K", "U"] ["A", "G", "K", "O", "U", "K"] ["A", "G", "K", "U", "K", "O"] ["A", "G", "K", "U", "O", "K"] ["A", "G", "O", "K", "K", "U"] ["A", "G", "O", "K", "U", "K"] ["A", "G", "O", "U", "K", "K"] ["A", "G", "U", "K", "K", "O"] ["A", "G", "U", "K", "O", "K"] ["A", "G", "U", "O", "K", "K"] ["A", "K", "G", "K", "O", "U"] ⋮ ["U", "O", "A", "G", "K", "K"] ["U", "O", "A", "K", "G", "K"] ["U", "O", "A", "K", "K", "G"] ["U", "O", "G", "A", "K", "K"] ["U", "O", "G", "K", "A", "K"] ["U", "O", "G", "K", "K", "A"] ["U", "O", "K", "A", "G", "K"] ["U", "O", "K", "A", "K", "G"] ["U", "O", "K", "G", "A", "K"] ["U", "O", "K", "G", "K", "A"] ["U", "O", "K", "K", "A", "G"] ["U", "O", "K", "K", "G", "A"] 6-element Vector{String}: "G" "O" "K" "A" "K" "U" |
「GOKAKU」という文字列、すなわち合格という答えが得られました。ちょうど100番目というのが良くできた問題ですね。
「100番目」という情報を知らないとして、「GOKAKU」という文字列が辞書式で何番目なのか求めてみましょう。
「indexin(配列B, 配列A)」で、配列Aにおいて配列Bの要素が何番目なのか（index）をまとめた配列が求められます。
1 | indexin(["b"],A)[1] |
1 | 2 |
これを使えば、
1 2 | indexin([[ "G", "O", "K", "A", "K", "U"]], sort(unique(collect(permutations(D)))))[1] |
1 | 100 |
と何番目にあるか求めることができました。
以上、Julia（Combinatorics）で順列、組み合わせの問題を解く方法を紹介してきました。
与えられた単語に対し、その文字列を入れ替えて別の単語を作る遊びは、アナグラムと呼ばれています。Combinatoricsを使えば、アナグラムの問題や回答が作りやすそうですね。
木村すらいむ（@kimu3_slime）でした。ではでは。
コロナ社 (2020-03-26T00:00:01Z)
￥7,353 (コレクター商品)
