Goで配列の順列組み合わせを列挙するプログラムを書いているときに、 配列のサイズが大きくなると、同じパターンが列挙されてしまって ちゃんと動かないという問題が発生した。
結論としては、appendの仕様を間違って理解していたために 同じSliceに対して処理をしてしまって、間違った挙動になっていた というのがオチだった。
問題のソースは以下の通り
package main import ( "fmt" ) func remove(a []int, i int) []int { o := make([]int, 0) for j := 0; j < len(a); j++ { if j == i { continue } o = append(o, a[j]) } return o } func permutation(a []int, x []int, xx [][]int) [][]int { if len(a) == 0 { xx2 := append(xx, x) fmt.Printf("%010p, cap(%2d), %v\n", x, cap(x), x) for _, x2 := range xx2 { fmt.Printf("%010p, cap(%2d), %v\n", x2, cap(x2), x2) } fmt.Scanln() return xx2 } for i, c := range a { x2 := append(x, c) fmt.Printf("x =%010p, cap(%2d), %v\n", x, cap(x), x) fmt.Printf("x2=%010p, cap(%2d), %v\n", x2, cap(x2), x2) fmt.Println() xx = permutation(remove(a, i), x2, xx) } return xx } func main() { a := []int{1, 2, 3, 4, 5, 6, 7} x := make([]int, 0) xx := make([][]int, 0) xx = permutation(a, x, xx) for i, e := range xx { fmt.Println(e) if i == 10 { break } } }
出力はこんな感じになる。fmt.Scanlnで出力を止めているので、実際にはこんな感じはならなけど。
x =0x00005904e8, cap( 0), [] x2=0xc000058058, cap( 1), [1] x =0xc000058058, cap( 1), [1] x2=0xc0000580d0, cap( 2), [1 2] x =0xc0000580d0, cap( 2), [1 2] x2=0xc000056120, cap( 4), [1 2 3] x =0xc000056120, cap( 4), [1 2 3] x2=0xc000056120, cap( 4), [1 2 3 4] x =0xc000056120, cap( 4), [1 2 3 4] x2=0xc000088240, cap( 8), [1 2 3 4 5] x =0xc000088240, cap( 8), [1 2 3 4 5] x2=0xc000088240, cap( 8), [1 2 3 4 5 6] x =0xc000088240, cap( 8), [1 2 3 4 5 6] x2=0xc000088240, cap( 8), [1 2 3 4 5 6 7] 0xc000088240, cap( 8), [1 2 3 4 5 6 7] 0xc000088240, cap( 8), [1 2 3 4 5 6 7] x =0xc000088240, cap( 8), [1 2 3 4 5] x2=0xc000088240, cap( 8), [1 2 3 4 5 7] x =0xc000088240, cap( 8), [1 2 3 4 5 7] x2=0xc000088240, cap( 8), [1 2 3 4 5 7 6] 0xc000088240, cap( 8), [1 2 3 4 5 7 6] 0xc000088240, cap( 8), [1 2 3 4 5 7 6] 0xc000088240, cap( 8), [1 2 3 4 5 7 6]
私の認識では appendは常に新しく配列を作成してくれるものだと思っていたが、実際はcapの上限までは同じ配列を使用する。
上限まで達するとcapを現在の2倍に広げてから末尾に追加する。という挙動になる。
配列のコピーが発生しているものだと思っていたので、再起関数内でappendの後に元の配列を操作するような処理を入れており
それが悪さをして、append先の配列の内容まで変わってしまっている。
これを回避するには、xx に追加するときに x の内容を別の配列にコピーしてから追加すること。
package main import ( "fmt" ) func remove(a []int, i int) []int { o := make([]int, 0) for j := 0; j < len(a); j++ { if j == i { continue } o = append(o, a[j]) } return o } func permutation(a []int, x []int, xx [][]int) [][]int { if len(a) == 0 { x2 := make([]int, len(x)) // 別の配列を作って copy(x2, x) // コピー xx2 := append(xx, x2) // コピーした配列をxxに追加する fmt.Printf("%010p, cap(%2d), %v\n", x, cap(x), x) for _, x2 := range xx2 { fmt.Printf("%010p, cap(%2d), %v\n", x2, cap(x2), x2) } fmt.Scanln() return xx2 } for i, c := range a { x2 := append(x, c) fmt.Printf("x =%010p, cap(%2d), %v\n", x, cap(x), x) fmt.Printf("x2=%010p, cap(%2d), %v\n", x2, cap(x2), x2) fmt.Println() xx = permutation(remove(a, i), x2, xx) } return xx } func main() { a := []int{1, 2, 3, 4, 5, 6, 7} x := make([]int, 0) xx := make([][]int, 0) xx = permutation(a, x, xx) for i, e := range xx { fmt.Println(e) if i == 10 { break } } }
出力を確認すると、以下のような感じになる。
x =0x00005904e8, cap( 0), [] x2=0xc0000120b0, cap( 1), [1] x =0xc0000120b0, cap( 1), [1] x2=0xc000012110, cap( 2), [1 2] x =0xc000012110, cap( 2), [1 2] x2=0xc00000a460, cap( 4), [1 2 3] x =0xc00000a460, cap( 4), [1 2 3] x2=0xc00000a460, cap( 4), [1 2 3 4] x =0xc00000a460, cap( 4), [1 2 3 4] x2=0xc00000e3c0, cap( 8), [1 2 3 4 5] x =0xc00000e3c0, cap( 8), [1 2 3 4 5] x2=0xc00000e3c0, cap( 8), [1 2 3 4 5 6] x =0xc00000e3c0, cap( 8), [1 2 3 4 5 6] x2=0xc00000e3c0, cap( 8), [1 2 3 4 5 6 7] 0xc00000e3c0, cap( 8), [1 2 3 4 5 6 7] 0xc00000e400, cap( 7), [1 2 3 4 5 6 7] x =0xc00000e3c0, cap( 8), [1 2 3 4 5] x2=0xc00000e3c0, cap( 8), [1 2 3 4 5 7] x =0xc00000e3c0, cap( 8), [1 2 3 4 5 7] x2=0xc00000e3c0, cap( 8), [1 2 3 4 5 7 6] 0xc00000e3c0, cap( 8), [1 2 3 4 5 7 6] 0xc00000e400, cap( 7), [1 2 3 4 5 6 7] 0xc00000e440, cap( 7), [1 2 3 4 5 7 6]
二次元配列の各要素のアドレスが別々のアドレスをさすようになった。
