Golang で順列・組み合わせ・重複順列・重複組み合わせの列挙

# 関連記事

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

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

# はじめに

関連記事にある通り、ここまで順列に関して 3 つのやり方を追求していきました。
今回はこの 3 つのやり方（再帰を用いる、スタックを用いる、繰り上がり法）を、組み合わせ、重複順列、重複組合せにも適用することで、この辺のパターンをひと通り網羅しておこうと思います。

計測は今まで同様、以下のオンボロマシンです：

```
macOS Big Sur
バージョン 11.0.1

MacBook Air (11-inch, Early 2015)
プロセッサ 1.6 GHz デュアルコアIntel Core i5
メモリ 4 GB 1600 MHz DDR3

go version go1.15.5 darwin/amd64
```

計測結果は少し編集して、実行時間（ns）、使用メモリ容量（B）、メモリ割り当て数（allocs）を載せます。

コードは全てこちらのリポジトリに上げてあります。（これも今までの記事と同様）
https://github.com/ikngtty/benchmark-go-combinatorics

# 順列

<img alt="tree-graph.png" width=300px src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140384/bf07b8a2-19a7-ef92-81e5-14fa4c0652fe.png">

詳しくは関連記事に書いた通りです。ここでは結論をまとめ直していきます。

## 下準備

以下のコードでパフォーマンスを計測しました：

```combinatorics/perm_test.go
func BenchmarkPermutations(b *testing.B) {
	const n = 10
	const k = 10

	doSomethingForPattern := func(pattern []int) {
		total := 0
		for i := 1; i < len(pattern); i++ {
			total += pattern[i] - pattern[i-1]
		}
	}

	targets := []struct {
		name string
		f    func()
	}{
		{"テスト対象関数の名前",
			func() {
				// テスト対象関数を用いて、[0, 1, ..., n-1]の数の中からk個選ぶ順列を生成し、
				// 各順列に対して`doSomethingForPattern`を行う。
			}},
		// ...
	}

	for _, target := range targets {
		b.Run(target.name, func(b *testing.B) {
			for try := 0; try < b.N; try++ {
				target.f()
			}
		})
	}
}
```

## 再帰を用いたやり方

最も素直な実装はこんな感じでした。

```combinatorics/perm.go
func PermutationsRecursive0(a []int, k int) [][]int {
	if k == 0 {
		pattern := []int{}
		return [][]int{pattern}
	}

	ans := [][]int{}
	for i := range a {
		aRest := make([]int, len(a)-1)
		for j := 0; j < i; j++ {
			aRest[j] = a[j]
		}
		for j := i + 1; j < len(a); j++ {
			aRest[j-1] = a[j]
		}

		childPatterns := PermutationsRecursive0(aRest, k-1)
		for _, childPattern := range childPatterns {
			pattern := append([]int{a[i]}, childPattern...)
			ans = append(ans, pattern)
		}
	}

	return ans
}
```

しかし実測結果は以下のようにズタボロ：

```
PermutationsRecursive0   	6338217782 ns	5168828928 B	89707742 allocs
```

ここから色々改善し、以下のコードにたどり着きました：

```combinatorics/perm.go
func PermutationsRecursive6(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	pattern := make([]int, k)

	var body func(pos int)
	body = func(pos int) {
		if pos == k {
			f(pattern)
			return
		}

		for num := range checklist {
			if checklist[num] {
				continue
			}

			pattern[pos] = num
			checklist[num] = true
			body(pos + 1)
			checklist[num] = false
		}
	}
	body(0)
}
```

```
PermutationsRecursive6   	 191816791 ns	        96 B	       2 allocs
```

## スタックを用いたやり方

最終的に、スライスでスタックを実装すると良いことが分かりました。
色々細かくスタックの使い方を変えたりしましたが、スライス版の場合は大してパフォーマンスが変わらないものが多かったです。
なので今回はその中でも一番スタンダードっぽい、「樹形図のノードをスタックに積む」という発想のやつをセレクトします。

