Golang による順列列挙のパフォーマンス研究 3. 繰り上がり法（仮名）

# 関連記事

本記事は [Geek-Space Advent Calendar 2020](https://adventar.org/calendars/5566) の 6 日目です。（間に合ってない）

- [Golang による順列列挙のパフォーマンス研究 1. 再帰を用いたやり方](https://qiita.com/ikngtty/items/a494ff83f12646dee88f)
- [Golang による順列列挙のパフォーマンス研究 2. スタックを用いたやり方](https://qiita.com/ikngtty/items/66c95a4e8517b4a9d8bb)
- Golang による順列列挙のパフォーマンス研究 3. 繰り上がり法（仮名） （本記事）
- [Golang で順列・組み合わせ・重複順列・重複組み合わせの列挙](https://qiita.com/ikngtty/items/bbb864612d798e8292f8)

# はじめに

ここまでは、探索途中の情報をスタックに溜めたり、または再帰呼び出しを使ってコールスタックに溜めたりすることで、樹形図のノード間を複雑に右往左往していく動きを再現していきました。

さて、我々が順列を考える時の思考について、今一度分析してみます。

例として、`[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

# 実装

## 下準備

計測環境については前回と同様なので省略。

## まずはそのまま実装

```combinatorics/perm.go
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 つの測定結果は、今までの最速記録群です。この辺には全然勝てないですが、そんなに悪くもないですね。

## チェックリストを使う

いつものやつです。

```combinatorics/perm.go
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 つのループにすることができます。

```combinatorics/perm.go
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
```

依然優秀ですが、少し遅くなりました。
工夫しすぎてむしろ複雑化してしまった感じもあるので、あんまりオススメできないですね。

# まとめ

結論実装を再掲：

```combinatorics/perm.go
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
```

繰り上がり法が一番速いですね。まあでも僅差なので割とどれでもいい気がします。
「競プロでどれを使うか」とか考える時は、書きやすさで選ぶと良いと思います。
個人的には再帰が一番書きやすいですが、再帰に慣れない人は繰り上がり法が良いんじゃないでしょうか。

Next: [Golang で順列・組み合わせ・重複順列・重複組み合わせの列挙](https://qiita.com/ikngtty/items/bbb864612d798e8292f8)