順列を列挙するプログラム
順列とは簡単に言えば1から自然数Nまでの重複のない自然数の集合から、すべて重複無しで使いながら並べた数字列のパターンである。
全然簡単じゃなかった。
ちなみに僕は順列=Permutationだと思ってたのだが、どうも数学的には違うらしい。
今回書きたかったのは与えられた数字の集合から重複しない並び順の組み合わせをすべて列挙するプログラムである。
簡単な例を上げると、
[1,2,3]からは[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]が列挙されるプログラムである。
高校数学で習った順列では、そのパターンの数を計算するだけで実際に列挙する手段については習わなかった。
しかし定義を理解していれば案外簡単に書くことができる。今回はTypeScript(Deno)で書いてみた。 code:perm.ts
// arrは並び替える数の集合
function* perm(arr: number[]): IterableIterator<number[]> {
// 再帰の最後では空の順列を返す
if (arr.length === 0) {
yield [];
}
for (let i = 0; i < arr.length; i++) {
// 先頭の数字を決める
// 決めた数字以外のみの集合を作る(要素が1つ減る)
rest.splice(i, 1);
// 再帰で残りの要素の順列を列挙し、それを後ろにつけたものを列挙する
for (const j of perm(rest)) {
}
}
}
hr.icon
以下解説
順列の列挙は、再帰を使って書くことができる。
関数の中で行うことは「与えられた集合から要素を一つ取って、それを先頭に持つパターンを列挙する」ことである
つまり、(1,2,3)という集合を受け取った関数は、
1と(2,3)の順列との組み合わせ
2と(1,3)の順列との組み合わせ
3と(1,2)の順列との組み合わせ
を列挙すればよい
同様に、(2,3)を受け取った関数は、
2と(3)
3と(2)
の組み合わせを列挙すればいい
これを再帰的に実行すると、一つ深さを下げると列挙対象となる集合の濃度(要素数)が一つずつ減っていく
そうして最終的にすべての順列が列挙できる
再帰をうまく使うと一見複雑な処理もこのように美しく記述することができる
JS的解説
generatorを使ったのはなんとなく便利だったからで、別に使わずとも書ける
その場合は返り値をnumber[][]にすればよい
おまけ
https://gyazo.com/82a97a6a558a1b489630c56cd0c980a1
こういうパズルも順列を列挙するプログラムがあれば一瞬で解ける
ちなみになんとたった一つだけピタリとはまる順列が存在する!
これはTwitterで回ってきたもので出典元が分からないのだが、数学的に解く方法はあるのだろうか…