```combinatorics/perm.go
func PermutationsWithSlice2(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	patternNodeStack := make([]patternNode2, 1)
	pattern := make([]int, k)

	patternNodeStack[0] = patternNode2{pos: -1, number: 0}
	for len(patternNodeStack) > 0 {
		patternNode := patternNodeStack[len(patternNodeStack)-1]
		patternNodeStack = patternNodeStack[:len(patternNodeStack)-1]

		for i := patternNode.pos; i < k; i++ {
			if i > -1 && pattern[i] > -1 {
				checklist[pattern[i]] = false
				pattern[i] = -1
			}
		}

		if patternNode.pos > -1 {
			pattern[patternNode.pos] = patternNode.number
			checklist[patternNode.number] = true
		}

		if patternNode.pos == k-1 {
			f(pattern)
			continue
		}

		for num := n - 1; num >= 0; num-- {
			if checklist[num] {
				continue
			}

			childNode := patternNode2{
				pos: patternNode.pos + 1, number: num,
			}
			patternNodeStack = append(patternNodeStack, childNode)
		}
	}
}
```

```
PermutationsWithSlice2   	 186323035 ns	      2112 B	       8 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
			}
		}
	}
}

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
	}

	pos := k
	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
		pos--
	}
}
```

```
PermutationsWithCarrying1	 149944171 ns	        96 B	       2 allocs
PermutationsWithCarrying2	 170103707 ns	        96 B	       2 allocs
```

## 計測結果まとめ

```
PermutationsRecursive0   	6338217782 ns	5168828928 B	89707742 allocs
PermutationsRecursive6   	 191816791 ns	        96 B	       2 allocs
PermutationsWithSlice2   	 186323035 ns	      2112 B	       8 allocs
PermutationsWithCarrying1	 149944171 ns	        96 B	       2 allocs
PermutationsWithCarrying2	 170103707 ns	        96 B	       2 allocs
```

# 組み合わせ

<img alt="tree-graph.png" width=300px src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140384/2db3853a-ab18-4192-8dee-f7abad113b26.png">


`1 桁目の数字 < 2 桁目の数字 <  ... < k 桁目の数字` という制約をつければ、あとは順列と同様に列挙することができます。
というか、今までは「x 桁目に使える数字」を考える時に「1 〜 x-1 桁目までに使われた数字を全て把握する」ということが必要でしたが（そのために「使用済み番号チェックリスト」という概念を持ち出したりしました）、今回の場合は「x-1 桁目の数字より上の数字が全部使える」とはっきり分かるので、その辺の処理が一気に楽になります。
ただ、例えば `[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]` から 6 個選ぶ組み合わせの時に、3 桁目とかに 9 を使ってしまうと、4 桁目以降に使える数字がなくなってしまったりします。一番大きい組み合わせが `{4, 5, 6, 7, 8, 9}` となるのを考えると、3 桁目の上限は 6 ですね。
この辺を加味すると、`[0, 1, ..., n-1]` から k 個選ぶ組み合わせにおいて x 桁目に使える数字は、「x-1 桁目の数字より上で、n-1-k+x 以下」となってきます。
ここまで整理できれば実装できたも同然です。

## 下準備

以下のコードで計測（ほとんど n と k を弄っただけです）：

```combinatorics/combi_test.go
func BenchmarkCombinations(b *testing.B) {
	const n = 24
	const k = 12

	doSomethingForPattern := func(pattern []int) {
		total := 0
		for i := 1; i < len(pattern); i++ {
			total += pattern[i] - pattern[i-1]
		}
	}

	targets := []struct {
		name string
		f    func()
	}{
		{"テスト対象関数の名前",
			func() {
				// テスト対象関数を用いて、[0, 1, ..., n-1]の数の中からk個選ぶ組み合わせを生成し、
				// 各組み合わせに対して`doSomethingForPattern`を行う。
			}},
		// ...
	}

	for _, target := range targets {
		b.Run(target.name, func(b *testing.B) {
			for try := 0; try < b.N; try++ {
				target.f()
			}
		})
	}
}
```

## 再帰を用いたやり方

素直に書けばこう：

