はじめに
- 前回 ピーマンとハトと数学を Go 言語で試す で動的計画法で組み合わせを検索して解を出したが、最初に思いついたのは全組み合わせを出してその中から下位を検索する解法だった。
- とはいえ全組み合わせを出す方法がすぐに出てこなかったので、今回は全組み合わせを列挙する方法を実装してみる。
総当りで組み合わせを列挙する
- http://blog.shibayu36.org/entry/2016/12/22/184334 を参考に
- n 個の要素を持つ配列の組み合わせの数は 2 の n 乗個
- 0 から
2 ** n - 1までの整数を 2 進数に変換し n 桁目が n 個目の要素の選択状況として、0 が選択しない 1 が選択する、というルールに基づいて組み合わせを生成する
github.com/nirasan/algo/blob/master/powerset.go#L5
func Powerset1(nums []int) [][]int {
if len(nums) == 0 {
return [][]int{ []int{} }
}
length := int(math.Pow(2, float64(len(nums))))
result := make([][]int, length)
for i := 0; i < length; i++ {
bi := i
s := []int{}
for _, n := range nums {
if bi % 2 != 0 {
s = append(s, n)
}
bi = bi / 2
}
result[i] = s
}
return result
}
動的計画法で組み合わせを列挙する
- 組み合わせ結果配列を作り空集合だけ入れておく
- 配列の 1 要素目から順に、組み合わせ結果配列の既存の要素に当の要素を追加したものを末尾に追加していく
- この操作によって元の配列の各要素について、組み合わせに追加しない場合（結果配列の既存の要素）と組み合わせに追加した場合（結果配列の末尾に追加される要素）を適用していくことと同等になり、組み合わせに追加しない場合は常に計算済みになるので高速化が期待される。
# 初期の結果配列
[ [] ]
# 元の配列
[ 1, 2, 3 ]
# 1 要素目の操作結果
[ /* 選択しない場合の要素 */ [], /* 選択した場合の要素 */ [1] ]
# 2 要素目の操作結果
[ /* 選択しない場合の要素 */ [], [1], /* 選択した場合の要素 */ [2], [1, 2] ]
# 3 要素目の操作結果
[ /* 選択しない場合の要素 */ [], [1], [2], [1, 2], /* 選択した場合の要素 */ [3], [1, 3], [2, 3], [1, 2, 3] ]
github.com/nirasan/algo/blob/master/powerset.go#L29
func Powerset2(nums []int) [][]int {
length := int(math.Pow(2, float64(len(nums))))
result := make([][]int, length)
index := 0
result[index] = []int{}
index++
for _, n := range nums {
max := index
for i := 0; i < max; i++ {
result[index] = copyAndAppend(result[i], n)
index++
}
}
return result
}
func copyAndAppend(nums []int, n int) []int {
dst := make([]int, len(nums)+1)
copy(dst, nums)
dst[len(nums)] = n
return dst
}
結果配列を持たずに列挙する
- 総当りで列挙する解法を改造して結果配列を持たずに受け取った関数で即時処理することで高速化が期待できないかと思い実装してみた
github.com/nirasan/algo/blob/master/powerset.go#L55
func Powerset3(nums []int, f func([]int)) {
if len(nums) == 0 {
f([]int{})
}
length := int(math.Pow(2, float64(len(nums))))
for i := 0; i < length; i++ {
bi := i
s := []int{}
for _, n := range nums {
if bi % 2 != 0 {
s = append(s, n)
}
bi = bi / 2
}
f(s)
}
}
各実装の比較
ベンチマークコード
github.com/nirasan/algo/blob/master/powerset_test.go#L34
func BenchmarkPowerset_len3(b *testing.B) {
nums := []int{1, 2, 3}
b.Run("Powerset1", func(b *testing.B){
for i := 0; i < b.N; i++ {
Powerset1(nums)
}
})
b.Run("Powerset2", func(b *testing.B){
for i := 0; i < b.N; i++ {
Powerset2(nums)
}
})
b.Run("Powerset3", func(b *testing.B){
f := func(in []int) {}
for i := 0; i < b.N; i++ {
Powerset3(nums, f)
}
})
}
func BenchmarkPowerset_len10(b *testing.B) {
nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
b.Run("Powerset1", func(b *testing.B){
for i := 0; i < b.N; i++ {
Powerset1(nums)
}
})
b.Run("Powerset2", func(b *testing.B){
for i := 0; i < b.N; i++ {
Powerset2(nums)
}
})
b.Run("Powerset3", func(b *testing.B){
f := func(in []int) {}
for i := 0; i < b.N; i++ {
Powerset3(nums, f)
}
})
}
結果
$ go test -bench . -benchmem
BenchmarkPowerset_len3/Powerset1-4 2000000 647 ns/op 344 B/op 13 allocs/op
BenchmarkPowerset_len3/Powerset2-4 5000000 380 ns/op 296 B/op 8 allocs/op
BenchmarkPowerset_len3/Powerset3-4 3000000 515 ns/op 152 B/op 12 allocs/op
BenchmarkPowerset_len10/Powerset1-4 10000 206059 ns/op 122184 B/op 3654 allocs/op
BenchmarkPowerset_len10/Powerset2-4 30000 47777 ns/op 69552 B/op 1024 allocs/op
BenchmarkPowerset_len10/Powerset3-4 10000 201229 ns/op 97608 B/op 3653 allocs/op
PASS
ok github.com/nirasan/algo 12.347s
おわりに
- やはり動的計画法による列挙が最速でメモリ効率も良かった
-
Powerset1とPowerset3を比較すると結果配列を持たないことにより速度はそこまで改善されないがメモリ効率はよくはなっていた