はじめに
- 前回 は全要素での組み合わせの列挙をしてみたが、今回は要素数を指定した組み合わせの列挙を行う。
全要素の組み合わせから指定の要素数の組み合わせを抽出する
- 前回作成した全要素の組み合わせの列挙を行い、結果から指定の要素数の組み合わせを抽出する。
- 明らかに無駄が多いがとりあえず一番ナイーブな実装から。
github.com/nirasan/algo/blob/master/combination.go#L3
func Combination1(nums []int, n int) [][]int {
ps := Powerset2(nums)
result := make([][]int, CombinationCount(len(nums), n))
index := 0
for _, s := range ps {
if len(s) == n {
result[index] = s
index++
}
}
return result
}
// 中略
func CombinationCount(n, m int) int {
return Fact(n) / (Fact(n-m) * Fact(m))
}
func Fact(n int) int {
if n == 0 {
return 1
} else {
return n * Fact(n-1)
}
}
ビット操作で組み合わせのパターンを列挙する
- http://blog.livedoor.jp/dankogai/archives/51857323.html にある解法の移植
- 2 進数表現で選ぶ選ばないを表現し列挙するのは前回も使った方法
-
Combination2NextIndexによって 2 進数で特定の数だけ 1 が立っている数を順次生成することができるのでこれを利用して列挙する
github.com/nirasan/algo/blob/master/combination.go#L16
func Combination2(nums []int, n int) [][]int {
size := len(nums)
result := make([][]int, CombinationCount(len(nums), n))
bi := (1 << uint(n)) - 1
max := 1 << uint(size)
index := 0
for bi < max {
bi = Combination2NextIndex(bi)
flags := bi
s := []int{}
for _, n := range nums {
if flags%2 != 0 {
s = append(s, n)
}
flags /= 2
}
result[index] = s
index++
}
return result
}
// 中略
func Combination2NextIndex(n int) int {
// (1) 2 進数で 1 になっている一番下の桁を取得
smallest := n & -n
// (2) 1 になっている一番下の桁に 1 を足す
ripple := n + smallest
// (3) 新たに 1 になっている一番下の桁を取得
newSmallest := ripple & -ripple
// (3) / (1) で (2) の操作により増えた 0 の数（失われた 1 の数）が算出され
// - 1 することで補填するべき 1 のビット列を取得する
ones := ((newSmallest / smallest) >> 1) - 1
// ripple に ones を補填して新しいインデックスとする
return ripple | ones
}
比較
- やはり dankogai 氏のマジカルな実装が実行速度とメモリ効率ともに素晴らしい。
BenchmarkCombination_5to3/Combination1-4 500000 3334 ns/op 1736 B/op 33 allocs/op
BenchmarkCombination_5to3/Combination2-4 500000 2964 ns/op 768 B/op 30 allocs/op
BenchmarkCombination_10to3/Combination1-4 20000 104392 ns/op 72624 B/op 1025 allocs/op
BenchmarkCombination_10to3/Combination2-4 30000 45778 ns/op 9760 B/op 360 allocs/op
PASS
ok github.com/nirasan/algo 8.124s