```combinatorics/combi.go
// [begin, begin+1, ..., end-1]（半開区間）からk個選ぶ組み合わせ
func CombinationsRecursive0(begin, end, k int) [][]int {
	if k == 0 {
		pattern := []int{}
		return [][]int{pattern}
	}

	ans := [][]int{}
	for num := begin; num < end-k+1; num++ {
		childPatterns := CombinationsRecursive0(num+1, end, k-1)
		for _, childPattern := range childPatterns {
			pattern := append([]int{num}, childPattern...)
			ans = append(ans, pattern)
		}
	}

	return ans
}
```

「x-1 桁目の数字より上の数字が x 桁目に使える数字の範囲」ということで、使える数字を範囲で受け取る形で書いています。

```
CombinationsRecursive0   	5270823668 ns	5060925400 B	70747903 allocs
```

ここから同様に工夫を凝らすとこうなります：

```combinatorics/combi.go
func CombinationsRecursive1(n, k int, f func([]int)) {
	pattern := make([]int, k)

	var body func(pos, begin int)
	body = func(pos, begin int) {
		if pos == k {
			f(pattern)
			return
		}

		for num := begin; num < n+pos-k+1; num++ {
			pattern[pos] = num
			body(pos+1, num+1)
		}
	}
	body(0, 0)
}
```

```
CombinationsRecursive1   	  55564969 ns	        96 B	       1 allocs
```

処理時間のオーダーが 2 桁違うので笑うしかない。

ちなみに、「x-1 桁目の数字」はわざわざ引数で渡さなくても生成中の組み合わせを見れば分かることなので、これを踏まえれば引数を 1 つ減らすことができます。

```combinatorics/combi.go
func CombinationsRecursive2(n, k int, f func([]int)) {
	// 0桁目からでも-1桁目の数字を見れるように先頭にダミーを1桁追加している
	pattern := make([]int, k+1)
	// 生成中の順列には、「まだちゃんと値を入れていない」という情報を
	// ちゃんと-1として埋め込む必要が出てきた
	pattern[0] = -1

	var body func(pos int)
	body = func(pos int) {
		if pos == k+1 {
			f(pattern[1:]) // ダミーを除いて使用
			return
		}

		for num := pattern[pos-1] + 1; num < n+pos-k; num++ {
			pattern[pos] = num
			body(pos + 1)
		}
	}
	body(1)
}
```

```
CombinationsRecursive2   	  58998589 ns	       112 B	       1 allocs
```

なんかむしろ遅くなりました。ボツですね。

## スタックを用いたやり方

```combinatorics/combi.go
// 順列のコードから流用
type patternNode3 struct {
	pos    int
	number int
}

func CombinationsWithSlice0(n, k int, f func([]int)) {
	patternNodeStack := make([]patternNode3, 1)
	pattern := make([]int, k)

	patternNodeStack[0] = patternNode3{pos: -1, number: -1}
	for len(patternNodeStack) > 0 {
		patternNode := patternNodeStack[len(patternNodeStack)-1]
		patternNodeStack = patternNodeStack[:len(patternNodeStack)-1]

		if patternNode.pos > -1 {
			pattern[patternNode.pos] = patternNode.number
		}

		if patternNode.pos == k-1 {
			f(pattern)
			continue
		}

		for num := n + patternNode.pos - k + 1; num >= patternNode.number+1; num-- {
			childNode := patternNode3{
				pos: patternNode.pos + 1, number: num,
			}
			patternNodeStack = append(patternNodeStack, childNode)
		}
	}
}
```

チェックリストが必要なくなったので、ちょっとスッキリしています。

```
CombinationsWithSlice0   	  44367916 ns	      8256 B	       9 allocs
```

## 繰り上がり法

こちらも分かりやすいやつとループまとめて工夫したやつの 2 つ用意しました。

