関連記事
本記事は Geek-Space Advent Calendar 2020 の 6 日目です。（間に合ってない）
- Golang による順列列挙のパフォーマンス研究 1. 再帰を用いたやり方
- Golang による順列列挙のパフォーマンス研究 2. スタックを用いたやり方
- Golang による順列列挙のパフォーマンス研究 3. 繰り上がり法（仮名） （本記事）
- Golang で順列・組み合わせ・重複順列・重複組み合わせの列挙
はじめに
ここまでは、探索途中の情報をスタックに溜めたり、または再帰呼び出しを使ってコールスタックに溜めたりすることで、樹形図のノード間を複雑に右往左往していく動きを再現していきました。
さて、我々が順列を考える時の思考について、今一度分析してみます。
例として、[0, 1, 2, 3, 4, 5, 6] の 7 つから 4 つを取り出して並べる順列について考えてみましょう。
さて、1, 0, 6, 5 の次の順列は何でしょうか？
多くの人はこう考えるんじゃないでしょうか。
「まず 4 桁目の数値を上げようとしてみよう。5 の次は 6。これは 3 桁目で使っている。6 より上は無い。じゃあ 3 桁目を上げる必要があるな。あ、3 桁目も上げることができない。じゃあ 2 桁目だ。1 は 1 桁目で使ってるけど、2 なら空いてるぞ。じゃあ 1, 2 までは確定で、3, 4 桁目は残りの数を使って一番小さいやつにすればいいな。3 桁目は 0, 4 桁目は 1 と 2 がもう埋まってるから、3 だな。よし、1, 2, 0, 3。」
この思考を分析してみると、実は樹形図の発想なんて要らないことが分かります。
枝がここまでどう生えているかとか、把握する必要がない。
今までどう溜め込むか苦心してきた「探索途中の情報」ですが、実は我々はそんなものを溜め込まずに、目の前の順列を見るだけで次の順列を判断できるのです。
というわけで、今回はこの思考法をそのままコードで表現してみます。
「この思考法」といちいち呼ぶのもアレなので、テキトーに「繰り上がり法」と名付けました。（N 進法で値を増やして繰り上がりを処理するような思考に近いので。ちなみに重複順列だと完全に N 進法になります。）
コードは前回同様、全てこちらのリポジトリに上げてあります。
https://github.com/ikngtty/benchmark-go-combinatorics
実装
下準備
計測環境については前回と同様なので省略。
まずはそのまま実装
func PermutationsWithCarrying0(n, k int, f func([]int)) {
pattern := make([]int, k)
// 最初の順列をセット
for i := range pattern {
pattern[i] = i
}
for {
f(pattern)
// 値増やしチャレンジ
pos := k - 1 // 着目する桁。まずは右端から。
for {
// -1桁目を増やそうとしてる
// = 0桁目で更に繰り上がりが起きたということ
// = 最後の順列の更にその次の順列を作ろうとしている状況
// = 処理を切り上げるタイミング
if pos == -1 {
return
}
oldNum := pattern[pos]
willBreak := false // 大域脱出用
for newNum := oldNum + 1; newNum < n; newNum++ {
// 数字が使われていたらスキップ
willContinue := false // 大域脱出用
for i := 0; i < pos; i++ {
if pattern[i] == newNum {
willContinue = true // 大域脱出
break
}
}
// 大域脱出
if willContinue {
continue
}
// 使われていない数字を見つけたケース
// -> 今見ている桁をその数に書き換えて、値増やし成功。
pattern[pos] = newNum
willBreak = true // 大域脱出
break
}
// 大域脱出
if willBreak {
break
}
// 今見ている桁の値はこれ以上増やせないというケース
// -> 繰り上がり。見る桁を一つ左にずらして繰り返す。
pos--
}
// 繰り上がった桁（値を増やした桁より右の桁全部）を埋める。なるべく小さい数字で埋める。
for pos++; pos < k; pos++ {
for num := 0; num < k; num++ {
// 数字が使われていたらスキップ
willContinue := false
for i := 0; i < pos; i++ {
if pattern[i] == num {
willContinue = true
break
}
}
if willContinue {
continue
}
// 使われていない数字を見つけたケース
// -> その数で書き換え
pattern[pos] = num
break
}
}
}
}
PermutationsRecursive6 191816791 ns 96 B 2 allocs
PermutationsWithSlice7 183175502 ns 9504 B 9 allocs
PermutationsWithCarrying0 602414196 ns 80 B 1 allocs
今回の測定結果の上に並べた 2 つの測定結果は、今までの最速記録群です。この辺には全然勝てないですが、そんなに悪くもないですね。
チェックリストを使う
いつものやつです。
func PermutationsWithCarrying1(n, k int, f func([]int)) {
checklist := make([]bool, n)
pattern := make([]int, k)
for i := range pattern {
pattern[i] = i
checklist[i] = true
}
for {
f(pattern)
pos := k - 1
for {
if pos == -1 {
return
}
oldNum := pattern[pos]
checklist[oldNum] = false
willBreak := false
for newNum := oldNum + 1; newNum < n; newNum++ {
if checklist[newNum] {
continue
}
pattern[pos] = newNum
checklist[newNum] = true
willBreak = true
break
}
if willBreak {
break
}
pos--
}
for pos++; pos < k; pos++ {
for num := 0; num < k; num++ {
if checklist[num] {
continue
}
pattern[pos] = num
checklist[num] = true
break
}
}
}
}
PermutationsRecursive6 191816791 ns 96 B 2 allocs
PermutationsWithSlice7 183175502 ns 9504 B 9 allocs
PermutationsWithCarrying0 602414196 ns 80 B 1 allocs
PermutationsWithCarrying1 149944171 ns 96 B 2 allocs
最速出ました！
やはりチェックリストによる使用済み番号管理は欠かせない模様。
ループをまとめる
ここまでのコードは、「前半：右端の桁から繰り上がりで徐々に左に進むループ」「後半：繰り上がった桁を埋め直すために右端へと戻っていくループ」の 2 つのループを並べる構成でした。
この 2 つのループをまとめて 1 つのループにすることができます。
func PermutationsWithCarrying2(n, k int, f func([]int)) {
checklist := make([]bool, n)
pattern := make([]int, k)
// 最初の順列をセット
for i := range pattern {
pattern[i] = i
checklist[i] = true
}
// 前回は 1 ループ 1 順列のループがあって、その内部に 1 ループ 1 桁のループがあった。
// 今回はいきなり 1 ループ 1 桁から始まる感じ。
pos := k // まずは右端の更に右から。`f`を実行したらすぐ右端に戻ってくる。
for pos > -1 {
if pos == k {
f(pattern)
pos--
continue
}
oldNum := pattern[pos]
if oldNum > -1 {
checklist[oldNum] = false
}
// 値増やしチャレンジ
willContinue := false // 大域脱出用
for newNum := oldNum + 1; newNum < n; newNum++ {
if checklist[newNum] {
continue
}
// 値増やしチャレンジ成功 -> 右へ進む
pattern[pos] = newNum
checklist[newNum] = true
pos++
willContinue = true // 大域脱出
break
}
// 大域脱出
if willContinue {
continue
}
// 値増やしチャレンジ失敗 -> 繰り上がり。左へ進む。
pattern[pos] = -1 // 一旦-1にしておくのがポイント
pos--
}
}
繰り上がりの時に、その桁の数字を -1 にしておくのがポイントです。
これにより、左向きに繰り上がっていく時の値増やしチャレンジと、右向きに値を埋めていく時の値増やしチャレンジを、同じコード（元の値から少しだけ値を増やそうとチャレンジする）で行うことができます。
PermutationsRecursive6 191816791 ns 96 B 2 allocs
PermutationsWithSlice7 183175502 ns 9504 B 9 allocs
PermutationsWithCarrying1 149944171 ns 96 B 2 allocs
PermutationsWithCarrying2 170103707 ns 96 B 2 allocs
依然優秀ですが、少し遅くなりました。
工夫しすぎてむしろ複雑化してしまった感じもあるので、あんまりオススメできないですね。
まとめ
結論実装を再掲：
func PermutationsWithCarrying1(n, k int, f func([]int)) {
checklist := make([]bool, n)
pattern := make([]int, k)
for i := range pattern {
pattern[i] = i
checklist[i] = true
}
for {
f(pattern)
pos := k - 1
for {
if pos == -1 {
return
}
oldNum := pattern[pos]
checklist[oldNum] = false
willBreak := false
for newNum := oldNum + 1; newNum < n; newNum++ {
if checklist[newNum] {
continue
}
pattern[pos] = newNum
checklist[newNum] = true
willBreak = true
break
}
if willBreak {
break
}
pos--
}
for pos++; pos < k; pos++ {
for num := 0; num < k; num++ {
if checklist[num] {
continue
}
pattern[pos] = num
checklist[num] = true
break
}
}
}
}
今回の計測結果群は以下：
PermutationsWithCarrying0 602414196 ns 80 B 1 allocs
PermutationsWithCarrying1 149944171 ns 96 B 2 allocs
PermutationsWithCarrying2 170103707 ns 96 B 2 allocs
優秀ですね。
最速シリーズを今一度まとめ：
PermutationsRecursive6 191816791 ns 96 B 2 allocs
PermutationsWithSlice7 183175502 ns 9504 B 9 allocs
PermutationsWithCarrying1 149944171 ns 96 B 2 allocs
繰り上がり法が一番速いですね。まあでも僅差なので割とどれでもいい気がします。
「競プロでどれを使うか」とか考える時は、書きやすさで選ぶと良いと思います。
個人的には再帰が一番書きやすいですが、再帰に慣れない人は繰り上がり法が良いんじゃないでしょうか。