Zenn
🍕

Juliaで順列と組み合わせを列挙する

2022/04/23に公開
2件
Julia
Jupyter Notebook
組み合わせ
順列
tech

プログラムを書いていたらfor文がだんだんと増えていって, 結局は再帰構文に行きつくことに気付いたのではないだろうか. 少しばかり難しいので, 調べた結果をまとめる. 以下では, 全て異なるものを選ぶ場合を考え, 全パターンを列挙するプログラムを考える.

全てを選ぶパターン k個を選ぶパターン
順列 n!
_n\mathrm{P}_k = \frac{n!}{(n-k)!}
円順列
(n-1)!
\frac{(n-1)!}{(n-k)!}
数珠順列
\frac{(n-1)!}{2}
\frac{1}{2}\frac{(n-1)!}{(n-k)!}
組み合わせ 1
_n\mathrm{C}_k = \frac{n!}{(n-k)!k!}

順列

Rosetta Codeで紹介されている順列の列挙のプログラムは

順列の列挙
# https://rosettacode.org/wiki/Permutations#Julia
perms(l) = isempty(l) ? [l] : [[x; y] for x in l for y in perms(setdiff(l, x))]

for perm in perms([1,2,3])
    println(perm)
end
出力
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

だが, 少しばかり圧縮されすぎていて何をしているのかわからない. 「ある要素を選んで, 残りの要素からまた選ぶ」という, 多少の無駄はあるが直感的な実装を以下に示す. 上記のRosseta Codeの出力と同じである.

順列の列挙
function permutations(choices)
    permutations = Vector[]
    function permutation(choices; chosen=Int64[])
        if isempty(choices)
            push!(permutations, chosen)
        else
            for x in choices
                permutation(setdiff(choices, [x]), chosen=union(chosen, [x]))
            end
        end
    end
    permutation(choices)
    return permutations
end

for perm in permutations([1,2,3])
    println(perm)
end
出力
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

上記は与えられたリストの全ての要素を並べるパターン. n個の中からk個を選ぶ場合はif文の判定部分をisempty(choices)からlength(chosen) == kに変えればよい. _3\mathrm{P}_2=\frac{3!}{(3-2)!}

順列の列挙（一部のみ選ぶ）
function permutations(choices, k)
    permutations = Vector[]
    function permutation(choices; chosen=Int64[])
        if length(chosen) == k
            push!(permutations, chosen)
        else
            for x in choices
                permutation(setdiff(choices, [x]), chosen=union(chosen, [x]))
            end
        end
    end
    permutation(choices)
    return permutations
end
    
for perm in permutations([1,2,3], 2)
    println(perm)
end
出力
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

円順列

誰かコメントにください.（個人的には順列だけで十分だったのでひとまず公開しました. ﾕﾙｼﾃ）

数珠順列

誰かコメントにください.（個人的には順列だけで十分だったのでひとまず公開しました. ﾕﾙｼﾃ）

組み合わせ

n個の中からn個を選ぶパターンは1通りしかないためつまらない. n個の中から1\leq k<n個を選ぶパターンを考える. Rosseta CodeではCombinatorics.jlを利用する方法とライブラリに頼らない実装の両方が与えられている. ここではライブラリを使った例を示す.

ライブラリ
# using Pkg
# Pkg.add("Combinatorics")
using Combinatorics
組み合わせの列挙
# using Combinatorics
for comb in combinations([1,2,3,4,5], 3)
    println(comb)
end
出力
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

この記事の元になったノートは下記のリンクにある.
https://gist.github.com/ohno/3063eed30ad90571250c46c48c5e3092

清水団さんが円順列と数珠順列も含めて, さらに同じものを含む場合にも対応した記事を書いてくださいました. 上位互換です.
https://zenn.dev/dannchu/articles/4d35b5d2b4c94c

Discussion