```combinatorics/combi.go
func CombinationsWithCarrying0(n, k int, f func([]int)) {
	pattern := make([]int, k)
	for i := range pattern {
		pattern[i] = i
	}

	for {
		f(pattern)

		pos := k - 1
		for {
			if pos == -1 {
				return
			}

			oldNum := pattern[pos]
			if oldNum == n+pos-k {
				pos--
				continue
			}

			pattern[pos]++
			break
		}

		for pos++; pos < k; pos++ {
			pattern[pos] = pattern[pos-1] + 1
		}
	}
}

func CombinationsWithCarrying1(n, k int, f func([]int)) {
	pattern := make([]int, k)
	for i := range pattern {
		pattern[i] = i
	}

	pos := k
	for pos > -1 {
		if pos == k {
			f(pattern)
			pos--
			continue
		}

		oldNum := pattern[pos]
		if oldNum == n+pos-k {
			pattern[pos] = -1
			pos--
			continue
		}

		if oldNum == -1 {
			pattern[pos] = pattern[pos-1] + 1
		} else {
			pattern[pos]++
		}
		pos++
	}
}
```

順列と比べてだいぶ書きやすくなりましたね。ある桁の値を増やす時、飛び飛びの増え方をすることがなく、必ず 1 増やせばいいだけなのはデカいです。ループで少しずつ増やしながら試すということがなくなっています。
ただし、左向きに繰り上がりしながら値を増やそうとする時と、繰り上げた桁を後から右向きに振り返って埋め直す時の処理が、今回は共通化できず条件分岐しています。まあそれぐらいです。

```
CombinationsWithCarrying0	  36928434 ns	        96 B	       1 allocs
CombinationsWithCarrying1	  49481598 ns	        96 B	       1 allocs
```

なんか妙に差が出てる…。

## 計測結果まとめ

```
CombinationsRecursive0   	5270823668 ns	5060925400 B	70747903 allocs
CombinationsRecursive1   	  55564969 ns	        96 B	       1 allocs
CombinationsRecursive2   	  58998589 ns	       112 B	       1 allocs
CombinationsWithSlice0   	  44367916 ns	      8256 B	       9 allocs
CombinationsWithCarrying0	  36928434 ns	        96 B	       1 allocs
CombinationsWithCarrying1	  49481598 ns	        96 B	       1 allocs
```

# 重複組合せ

<img alt="tree-graph.png" width=300px src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140384/e2f83ee1-b5fa-306b-8f67-00d37bd7c010.png">


順番前後して、先に重複組合せを取り上げます。
なぜかというと、重複組合せの列挙は組み合わせの時とほっとんど同じだからです。
組み合わせは `1 桁目の数字 < 2 桁目の数字 <  ... < k 桁目の数字` という考え方をしましたが、これを `1 桁目の数字 <= 2 桁目の数字 <=  ... <= k 桁目の数字` に変えてしまうだけで重複組合せになります。
なので組み合わせの次に並べたかったというわけです。

`[0, 1, ..., n-1]` から k 個選ぶ組み合わせにおいて x 桁目に使える数字を考えると、組合わせの時は「x-1 桁目の数字より上で、n-1-k+x 以下」でしたが、今回は「x-1 桁目の数字以上で、n以下」です。もっと簡単ですね。

## 下準備

また n と k を調整しただけですが、以下のコードで計測：

```combinatorics/dup_combi_test.go
func BenchmarkDupCombinations(b *testing.B) {
	const n = 18
	const k = 9

	doSomethingForPattern := func(pattern []int) {
		total := 0
		for i := 1; i < len(pattern); i++ {
			total += pattern[i] - pattern[i-1]
		}
	}

	targets := []struct {
		name string
		f    func()
	}{
		{"テスト対象関数の名前",
			func() {
				// テスト対象関数を用いて、[0, 1, ..., n-1]の数の中からk個選ぶ重複組み合わせを生成し、
				// 各重複組み合わせに対して`doSomethingForPattern`を行う。
			}},
		// ...
	}

	for _, target := range targets {
		b.Run(target.name, func(b *testing.B) {
			for try := 0; try < b.N; try++ {
				target.f()
			}
		})
	}
}
```

## 再帰を用いたやり方

素直なやつ：

```combinatorics/dup_combi.go
func DupCombinationsRecursive0(begin, end, k int) [][]int {
	if k == 0 {
		pattern := []int{}
		return [][]int{pattern}
	}

	ans := [][]int{}
	for num := begin; num < end; num++ {
		childPatterns := DupCombinationsRecursive0(num, end, k-1)
		for _, childPattern := range childPatterns {
			pattern := append([]int{num}, childPattern...)
			ans = append(ans, pattern)
		}
	}

	return ans
}
```

