整数 n がスライス ([ ]int) に含まれているか調べる関数 member とスライスから重複した要素を取り除く関数 removeDup を定義してください。removeDup は引数のスライスを破壊せずに新しいスライスを返すものとします。
func member(n int, buff []int) bool func removeDup(buff []int) []int
removeDup([]int{1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5}) => [1 2 3 4 5]
集合をスライス ([ ]int) で表すことにします。集合の和、集合の積、集合の差を求める関数 union, intersection, difference を定義してください。これらの関数は引数のスライスを破壊せずに新しいスライスを返すものとします。
func union(xs, ys []int) []int func intersection(xs, ys []int) []int func difference(xs, ys []int) []int
union([]int{1, 2, 3, 4}, []{3, 4, 5, 6}) => [1 2 3 4 5 6]
intersection([]int{1, 2, 3, 4}, []{3, 4, 5, 6}) => [3 4]
difference([]int{1, 2, 3, 4}, []{3, 4, 5, 6}) => [1 2]
シェルソート (shell sort) は挿入ソートの改良版ともいえる方法です。最初は遠く離れた要素間でソートを開始し、徐々に間隔を狭めていきます。最後は隣り合った要素間でソートします。つまり、単純挿入ソートと同じになります。
間隔が大きいときは要素の個数が少ないので、単純なアルゴリズムでもソートにかかる時間は少なくてすみます。間隔が小さくなると要素の個数は多くなりますが、大まかにソートされているので挿入ソートでも高速にソートすることが可能です。
9 5 3 7 6 4 2 8 最初の状態
9 6 間隔を 4 で分割する
5 4
3 8
7 2
6 9 各群をソートする
4 5
3 8
2 7
6 3 9 8 間隔を 2 で分割する
4 2 5 7
3 6 8 9 各群をソートする
2 4 5 7
3 2 6 4 8 5 9 7 間隔を 1 で分割する（単純挿入ソートと同じ）
2 3 4 5 6 7 8 9 ソート完了
図 : シェルソート
スライス ([ ]int) をシェルソートする関数 shellSort を定義してください。
整数 n を b 進数 (2 <= b <= 16) で画面 (標準出力) に表示する関数 printInt を定義してください。
func printInt(n, b int)
b 進数 (2 <= b <= 16) の文字列を整数に変換する関数 strToInt を定義してください。
func strToInt(s string, b int) int
1 から n までの数字から m 個を選ぶ順列を生成する関数 permutation を定義してください。permutation は高階関数で、生成した順列を引数の関数に渡すものとします。
func permutation(f func([]int), n, m int)
1 から n までの数字から重複を許して m 個を選ぶ順列を生成する関数 repeatPerm を定義してください。repeatPerm は高階関数で、生成した順列を引数の関数に渡すものとします。
func repeatPerm(f func([]int), n, m int)
組み合わせの数を求める関数 combNum を使わないで、「パスカルの三角形」を表示するプログラムを作ってください。
１ 0Ｃ0
／ ＼ ／ ＼
１ １ 1Ｃ0 1Ｃ1
／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ２ １ 2Ｃ0 2Ｃ1 2Ｃ2
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ３ ３ １ 3Ｃ0 3Ｃ1 3Ｃ2 3Ｃ3
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ４ ６ ４ １ 4Ｃ0 4Ｃ1 4Ｃ2 4Ｃ3 4Ｃ4
図 : パスカルの三角形
パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは (a + b)n を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 nＣr に対応します。
C>go run pascal.go [1] [1 1] [1 2 1] [1 3 3 1] [1 4 6 4 1] [1 5 10 10 5 1] [1 6 15 20 15 6 1] [1 7 21 35 35 21 7 1] [1 8 28 56 70 56 28 8 1] [1 9 36 84 126 126 84 36 9 1] [1 10 45 120 210 252 210 120 45 10 1] [1 11 55 165 330 462 462 330 165 55 11 1] [1 12 66 220 495 792 924 792 495 220 66 12 1] [1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1] [1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1] [1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1]
1 から n までの数字から m 個を選ぶ組み合わせを生成する関数 combination を定義してください。combination は高階関数で、生成した組み合わせを引数の関数に渡すものとします。
func combination(f func([]int), n, m int)
1 から n までの数字から重複を許して m 個を選ぶ組み合わせを生成する関数 repeatComb を定義してください。repeatComb は高階関数で、生成した組み合わせを引数の関数に渡すものとします。
func repeatComb(f func([]int), n, m int)
リスト : 重複要素の削除
// n がスライスに含まれているか
func member(n int, xs []int) bool {
for _, x := range xs {
if n == x { return true }
}
return false
}
// 重複要素を取り除く
func removeDup(xs []int) []int {
ys := make([]int, 0, len(xs))
for _, x := range xs {
if !member(x, ys) {
ys = append(ys, x)
}
}
return ys
}
関数 member はスライスの先頭から順番に要素と n を比較して、同じ要素があれば true を返します。見つからない場合は false を返します。関数 removeDup は member を使うと簡単です。最初に空のスライスを make で生成して変数 ys にセットします。次に、xs から要素を順番に取り出し、要素 x が ys に含まれているか member でチェックします。含まれていない場合は x を append で ys に追加します。
リスト : 和集合
func union(xs, ys []int) []int {
zs := make([]int, len(xs))
copy(zs, xs)
for _, y := range ys {
if !member(y, zs) {
zs = append(zs, y)
}
}
return zs
}
union の場合、最初に xs をコピーしたスライス zs を作ります。そして、ys から要素を順番に取り出して変数 y にセットし、それが zs に含まれているか member でチェックします。そうであれば、append で y を zs に追加します。
リスト : 積集合
func intersection(xs, ys []int) []int {
zs := make([]int, 0)
for _, x := range xs {
if member(x, ys) {
zs = append(zs, x)
}
}
return zs
}
intersection の場合、make で空のスライスを生成して変数 zs にセットします。次に、xs から要素を順番に取り出して変数 x にセットし、それが ys に含まれているか member でチェックします。そうであれば、append で zs に x を追加します。これで、重複した要素を zs に集めることができます。
リスト : 差集合
func difference(xs, ys []int) []int {
zs := make([]int, 0)
for _, x := range xs {
if !member(x, ys) {
zs = append(zs, x)
}
}
return zs
}
difference は intersection と似ています。違いは、xs の要素 x が ys に含まれていなければ、x を append で zs に追加するところです。これで、xs から ys の要素を取り除くことができます。
リスト : シェルソート
func shellSort(buff []int) []int {
k := len(buff)
gap := k / 2
for ; gap > 0; gap /= 2 {
for i := gap; i < k; i++ {
temp := buff[i]
j := i - gap
for ; j >= 0 && temp < buff[j]; j -= gap {
buff[j + gap] = buff[j]
}
buff[j + gap] = temp
}
}
return buff
}
最初のループで間隔を徐々に狭めていきます。ここでは単純に 2 で割っていくことにしました。次のループで比較する要素を取り出します。最後のループでこの要素を挿入する位置を探索します。このときの探索は隣り合った要素ではなく gap 離れた要素を比較します。
2 番目のループでは、各群を並列にソートしていることに注意してください。群のひとつの要素を取り出して位置を決めたら、次の群の要素を取り出して位置を決めています。最後に gap は 1 になるので、挿入ソートと同じになりソートが完了します。
シェルソートの場合、gap を常に奇数になるようにすると、実行速度はデータの個数 n の 1.5 乗に比例します。また、クヌース先生によると、gap の値に次の数列を用いると、シェルソートは n の 1.25 乗に比例するそうです。
gap = ..., 121, 40, 13, 4, 1
この数列は 3 倍して 1 を加えることで得られる数列を逆にしたものです。これをプログラムすると、次のようになります。
リスト : シェルソートの改良版
func shellSort1(buff []int) []int {
k := len(buff)
gap := 1
for gap < k / 9 {
gap = gap * 3 + 1
}
for ; gap > 0; gap /= 3 {
for i := gap; i < k; i++ {
temp := buff[i]
j := i - gap
for ; j >= 0 && temp < buff[j]; j -= gap {
buff[j + gap] = buff[j]
}
buff[j + gap] = temp
}
}
return buff
}
シェルソートは実装が簡単で、極端に要素数が大きくなければ十分実用になるソートだと思います。
リスト : 整数の印字
var charTable = []string{
"0", "1", "2", "3", "4", "5", "6", "7",
"8", "9", "A", "B", "C", "D", "E", "F",
}
func printIntSub(n, b int) {
if n > 0 {
printIntSub(n / b, b)
fmt.Print(charTable[n % b])
}
}
func printInt(n int, b uint) {
if b < 2 || b > 16 {
fmt.Print("error")
else if n < 0 {
fmt.Print("-")
printIntSub(-n, b)
} else if n == 0 {
fmt.Print("0")
} else {
printIntSub(n, b)
}
fmt.Println("")
}
実際の印字処理は関数 printIntSub で行います。上位の桁から表示するため再帰呼び出しを使っています。n <= 0 が再帰呼び出しの停止条件です。n が 0 でなければ、n を b で割り算して printIntSub を再帰呼び出しします。戻ってきたら、n % b の印字コードを codeTable から求めて、それを Print で出力します。printInt は引数の条件をチェックして printIntSub を呼び出すだけです。
リスト : 文字列を整数に変換する
func position(x byte, limit int, s string) int {
for i := 0; i < limit; i++ {
if s[i] == x { return i }
}
return -1
}
func strToInt(s string, b int) (int, bool) {
codeTable := "0123456789ABCDEF"
a, i, sign := 0, 0, 1
if b < 2 || b > len(codeTable) { return 0, false }
switch s[0] {
case '+':
i++
case '-':
sign = -1
i++
}
for ; i < len(s); i++ {
x := position(s[i], b, codeTable)
if x < 0 { return 0, false}
a = a * b + x
}
return sign * a, true
}
strToInt は引数 b の範囲をチェックしてから、文字列の先頭に符号 (+, -) があるかチェックします。変数 i が文字列の添字を表していて、符号がある場合は i の値を +1 します。- 符号がある場合は変数 sign を -1 に書き換えます。あとは、s から文字 (byte) を順番に取り出して、position で整数値 x に変換します。変換できない場合は 0 と false を返します。そうでなければ、累積変数 a の値を a * 10 + x に更新します。最後に sign * a と true を返します。
リスト : 順列の生成
func permSub(f func([]int), n, m int, xs []int) {
if len(xs) == m {
f(xs)
} else {
for i := 1; i <= n; i++ {
if !member(i, xs) {
permSub(f, n, m, append(xs, i))
}
}
}
}
func permutation(f func([]int), n, m int) {
permSub(f, n, m, make([]int, 0, m))
}
実際の処理は関数 permSub で行います。引数 xs に選んだ数字を格納します。xs の長さが m と等しい場合、m 個の数字を選んだので f(xs) を実行します。そうでなければ、for ループで 1 から n までの数字を変数 i にセットします。member で xs に i が含まれているかチェックして、含まれていなければ append で xs に i を追加して permSub を再帰呼び出しします。
簡単な実行例を示します。
リスト : 簡単な実行例
func main() {
p := func(xs []int) { fmt.Print(xs) }
permutation(p, 4, 4)
}
C>go run perm.go [1 2 3 4][1 2 4 3][1 3 2 4][1 3 4 2][1 4 2 3][1 4 3 2][2 1 3 4][2 1 4 3][2 3 1 4] [2 3 4 1][2 4 1 3][2 4 3 1][3 1 2 4][3 1 4 2][3 2 1 4][3 2 4 1][3 4 1 2][3 4 2 1] [4 1 2 3][4 1 3 2][4 2 1 3][4 2 3 1][4 3 1 2][4 3 2 1]
リスト : 重複順列の生成
func repeatPermSub(f func([]int), n, m int, xs []int) {
if m == 0 {
f(xs)
} else {
for i := 1; i <= n; i++ {
repeatPermSub(f, n, m - 1, append(xs, i))
}
}
}
func repeatPerm(f func([]int), n, m int) {
repeatPermSub(f, n, m, make([]int, 0, m))
}
重複順列は簡単です。数字は重複してもよいので、member で数字をチェックする必要はありません。
簡単な実行例を示します。
リスト : 簡単な実行例
func main() {
p := func(xs []int) { fmt.Print(xs) }
repeatPerm(p, 3, 3)
}
C>go run rperm.go [1 1 1][1 1 2][1 1 3][1 2 1][1 2 2][1 2 3][1 3 1][1 3 2][1 3 3][2 1 1] [2 1 2][2 1 3][2 2 1][2 2 2][2 2 3][2 3 1][2 3 2][2 3 3][3 1 1][3 1 2] [3 1 3][3 2 1][3 2 2][3 2 3][3 3 1][3 3 2][3 3 3]
パスカルの三角形は組み合わせの公式を使って作成することができます。
nC0 = nCn = 1 nCr = n-1Cr-1 + n-1Cr
公式からわかるように、nＣr の値は n-1Ｃr と n-1Ｃr-1 を足したものです。n = 0 から順番に組み合わせの数を求めて表に格納していけばいいわけです。
プログラムは次のようになります。
リスト : パスカルの三角形 (1)
func pascal(n int) {
table := make([][]int, n)
table[0] = []int{1}
table[1] = []int{1,1}
for i := 2; i < n; i++ {
table[i] = make([]int, i + 1)
table[i][0] = 1
for j := 1; j < i; j++ {
table[i][j] = table[i - 1][j - 1] + table[i - 1][j]
}
table[i][i] = 1
}
for i := 0; i < n; i++ {
fmt.Println(table[i])
}
}
変数 table に組み合わせの数を格納する 2 次元配列をセットします。talbe[i][j] は table[i - 1][j - 1] + table[i - 1][j] で求めることができます。最初に、table[0] に [1] を、table[1] に [1 1] をセットします。あとは、table にスライスをセットして、
組み合わせの数を求めていくだけです。なお、table は二次元配列ではなく一次元配列で済ますこともできます。次の図を見てください。
0 1 2 3 4 5 6
-------------------------
0 [ 1 1 1 1 1 1 1 ]
1 [ 1 1 1 1 1 1 1 ]
＼|
2 [ 1 2 1 1 1 1 1 ]
＼|＼|
3 [ 1 3 3 1 1 1 1 ]
＼|＼|＼|
4 [ 1 4 6 4 1 1 1 ]
＼|＼|＼|＼
5 [ 1 5 10 10 5 1 1 ]
＼|＼|＼|＼|＼|
6 [ 1 6 15 20 15 6 1 ]
図 : パスカルの三角形
最初にベクタの内容を 1 に初期化します。n = 0, 1 の場合はこのままで大丈夫です。あとは図のように、隣の要素を足し算するだけです。プログラムは次のようになります。
リスト : パスカルの三角形 (2)
func fill(buff []int, x int) {
for i := 0; i < len(buff); i++ {
buff[i] = x
}
}
func printPascal(n int, buff []int) {
for i := 0; i <= n; i++ {
fmt.Print(buff[i], " ")
}
fmt.Println("")
}
func pascal1(n int) {
table := make([]int, n + 1)
fill(table, 1)
printPascal(0, table)
printPascal(1, table)
for i := 2; i < n; i++ {
for j := i - 1; j > 0; j-- {
table[j] += table[j - 1]
}
printPascal(i, table)
}
}
関数 fill(ary, x) はスライス ary の全ての要素を x に書き換えます。関数 printPascal(x, table) は table の 0 番目から x 番目の要素を画面へ出力します。pascal1 はスライス table の値を書き換えていくので、table の後方から計算していくことに注意してください。前方から計算すると値がおかしくなります。
1 から 5 までの数字の中から 3 個を選ぶ組み合わせは次のようになります。
[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5],
最初に 1 を選択した場合、次は [2, 3, 4, 5] の中から 2 個を選べばいいですね。2 番目に 2 を選択したら、次は [3, 4, 5] の中から 1 個を選べばいいわけです。これで、[1, 2, 3], [1, 2, 4], [1, 2, 5] が生成されます。[2, 3, 4, 5] の中から 2 個選ぶとき、2 を選ばない場合があります。この場合は [3, 4, 5] の中から 2 個を選べばいいわけです。ここで 3 を選ぶと [1, 3, 4], [1, 3, 5] が生成できます。同様に、3 を除いた [4, 5] の中から 2 個を選ぶと [1, 4, 5] を生成することができます。
これで 1 を含む組み合わせを生成したので、次は 1 を含まない組み合わせ、つまり [2, 3, 4, 5] から 3 個を選ぶ組み合わせを生成すればいいわけです。けっきょく、この処理の考え方は組み合わせの公式と同じです。
nC0 = nCn = 1 nCr = n-1Cr-1 + n-1Cr
プログラムは次のようになります。
リスト : 組み合わせの生成
func combSub(f func([]int), n, m int, xs []int) {
if m == 0 {
f(xs)
} else if n == m {
for i := m; i > 0; i-- {
xs = append(xs, i)
}
f(xs)
} else {
combSub(f, n - 1, m, xs)
combSub(f, n - 1, m - 1, append(xs, n))
}
}
func combination(f func([]int), n, m int) {
combSub(f, n, m, make([]int, 0, m))
}
実際の処理は関数 combSub で行います。combSub は、1 から n までの数字の中から m 個を選ぶ組み合わせを生成します。選んだ要素は変数 xs のスライスに格納します。m が 0 になったら組み合わせを一つ生成できたので f(xs) を呼び出します。n が m と等しくなったならば、残りの数字 (1 から m まで) を全て選択します。for ループで 1 から m までの数字を xs に追加してから f(xs) を呼び出します。
この 2 つの条件が再帰呼び出しの停止条件になります。あとは combSub を再帰呼び出しするだけです。最初の呼び出しは数字 n を選ばない場合です。残りの数字の中から m 個の数字を選びます。最後の呼び出しが数字 n を選択する場合です。数字 n を xs に追加して、残りの数字の中から m - 1 個を選びます。
簡単な実行例を示します。
リスト : 簡単な実行例
func main() {
p := func(xs []int) { fmt.Print(xs) }
combination(p, 5, 3)
}
C>go run comb.go [3 2 1][4 2 1][4 3 1][4 3 2][5 2 1][5 3 1][5 3 2][5 4 1][5 4 2][5 4 3]
要素の順番が逆になっていますが、正常に動作しています。
リスト : 重複組み合わせの生成
func repeatCombSub(f func([]int), n, m int, xs []int) {
if m == 0 {
f(xs)
} else if n == 1 {
for i := 0; i < m; i++ {
xs = append(xs, 1)
}
f(xs)
} else {
repeatCombSub(f, n - 1, m, xs)
repeatCombSub(f, n, m - 1, append(xs, n))
}
}
func repeatComb(f func([]int), n, m int) {
repeatCombSub(f, n, m, make([]int, 0, m))
}
重複組み合わせを求める repeatComb も簡単です。実際の処理は関数 repeatCombSub で行います。2 番目の else if 節で、n が 1 の場合は 1 を m 個選びます。最後の else 節では、n を選んだあとそれを取り除かないで m - 1 個の要素を選びます。
簡単な実行例を示します。
リスト : 簡単な実行例
func main() {
p := func(xs []int) { fmt.Print(xs) }
repeatComb(p, 4, 3)
}
C>go run comb.go [1 1 1][2 1 1][2 2 1][2 2 2][3 1 1][3 2 1][3 2 2][3 3 1][3 3 2][3 3 3] [4 1 1][4 2 1][4 2 2][4 3 1][4 3 2][4 3 3][4 4 1][4 4 2][4 4 3][4 4 4]