`begin` に渡す数字が `num+1` ではなく `num` になり、ループ条件 `num < end-k+1` が `num < end` になっています。そんだけ。

```
DupCombinationsRecursive0   	4282572542 ns	4187600032 B	60615826 allocs
```

そんで改良：

```combinatorics/dup_combi.go
func DupCombinationsRecursive1(n, k int, f func([]int)) {
	pattern := make([]int, k)

	var body func(pos, begin int)
	body = func(pos, begin int) {
		if pos == k {
			f(pattern)
			return
		}

		for num := begin; num < n; num++ {
			pattern[pos] = num
			body(pos+1, num)
		}
	}
	body(0, 0)
}
```

```
DupCombinationsRecursive1   	  47771265 ns	        80 B	       1 allocs
```

## スタックを用いたやり方

```combinatorics/dup_combi.go
// 順列のコードから流用
type patternNode3 struct {
	pos    int
	number int
}

func DupCombinationsWithSlice0(n, k int, f func([]int)) {
	patternNodeStack := make([]patternNode3, 1)
	pattern := make([]int, k)

	patternNodeStack[0] = patternNode3{pos: -1, number: 0}
	for len(patternNodeStack) > 0 {
		patternNode := patternNodeStack[len(patternNodeStack)-1]
		patternNodeStack = patternNodeStack[:len(patternNodeStack)-1]

		if patternNode.pos > -1 {
			pattern[patternNode.pos] = patternNode.number
		}

		if patternNode.pos == k-1 {
			f(pattern)
			continue
		}

		for num := n - 1; num >= patternNode.number; num-- {
			childNode := patternNode3{
				pos: patternNode.pos + 1, number: num,
			}
			patternNodeStack = append(patternNodeStack, childNode)
		}
	}
}
```

-1 桁目に入れるダミーの数字が -1 から 0 になってたりします。

```
DupCombinationsWithSlice0   	  42335223 ns	      8240 B	       9 allocs
```

## 繰り上がり法

```combinatorics/dup_combi.go
func DupCombinationsWithCarrying0(n, k int, f func([]int)) {
	pattern := make([]int, k)

	for {
		f(pattern)

		pos := k - 1
		for {
			if pos == -1 {
				return
			}

			oldNum := pattern[pos]
			if oldNum == n-1 {
				pos--
				continue
			}

			pattern[pos]++
			break
		}

		numToReplace := pattern[pos]
		for pos++; pos < k; pos++ {
			pattern[pos] = numToReplace
		}
	}
}

func DupCombinationsWithCarrying1(n, k int, f func([]int)) {
	pattern := make([]int, k)

	pos := k
	for pos > -1 {
		if pos == k {
			f(pattern)
			pos--
			continue
		}

		oldNum := pattern[pos]
		if oldNum == n-1 {
			pattern[pos] = -1
			pos--
			continue
		}

		if oldNum == -1 {
			pattern[pos] = pattern[pos-1]
		} else {
			pattern[pos]++
		}
		pos++
	}
}
```

`pattern` には最初の重複組み合わせをセットする必要があるんですが、最初の組み合わせが `{0, 1, 2}` のような形になるのに対し、最初の重複組合せは `{0, 0, 0}` のような形になるので、配列を生成した時点でセット完了になっており、そのためセット処理が消えました。

```
DupCombinationsWithCarrying0	  35562403 ns	        80 B	       1 allocs
DupCombinationsWithCarrying1	  48869797 ns	        80 B	       1 allocs
```

## 計測結果まとめ

```
DupCombinationsRecursive0   	4282572542 ns	4187600032 B	60615826 allocs
DupCombinationsRecursive1   	  47771265 ns	        80 B	       1 allocs
DupCombinationsWithSlice0   	  42335223 ns	      8240 B	       9 allocs
DupCombinationsWithCarrying0	  35562403 ns	        80 B	       1 allocs
DupCombinationsWithCarrying1	  48869797 ns	        80 B	       1 allocs
```

# 重複順列

<img alt="tree-graph.png" width=300px src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140384/1ff06ae5-2453-e65b-f87d-512e5efc40a9.png">


後回しにした重複順列ですが、実は一番簡単です。
なんせ、各桁は他の桁が何を使っているかを全く意識する必要がありません。
全桁独立して考えれば OK です。
もちろんチェックリストも要りません。

## 下準備

n と k を調整した計測コード：

```combinatorics/dup_perm_test.go
func BenchmarkDupPermutations(b *testing.B) {
	const n = 8
	const k = 7

	doSomethingForPattern := func(pattern []int) {
		total := 0
		for i := 1; i < len(pattern); i++ {
			total += pattern[i] - pattern[i-1]
		}
	}

	targets := []struct {
		name string
		f    func()
	}{
		{"テスト対象関数の名前",
			func() {
				// テスト対象関数を用いて、[0, 1, ..., n-1]の数の中からk個選ぶ重複順列を生成し、
				// 各重複順列に対して`doSomethingForPattern`を行う。
			}},
		// ...
	}

	for _, target := range targets {
		b.Run(target.name, func(b *testing.B) {
			for try := 0; try < b.N; try++ {
				target.f()
			}
		})
	}
}
```

## 再帰を用いたやり方

素直なやつ：

```combinatorics/dup_perm.go
func DupPermutationsRecursive0(n, k int) [][]int {
	if k == 0 {
		pattern := []int{}
		return [][]int{pattern}
	}

	ans := [][]int{}
	for num := 0; num < n; num++ {
		childPatterns := DupPermutationsRecursive0(n, k-1)
		for _, childPattern := range childPatterns {
			pattern := append([]int{num}, childPattern...)
			ans = append(ans, pattern)
		}
	}

	return ans
}
```

```
DupPermutationsRecursive0   	2145949059 ns	2020474264 B	30689223 allocs
```

改良：

```combinatorics/dup_perm.go
func DupPermutationsRecursive1(n, k int, f func([]int)) {
	pattern := make([]int, k)

	var body func(pos int)
	body = func(pos int) {
		if pos == k {
			f(pattern)
			return
		}

		for num := 0; num < n; num++ {
			pattern[pos] = num
			body(pos + 1)
		}
	}
	body(0)
}
```

```
DupPermutationsRecursive1   	  23847135 ns	        64 B	       1 allocs
```

## スタックを用いたやり方

```combinatorics/dup_perm.go
// 順列のコードから流用
type patternNode3 struct {
	pos    int
	number int
}

func DupPermutationsWithSlice0(n, k int, f func([]int)) {
	patternNodeStack := make([]patternNode3, 1)
	pattern := make([]int, k)

	patternNodeStack[0] = patternNode3{pos: -1, number: 0}
	for len(patternNodeStack) > 0 {
		patternNode := patternNodeStack[len(patternNodeStack)-1]
		patternNodeStack = patternNodeStack[:len(patternNodeStack)-1]

		if patternNode.pos > -1 {
			pattern[patternNode.pos] = patternNode.number
		}

		if patternNode.pos == k-1 {
			f(pattern)
			continue
		}

		for num := n - 1; num >= 0; num-- {
			childNode := patternNode3{
				pos: patternNode.pos + 1, number: num,
			}
			patternNodeStack = append(patternNodeStack, childNode)
		}
	}
}
```

```
DupPermutationsWithSlice0   	  23043210 ns	      2080 B	       7 allocs
```

## 繰り上がり法

N 進法そのまんまなので、「繰り上がり」のニュアンスは重複順列が一番よく表れています。

ちなみに「繰り上がった桁を後でなるべく小さい数字で埋め直す」という作業ですが、今回は繰り上がった桁の数字は必ず 0 になるので、繰り上がると分かった時にさっさと 0 を入れてしまえばあとで埋め直す必要すらないです。

```combinatorics/dup_perm.go
func DupPermutationsWithCarrying0(n, k int, f func([]int)) {
	pattern := make([]int, k)

	for {
		f(pattern)

		pos := k - 1
		for {
			if pos == -1 {
				return
			}

			oldNum := pattern[pos]
			if oldNum == n-1 {
				pattern[pos] = 0
				pos--
				continue
			}

			pattern[pos]++
			break
		}
	}
}

func DupPermutationsWithCarrying1(n, k int, f func([]int)) {
	pattern := make([]int, k)

	pos := k
	for pos > -1 {
		if pos == k {
			f(pattern)
			pos--
			continue
		}

		oldNum := pattern[pos]
		if oldNum == n-1 {
			pattern[pos] = 0
			pos--
			continue
		}

		pattern[pos]++
		pos = k // 右端に一気に飛んで良い
	}
}
```

デッドリー・シンプルですね。

```
DupPermutationsWithCarrying0	  15678811 ns	        64 B	       1 allocs
DupPermutationsWithCarrying1	  22888059 ns	        64 B	       1 allocs
```

## N 進法表記に変換するやり方

せっかくなのでちょっと特殊解を試します。

`[0, 1, ..., n-1]` から k 個選ぶ重複順列の列挙は、n 進法表記で k 桁の数字を全て並べる処理と同値です。
なので、10 進法の int をインクリメントしていきながら都度 n 進法に変換することで、重複順列を全て列挙することができます。
順列、組み合わせ、重複組み合わせは全て変則的な n 進法であり、単純な変換は難しい（多分）です。なので、重複順列の場合のみ使えるやり方になってきます。

ちなみに `n = 2` として、 2 進法への変換をビット演算で行うと、よくあるビット全探索になります。

```combinatorics/dup_perm.go
func DupPermutationsWithBaseConverting0(n, k int, f func([]int)) {
	pattern := make([]int, k)

	for deciNum := 0; deciNum < Pow(n, k); deciNum++ {
		rest := deciNum
		for pos := k - 1; pos >= 0; pos-- {
			pattern[pos] = rest % n
			rest /= n
		}
		f(pattern)
	}
}
```

```combinatorics/util.go
func Pow(base, exponent int) int {
	answer := 1
	for i := 0; i < exponent; i++ {
		answer *= base
	}
	return answer
}
```

```
DupPermutationsWithBaseConverting1	 232745482 ns	        64 B	       1 allocs
```

残念ながら他より 10 倍ぐらいかかっている模様。
やはり重複順列毎に k 桁全部の値を書き込み直しているのが痛いですね。

## 計測結果まとめ

```
DupPermutationsRecursive0         	2145949059 ns	2020474264 B	30689223 allocs
DupPermutationsRecursive1         	  23847135 ns	        64 B	       1 allocs
DupPermutationsWithSlice0         	  23043210 ns	      2080 B	       7 allocs
DupPermutationsWithCarrying0      	  15678811 ns	        64 B	       1 allocs
DupPermutationsWithCarrying1      	  22888059 ns	        64 B	       1 allocs
DupPermutationsWithBaseConverting1	 232745482 ns	        64 B	       1 allocs
```

# まとめ

実装難易度を振り返ってみると、「重複順列 < 重複組合せ <= 組み合わせ << 順列」と言えそうです。
実はここまで難しい順に進んできたことになります。
今までの順列の実装が難しく感じた人は、一旦こっちの重複順列とかの実装を読んだ方が良いかもしれませんね。

私はこの後、自分用の競プロライブラリとして、再帰を用いたやつをひと通りまとめておく予定です。（再帰のやり方が一番書きやすく、いざという時に弄りやすそうなので。）
色々実装を追求して計測して比較した後なので、「この実装で良いな」とそこそこ自信を持てるようになりました。大満足です。

TODO: 寄せられた情報によると、[フィッシャー–イェーツのシャッフル](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%83%E3%82%B7%E3%83%A3%E3%83%BC%E2%80%93%E3%82%A4%E3%82%A7%E3%83%BC%E3%83%84%E3%81%AE%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB)について調べることで、配列の中身をスワップしながら爆速で順列を列挙する方法が出てくるらしい。そのうち詳しく調べたいところ。

おわり。