●問題31
m 個の整数 1, 2, ..., m の順列を考えます。このとき、i 番目 (先頭要素が 1 番目) の要素が整数 i ではない順列を「完全順列」といいます。1 から m までの整数値で完全順列を生成する高階関数 perfectPerm を定義してください。
func derangement(f func([]int), int)
derangement(func(xs []int){ fmt.Println(xs) }, 3) => (画面に出力)
[2 3 1]
[3 1 2]
derangement(func(xs []int){ fmt.Println(xs) }, 4) => (画面に出力)
[2 1 4 3]
[2 3 4 1]
[2 4 1 3]
[3 1 4 2]
[3 4 1 2]
[3 4 2 1]
[4 1 2 3]
[4 3 1 2]
[4 3 2 1]
●問題32
完全順列の総数を「モンモール数 (Montmort number)」といいます。モンモール数は次の漸化式で求めることができます。
A1 = 0 A2 = 1 An = (n - 1) * (An-1 + An-2) ; n >= 3
モンモール数を多倍長整数 Int で求める関数 montmortNumber を定義してください。
func montmortNumber(n int64) *big.Int
montmortNumber(1) => 0 montmortNumber(2) => 1 montmortNumber(3) => 2 montmortNumber(4) => 9 montmortNumber(5) => 44 montmortNumber(6) => 265 montmortNumber(7) => 1854 // 高速版 montmortNumber2(10) => 1334961 montmortNumber2(20) => 895014631192902121 montmortNumber2(30) => 97581073836835777732377428235481 montmortNumber2(40) => 300158458444475693321518926221316715906770469041 montmortNumber2(50) => 11188719610782480504630258070757734324011354208865721592720336801
●問題33
バランスの取れた n 対のカッコ列を生成する高階関数 kakko を定義してください。カッコ列は ( と ) からなる列のことで、バランスが取れているカッコ列は、右カッコで閉じることができる、つまり右カッコに対応する左カッコがある状態のことをいいます。たとえば n = 1 の場合、( ) はバランスの取れたカッコ列ですが、) ( はバランスが取れていません。
func kakko(f func(string), n int)
kakko(func(x string){ fmt.Println(x) }, 3) => (画面に出力)
((()))
(()())
(())()
()(())
()()()
kakko(func(x string){ fmt.Println(x) }, 4) => (画面に出力)
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
●問題34
バランスの取れた n 対のカッコ列の総数を多倍長整数 Int で求める関数 kakkoNum を定義してください。
func kakkoNum(n int) *big.Int
kakkoNum(1) => 1 kakkoNum(2) => 2 kakkoNum(3) => 5 kakkoNum(4) => 14 kakkoNum(5) => 42 kakkoNum(6) => 132 kakkoNum(7) => 429 kakkoNum(8) => 1430 kakkoNum(9) => 4862 kakkoNum(10) => 16796 kakkoNum(30) => 3814986502092304 kakkoNum(50) => 1978261657756160653623774456 kakkoNum(100) => 896519947090131496687170070074100632420837521538745909320
●問題35
整数 n を 1 以上の自然数の和で表すことを考えます。これを「整数の分割」といいます。整数を分割するとき、同じ自然数を何回使ってもかまいませんが、並べる順序が違うだけのものは同じ分割とします。簡単な例を示します。
n = 6
6 分割 : 1 + 1 + 1 + 1 + 1 + 1
5 分割 : 1 + 1 + 1 + 1 + 2
4 分割 : 1 + 1 + 1 + 3
1 + 1 + 2 + 2
3 分割 : 1 + 1 + 4
1 + 2 + 3
2 + 2 + 2
2 分割 : 1 + 5
2 + 4
3 + 3
1 分割 : 6
6 の場合、分割の仕方は 11 通りあります。この数を「分割数」といいます。自然数 n の分割数を多倍長整数 Int で求める関数 partitionNumber を定義してください。
func partitionNumber(n int64) *big.Int
partitionNumber(1) => 1 partitionNumber(2) => 2 partitionNumber(3) => 3 partitionNumber(4) => 5 partitionNumber(5) => 7 partitionNumber(6) => 11 partitionNumber(7) => 15 partitionNumber(8) => 22 partitionNumber(10) => 42 // 高速版 partitionNumber2(50) => 204226 partitionNumber2(1000) => 24061467864032622473692149727991
●問題36
整数 n の分割の仕方をすべて求める高階関数 partitionOfInt を定義してください。
partitionOfInt(f func([]int), int)
partitionOfInt(func(xs []int) { fmt.Println(xs) }, 6) => (画面に出力)
[6]
[5 1]
[4 2]
[4 1 1]
[3 3]
[3 2 1]
[3 1 1 1]
[2 2 2]
[2 2 1 1]
[2 1 1 1 1]
[1 1 1 1 1 1]
●問題37
スライスで表した集合 ls を分割することを考えます。たとえば、集合 [1 2 3] は次のように分割することができます。
1 分割 : [[1 2 3]] 2 分割 : [[1 2] [3]], [[1 3] [2]], [[1] [2 3]] 3 分割 ; [[1] [2] [3]]
このように、分割した集合 xs は元の集合 ls の部分集合になります。分割した部分集合の積は空集合になり、分割した部分集合のすべての和を求めると元の集合になります。
ls の分割の仕方をすべて求める関数 parititon_of_set ls を定義してください。
func partitionOfSet(f func([][]int), xs []int)
partitionOfSet(func(xs [][]int){ fmt.Println(xs) }, []int{1,2,3}) => (画面に出力)
[[1 2 3]]
[[1 2] [3]]
[[1 3] [2]]
[[1] [2 3]]
[[1] [2] [3]]
partitionOfSet(func(xs [][]int){ fmt.Println(xs) }, []int{1,2,3,4}) => (画面に出力)
[[1 2 3 4]]
[[1 2 3] [4]]
[[1 2 4] [3]]
[[1 2] [3 4]]
[[1 2] [3] [4]]
[[1 3 4] [2]]
[[1 3] [2 4]]
[[1 3] [2] [4]]
[[1 4] [2 3]]
[[1] [2 3 4]]
[[1] [2 3] [4]]
[[1 4] [2] [3]]
[[1] [2 4] [3]]
[[1] [2] [3 4]]
[[1] [2] [3] [4]]
●問題38
集合を分割する方法の総数を「ベル数 (Bell Number)」といい、次の漸化式で求めることができます。
B(0) = 1
n
B(n+1) = ΣnＣk * B(k) ; n >= 1
k=0
ベル数を多倍長整数 Int で求める関数 bellNumber を定義してください。
func bellNumber(n int64) *big.Int
bellNumber(0) => 1 bellNumber(1) => 1 bellNumber(2) => 2 bellNumber(3) => 5 bellNumber(4) => 15 bellNumber(5) => 52 bellNumber(10) => 115975 // 高速版 bellNumber2(20) => 51724158235372 bellNumber2(40) => 157450588391204931289324344702531067 bellNumber2(60) => 976939307467007552986994066961675455550246347757474482558637
●問題39
k 個の要素をもつ集合 ls を要素数が等しい m 個の部分集合に分割することを考えます。部分集合の要素数 n は k / m になります。分割の仕方をすべて求める高階関数 groupPartition を定義してください。
func groupPartition(f func([][]int), n, m int, ls []int)
groupPartition(func(xs [][]int){ fmt.Println(xs) }, 2, 2, []int{1,2,3,4}) => (画面に表示)
[[1 2] [3 4]]
[[1 3] [2 4]]
[[1 4] [2 3]]
groupPartition(func(xs [][]int){ fmt.Println(xs) }, 2, 3, []int{1,2,3,4,5,6}) => (画面に表示)
[[1 2] [3 4] [5 6]]
[[1 2] [3 5] [4 6]]
[[1 2] [3 6] [4 5]]
[[1 3] [2 4] [5 6]]
[[1 3] [2 5] [4 6]]
[[1 3] [2 6] [4 5]]
[[1 4] [2 3] [5 6]]
[[1 5] [2 3] [4 6]]
[[1 6] [2 3] [4 5]]
[[1 4] [2 5] [3 6]]
[[1 4] [2 6] [3 5]]
[[1 5] [2 4] [3 6]]
[[1 6] [2 4] [3 5]]
[[1 5] [2 6] [3 4]]
[[1 6] [2 5] [3 4]]
●問題40
集合を groupPartition で分割するとき、その仕方の総数を多倍長整数 Int で求める関数 groupPartitionNumber を定義してください。
func groupPartitionNumber(n, m int64) *big.Int
引数 n は部分集合の要素数、m は部分集合の個数です。
groupPartitionNumber(2, 2) => 3 groupPartitionNumber(2, 3) => 15 groupPartitionNumber(3, 3) => 280 groupPartitionNumber(3, 4) => 15400 groupPartitionNumber(3, 5) => 1401400
●解答31
リスト : 完全順列
// n と等しい要素があるか
func member(n int, xs []int) bool {
for _, x := range xs {
if n == x {
return true
}
}
return false
}
func permSub(f func([] int), n int, a []int) {
if len(a) == n {
f(a)
} else {
for i := 1; i <= n; i++ {
if i != len(a) + 1 && !member(i, a) {
permSub(f, n, append(a, i))
}
}
}
}
func derangement(f func([]int), n int) {
perfectSub(f, n, make([]int, 0, n))
}
実際の処理は関数 permSub で行います。1 から n までの数字を n 個選ぶ順列を生成する処理で、数字 i が len(a) + 1 と等しい場合は数字 i を選択しません。len(a) が n と等しい場合は n 個の数字を選んだので f(a) を実行します。これで完全順列を生成することができます。
●解答32
リスト : 完全順列の総数
func montmortNumber(n int64) *big.Int {
switch {
case n == 1: return big.NewInt(0)
case n == 2: return big.NewInt(1)
default:
// (n - 1) * montmortNumber(n - 1) + montmortNumber(n - 2)
a := montmortNumber(n - 1)
a.Add(a, montmortNumber(n - 2))
a.Mul(a, big.NewInt(n - 1))
return a
}
}
// 別解
func montmortNumber2(n int64) *big.Int {
a := big.NewInt(0)
b := big.NewInt(1)
c := big.NewInt(0)
for i := int64(1); i < n; i++ {
// a, b = b, (i + 1) * (a + b)
c.Set(a)
a.Set(b)
b.Add(c, b)
b.Mul(b, big.NewInt(i + 1))
}
return a
}
関数 montmortNumber は公式をそのままプログラムしただけです。二重再帰になっているので、実行速度はとても遅くなります。これを繰り返しに変換すると別解のようになります。考え方はフィボナッチ数列と同じです。変数 a に i 番目の値を、b に i + 1 番目の値を保存しておきます。すると、i + 2 番目の値は (i + 1) * (a + b) で計算することができます。あとは、b の値を a に、新しい値を b にセットして処理を繰り返すだけです。
●解答33
リスト : カッコ列の生成
func kakkoSub(f func(string), x, y, m int, a string) {
if x == y && x == m {
f(a)
} else {
if x < m {
kakkoSub(f, x + 1, y, m, a + "(")
}
if y < x {
kakkoSub(f, x, y + 1, m, a + ")")
}
}
}
func kakko(f func(string), m int) {
kakkoSub(f, 0, 0, m, "")
}
カッコ列の生成は簡単です。関数 kakkoSub の引数 x が左カッコの個数、引数 y が右カッコの個数を表します。引数 a は累積変数でカッコ列を表す文字列です。
バランスの取れたカッコ列の場合、x, y, m には y <= x <= m の関係が成り立ちます。x == y == m の場合、カッコ列がひとつ完成しました。引数の関数 f を呼び出します。そうでなければ、kakkoSub を再帰呼び出しします。x < m であれば左カッコを追加し、y < x であれば右カッコを追加します。これでカッコ列を生成することができます。
●解答34
カタラン数 - Wikipedia によると、カッコ列の総数は「カタラン数 (Catalan number)」になるとのことです。カタラン数は次に示す公式で求めることができます。
(2n)!
Ｃn = ----------
(n+1)!n!
これをそのままプログラムしてもいいのですが、それではちょっと面白くないので別な方法でプログラムを作ってみましょう。カタラン数は次に示す経路図において、A から B までの最短距離の道順を求めるとき、対角線を超えないものの総数に一致します。
図 : 道順の総数の求め方
A からある地点にいたる最短距離の道順の総数は、左隣と真下の地点の値を足したものになります。一番下の地点は 1 で、対角線を越えた地点は 0 になります。あとは下から順番に足し算していけば、A から B までの道順の総数を求めることができます。上図の場合はカラタン数 Ｃ4 に相当し、その値は 14 となります。
プログラムはスライスを使うと簡単です。次の図を見てください。
0 : [1, 1, 1, 1, 1] 1 : [1, 1, 1, 1, 1,] 2 : [1, 1, 1+1=2, 2+1=3, 3+1=4] => [1, 1, 2, 3, 4] 3 : [1, 1, 2, 3+2=5, 5+4=9] => [1, 1, 2, 5, 9] 4 : [1, 1, 2, 5, 5+9=14] => [1, 1, 2, 5, 14]
上図は Ｃn (n = 4) を求める場合です。大きさが n + 1, 要素の値が 1 のベクタを用意します。n = 0, 1 の場合は n 番目の要素をそのまま返します。n が 2 よりも大きい場合、変数 i を 2 に初期化して、i - 1 番目以降の要素の累積和を求めます。
たとえば i = 2 の場合、2 番目の要素は 1 番目の要素と自分自身を加算した値 2 になります。3 番目の要素は 2 番目の要素と自分自身を足した値 3 になり、4 番目の要素は 3 + 1 = 4 になります。次に i を +1 して同じことを繰り返します。3 番目の要素は 2 + 3 = 5 になり、4 番目の要素は 5 + 4 = 9 になります。i = 4 のとき、4 番目の要素は 5 + 9 = 14 となり、Ｃ4 の値を求めることができました。
プログラムは次のようになります。
リスト : カッコ列の総数
func kakkoNum(n int) *big.Int {
table := make([]*big.Int, n + 1)
for i := 0; i <= n; i++ {
table[i] = big.NewInt(1)
}
for i := 2; i <= n; i++ {
for j := i; j <= n; j++ {
table[j].Add(table[j], table[j - 1])
}
}
return table[n]
}
説明したことをそのままプログラムしただけなので、とくに難しいところはないと思います。
●解答35
6 の場合、分割の仕方は上図のように 11 通りあります。分割の仕方を列挙する場合、整数 n から k 以下の整数を選んでいくと考えてください。まず、6 から 6 を選びます。すると、残りは 0 になるので、これ以上整数を分割することはできません。次に、6 から 5 を選びます。残りは 1 になるので、1 を選ぶしか方法はありません。
次に、4 を選びます。残りは 2 になるので、2 から 2 以下の整数を分割する方法になります。2 から 2 を選ぶと残りは 0 になるので 2 が得られます。1 を選ぶと残りは 1 になるので、1 + 1 が得られます。したがって、4 + 2, 4 + 1 + 1 となります。同様に、6 から 3 を選ぶと、残りは 3 から 3 以下の整数を選ぶ方法になります。
6 から 2 以下の整数を選ぶ方法は、残り 4 から 2 以下の整数を選ぶ方法になり、そこで 2 を選ぶと 2 から 2 以下の整数を選ぶ方法になります。1 を選ぶと 4 から 1 以下の整数を選ぶ方法になりますが、これは 1 通りしかありません。最後に 6 から 1 を選びますが、これも 1 通りしかありません。これらをすべて足し合わせると 11 通りになります。
整数 n を k 以下の整数で分割する総数を求める関数を p(n, k) とすると、p(n, k) は次のように定義することができます。
p(n, k) = 0 ; n < 0 または k < 1 p(n, k) = 1 ; n = 0 または k = 1 p(n, k) = p(n - k, k) + p(n, k - 1)
たとえば、p(6, 6) は次のように計算することができます。
p(6, 6) => p(0, 6) + p(6, 5)
=> 1 + p(1, 5) + p(6, 4)
=> 1 + 1 + p(2, 4) + p(6, 3)
=> 1 + 1 + 2 + 7
=> 11
p(2, 4) => p(-2, 4) + p(2, 3)
=> 0 + p(-1, 3) + p(2, 2)
=> 0 + 0 + p(0, 2) + p(2, 1)
=> 0 + 0 + 1 + 1
=> 2
p(6, 3) => p(3, 3) + p(6, 2)
=> p(0, 3) + p(3, 2) + p(4, 2) + p(6, 1)
=> 1 + p(1, 2) + p(3, 1) + p(2, 2) + p(4, 1) + 1
=> 1 + 1 + 1 + p(0, 2) + p(2, 1) + 1 + 1
=> 1 + 1 + 1 + 1 + 1 + 1 + 1
=> 7
分割数を求める関数 partitionNumber は、関数 p(n, k) を使うと次のようにプログラムすることができます。
リスト : 分割数
func partNum(n, k int64) *big.Int {
if n < 0 || k < 1 {
return big.NewInt(0)
} else if n <= 1 || k == 1 {
return big.NewInt(1)
} else {
x := partNum(n - k, k)
return x.Add(x, partNum(n, k - 1))
}
}
func partitionNumber(n int) *big.Int {
return partNum(int64(n), int64(n))
}
関数 partNum は p(n, k) の定義をそのままプログラムしただけです。ただし、このプログラムは二重再帰で何度も同じ値を求めているため実行速度はとても遅くなります。
動的計画法を使うと、大きな値でも高速に計算することができます。次の図を見てください。
k 1 : [1, 1, 1, 1, 1, 1, 1] 2 : [1, 1, 1+1=2, 1+1=2, 2+1=3, 2+1=3, 3+1=4] => [1, 1, 2, 2, 3, 3, 4] 3: [1, 1, 2, 1+2=3, 1+3=4, 2+3=5, 3+4=7] => [1, 1, 2, 3, 4, 5, 7] 4: [1, 1, 2, 3, 1+4=4, 1+5=6, 2+7=9] => [1, 1, 2, 3, 5, 6, 9 5: [1, 1, 2, 3, 5, 1+6=7, 1+9=10] => [1, 1, 2, 3, 5, 7, 10] 6: [1, 1, 2, 3, 5, 7, 10+1=11] => [1, 1, 2, 3, 5, 7, 11]
大きさ n + 1 のスライスを用意します。スライスの添字が n を表していて、p(n, 1) から順番に値を求めていきます。p(n, 1) の値は 1 ですから、スライスの要素は 1 に初期化します。次に、p(n, 2) の値を求めます。定義により p(n, 2) = p(n - 2, 2) + p(n, 1) なので、2 番目以降の要素に n - 2 番目の要素を加算すれば求めることができます。あとは、k の値をひとつずつ増やして同様の計算を行えば p(n, n) の値を求めることができます。
プログラムは次のようになります。
リスト : 分割数 (動的計画法)
func partitionNumber2(n int) *big.Int {
a := make([]*big.Int, n + 1)
for i := 0; i <= n; i++ {
a[i] =big.NewInt(1)
}
for k := 2; k <= n; k++ {
for m := k; m <= n; m++ {
a[m].Add(a[m], a[m - k])
}
}
return a[n]
}
説明をそのままプログラムしただけなので、とくに難しいところはないと思います。
●解答36
リスト : 整数の分割
// 要素が x で大きさが n のスライスを生成する
func makeSlice(n, x int) []int {
a := make([]int, n)
for i := 0; i < n; i++ {
a[i] = x
}
return a
}
func partInt(f func([]int), n, k int, a []int) {
switch {
case n == 0: f(a)
case n == 1: f(append(a, 1))
case k == 1: f(append(a, makeSlice(n, 1)...))
default:
if n - k >= 0 {
partInt(f, n - k, k, append(a, k))
}
partInt(f, n, k - 1, a)
}
}
func partitionOfInt(f func([]int), n int) {
partInt(f, n, n, make([]int, 0))
}
基本的な考え方は partitionNumber と同じです。関数 partInt は選んだ数値を累積変数 a のスライスに格納していくだけです。n が 0 の場合は f(a) を評価し、n が 1 の場合は a に 1 を追加してから f を評価します。k が 1 の場合は makeSlice で要素が 1 で長さが n のスライスを作成します。そして、それを append で a と連結してから f を評価します。
●解答37
集合を分割するアルゴリズムは簡単です。たとえば、n -1 個の要素 x1, ..., xn-1 を持つ集合を分割したところ、i 個の部分集合 S1, ..., Si が生成されたとしましょう。ここに、n 番目の要素 xn を追加すると、要素が n 個の集合を分割することができます。
新しい要素を追加する場合は次に示す手順で行います。
- 部分集合 Sk (k = 1 から i まで) に要素 xn を追加する
- 新しい部分集合 Si+1 (要素が xn だけの集合) を生成する
簡単な例を示しましょう。次の図を見てください。
部分集合を格納するスライスを用意します。最初、部分集合は空集合なので空スライスに初期化します。次に、要素 1 を追加します。部分集合は空スライスなので、手順 1 は適用できません。手順 2 を適用して新しい部分集合 [1] を追加します。
次に要素 2 を追加します。[[1]] に 手順 1 を適用すると、部分集合 [1] に要素を追加して [[1 2]] になります。手順 2 を適用すると、新しい部分集合 [2] を追加して [[1] [2]] になります。最後に 3 を追加します。[[1 2]] に手順 1 を適用すると [[1 2 3]] に、手順 2 を適用すると [[1 2] [3]] になります。[[1] [2]] に手順 1 を適用すると [[1 3] [2]] と [[1] [2 3]] になり、手順 2 を適用すると [[1] [2] [3]] になります。
このように、簡単な方法で集合を分割することができます。実際にプログラムを作る場合、上図を木と考えて、深さ優先で木をたどると簡単です。次のリストを見てください。
リスト : 集合の分割
func partSub(f func([][]int), ls []int, a [][]int) {
if len(ls) == 0 {
f(a)
} else {
for i := 0; i < len(a); i++ {
save := a[i]
a[i] = append(a[i], ls[0])
partSub(f, ls[1:], a)
a[i] = save
}
b := make([]int, 1)
b[0] = ls[0]
partSub(f, ls[1:], append(a, b))
}
}
func partitionOfSet(f func([][]int), ls []int) {
a := make([][]int, 0)
b := make([]int, 1)
b[0] = ls[0]
partSub(f, ls[1:], append(a, b))
}
実際の処理は関数 partSub で行います。生成した部分集合は累積変数 a に格納します。ls が空スライスの場合、追加する要素がなくなったので f(a) を評価します。要素がある場合、i 番目の部分集合に要素 ls[0] を追加します。a[i] の値を破壊的に書き換えるので、変数 save に a[i] の値を保存しておきます。そして、再帰呼び出しから戻ってきたら a[i] の値を save に戻します。すべての部分集合に要素を追加したら、ls[0] を要素として持つ部分集合を生成して累積変数 a に追加します。
●解答38
リスト : ベル数
// 組み合わせの数
func combinationNumber(n, r int64) *big.Int {
if n == r || r == 0 {
return big.NewInt(1)
} else {
a := combinationNumber(n, r - 1)
a.Mul(a, big.NewInt(n - r + 1))
a.Div(a, big.NewInt(r))
return a
}
}
func bellNumber(n int) *big.Int {
bs := make([]*big.Int, 1, n + 1)
bs[0] = big.NewInt(1)
for i := 0; i < n; i++ {
a := big.NewInt(0)
for k, x := range bs {
c := combinationNumber(int64(i), int64(k))
c.Mul(x, c)
a.Add(a, c)
}
bs = append(bs, a)
}
return bs[len(bs) - 1]
}
bellNumber は公式をそのままプログラムするだけです。累積変数 bs にベル数を格納します。nＣk は関数 combinationNumber で求めます。次の for ループで nＣk * B(k) の総和を計算します。あとは、その値を append で bs に追加するだけです。
●解答39
リスト : 集合のグループ分け
func groupPartSub(f func([][]int), ls []int, n, m int, a [][]int) {
if len(ls) == 0 {
f(a)
} else {
for i := 0; i < len(a); i++ {
if len(a[i]) < n {
save := a[i]
a[i] = append(a[i], ls[0])
groupPartSub(f, ls[1:], n, m, a)
a[i] = save
}
}
if len(a) < m {
b := make([]int, 1)
b[0] = ls[0]
groupPartSub(f, ls[1:], n, m, append(a, b))
}
}
}
func groupPartition(f func([][]int), n, m int, ls []int) {
a := make([][]int, 0)
b := make([]int, 1)
b[0] = ls[0]
groupPartSub(f, ls[1:], n, m, append(a, b))
}
groupPartition は partitionOfSet を改造するだけで簡単に作成することができます。生成する部分集合の大きさを n に、部分集合の個数を m に制限するだけです。i 番目の部分集合に要素を追加する場合、len(a[i]) が n 未満であることをチェックします。新しい部分集合を追加する場合、len(a) が m 未満であることをチェックします。これで集合をグループに分けることができます。
●解答40
グループ分けの総数は次の式で求めることができます。
k = n * m kＣn * k-nＣn * k-2*nＣn * ... * 2*nＣn * nＣn / m!
たとえば、n = 3, m = 5 の場合は次のようになります。
15Ｃ3 * 12Ｃ3 * 9Ｃ3 * 6Ｃ3 * 3Ｃ3 / 5! = 1401400
これをそのままプログラムすると次のようになります。
リスト : グループ分けの総数
// 階乗
func fact(n int64) *big.Int {
a := big.NewInt(1)
for ; n > 0; n-- {
a.Mul(a, big.NewInt(n))
}
return a
}
func groupPartitionNumber(n, m int64) *big.Int {
a := big.NewInt(1)
for k := n * m; k > 0; k -= n {
a.Mul(a, combinationNumber(k, n))
}
return a.Div(a, fact(m))
}
階乗は関数 fact で、組み合わせの個数は関数 combinationNumber で計算します。要素の個数を変数 k にセットし、combinationNumber(k, n) の返り値を累積変数 a に 乗算します。あとは k から n を減算し、k が 0 でなければ処理を繰り返すだけです。最後に a / fact(m) を計算して返します。
●プログラムリスト
//
// yagp04.go : Yet Another Golang Problems
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import (
"fmt"
"math/big"
)
//
// P31
//
// n と等しい要素があるか
func member(n int, xs []int) bool {
for _, x := range xs {
if n == x {
return true
}
}
return false
}
func permSub(f func([] int), n int, a []int) {
if len(a) == n {
f(a)
} else {
for i := 1; i <= n; i++ {
if i != len(a) + 1 && !member(i, a) {
permSub(f, n, append(a, i))
}
}
}
}
func derangement(f func([]int), n int) {
permSub(f, n, make([]int, 0, n))
}
// P32
func montmortNumber(n int64) *big.Int {
switch {
case n == 1: return big.NewInt(0)
case n == 2: return big.NewInt(1)
default:
// (n - 1) * montmortNumber(n - 1) + montmortNumber(n - 2)
a := montmortNumber(n - 1)
a.Add(a, montmortNumber(n - 2))
a.Mul(a, big.NewInt(n - 1))
return a
}
}
// 別解
func montmortNumber2(n int64) *big.Int {
a := big.NewInt(0)
b := big.NewInt(1)
c := big.NewInt(0)
for i := int64(1); i < n; i++ {
// a, b = b, (i + 1) * (a + b)
c.Set(a)
a.Set(b)
b.Add(c, b)
b.Mul(b, big.NewInt(i + 1))
}
return a
}
// P33
func kakkoSub(f func(string), x, y, m int, a string) {
if x == y && x == m {
f(a)
} else {
if x < m {
kakkoSub(f, x + 1, y, m, a + "(")
}
if y < x {
kakkoSub(f, x, y + 1, m, a + ")")
}
}
}
func kakko(f func(string), m int) {
kakkoSub(f, 0, 0, m, "")
}
// P34
func kakkoNum(n int) *big.Int {
table := make([]*big.Int, n + 1)
for i := 0; i <= n; i++ {
table[i] = big.NewInt(1)
}
for i := 2; i <= n; i++ {
for j := i; j <= n; j++ {
table[j].Add(table[j], table[j - 1])
}
}
return table[n]
}
// P35
func partNum(n, k int64) *big.Int {
if n < 0 || k < 1 {
return big.NewInt(0)
} else if n <= 1 || k == 1 {
return big.NewInt(1)
} else {
x := partNum(n - k, k)
return x.Add(x, partNum(n, k - 1))
}
}
func partitionNumber(n int) *big.Int {
return partNum(int64(n), int64(n))
}
func partitionNumber2(n int) *big.Int {
a := make([]*big.Int, n + 1)
for i := 0; i <= n; i++ {
a[i] =big.NewInt(1)
}
for k := 2; k <= n; k++ {
for m := k; m <= n; m++ {
a[m].Add(a[m], a[m - k])
}
}
return a[n]
}
//
// P36
//
// 要素が x で大きさが n のスライスを生成する
func makeSlice(n, x int) []int {
a := make([]int, n)
for i := 0; i < n; i++ {
a[i] = x
}
return a
}
func partInt(f func([]int), n, k int, a []int) {
switch {
case n == 0: f(a)
case n == 1: f(append(a, 1))
case k == 1: f(append(a, makeSlice(n, 1)...))
default:
if n - k >= 0 {
partInt(f, n - k, k, append(a, k))
}
partInt(f, n, k - 1, a)
}
}
func partitionOfInt(f func([]int), n int) {
partInt(f, n, n, make([]int, 0))
}
//
// P37
//
func partSub(f func([][]int), ls []int, a [][]int) {
if len(ls) == 0 {
f(a)
} else {
for i := 0; i < len(a); i++ {
save := a[i]
a[i] = append(a[i], ls[0])
partSub(f, ls[1:], a)
a[i] = save
}
b := make([]int, 1)
b[0] = ls[0]
partSub(f, ls[1:], append(a, b))
}
}
func partitionOfSet(f func([][]int), ls []int) {
a := make([][]int, 0)
b := make([]int, 1)
b[0] = ls[0]
partSub(f, ls[1:], append(a, b))
}
//
// P38
//
// 組み合わせの数
func combinationNumber(n, r int64) *big.Int {
if n == r || r == 0 {
return big.NewInt(1)
} else {
a := combinationNumber(n, r - 1)
a.Mul(a, big.NewInt(n - r + 1))
a.Div(a, big.NewInt(r))
return a
}
}
func bellNumber(n int) *big.Int {
bs := make([]*big.Int, 1, n + 1)
bs[0] = big.NewInt(1)
for i := 0; i < n; i++ {
a := big.NewInt(0)
for k, x := range bs {
c := combinationNumber(int64(i), int64(k))
c.Mul(x, c)
a.Add(a, c)
}
bs = append(bs, a)
}
return bs[len(bs) - 1]
}
//
// P39
//
func groupPartSub(f func([][]int), ls []int, n, m int, a [][]int) {
if len(ls) == 0 {
f(a)
} else {
for i := 0; i < len(a); i++ {
if len(a[i]) < n {
save := a[i]
a[i] = append(a[i], ls[0])
groupPartSub(f, ls[1:], n, m, a)
a[i] = save
}
}
if len(a) < m {
b := make([]int, 1)
b[0] = ls[0]
groupPartSub(f, ls[1:], n, m, append(a, b))
}
}
}
func groupPartition(f func([][]int), n, m int, ls []int) {
a := make([][]int, 0)
b := make([]int, 1)
b[0] = ls[0]
groupPartSub(f, ls[1:], n, m, append(a, b))
}
//
// P40
//
// 階乗
func fact(n int64) *big.Int {
a := big.NewInt(1)
for ; n > 0; n-- {
a.Mul(a, big.NewInt(n))
}
return a
}
func groupPartitionNumber(n, m int64) *big.Int {
a := big.NewInt(1)
for k := n * m; k > 0; k -= n {
a.Mul(a, combinationNumber(k, n))
}
return a.Div(a, fact(m))
}
// 簡単なテスト
func main() {
fmt.Println("----- P31 -----")
derangement(func(xs []int){ fmt.Println(xs) }, 3)
derangement(func(xs []int){ fmt.Println(xs) }, 4)
fmt.Println("----- P32 -----")
for i := 1; i <= 7; i++ {
fmt.Println(i, ":", montmortNumber(int64(i)))
}
for i := 10; i <= 50; i += 10 {
fmt.Println(i, ":", montmortNumber2(int64(i)))
}
fmt.Println("----- P33 -----")
kakko(func(x string){ fmt.Println(x) }, 3)
kakko(func(x string){ fmt.Println(x) }, 4)
fmt.Println("----- P34 -----")
for i := 1; i <= 10; i++ {
fmt.Println(i, ":", kakkoNum(i))
}
fmt.Println("30 :", kakkoNum(30))
fmt.Println("50 :", kakkoNum(50))
fmt.Println("100 :", kakkoNum(100))
fmt.Println("----- P35 -----")
for i := 1; i <= 10; i++ {
fmt.Println(i, ":", partitionNumber(i))
}
fmt.Println("50 :", partitionNumber2(50))
fmt.Println("100 :", partitionNumber2(100))
fmt.Println("1000 :", partitionNumber2(1000))
fmt.Println("----- P36 -----")
partitionOfInt(func(xs []int) { fmt.Println(xs) }, 5)
partitionOfInt(func(xs []int) { fmt.Println(xs) }, 6)
fmt.Println("----- P37 -----")
partitionOfSet(func(xs [][]int){ fmt.Println(xs) }, []int{1,2,3})
partitionOfSet(func(xs [][]int){ fmt.Println(xs) }, []int{1,2,3,4})
fmt.Println("----- P38 -----")
for i := 0; i <= 10; i++ {
fmt.Println(i, ":", bellNumber(i))
}
for i := 20; i <= 80; i += 20 {
fmt.Println(i, ":", bellNumber(i))
}
fmt.Println("----- P39 -----")
groupPartition(func(xs [][]int){ fmt.Println(xs) }, 2, 2, []int{1,2,3,4})
groupPartition(func(xs [][]int){ fmt.Println(xs) }, 2, 3, []int{1,2,3,4,5,6})
fmt.Println("----- P40 -----")
fmt.Println(groupPartitionNumber(2, 2))
fmt.Println(groupPartitionNumber(2, 3))
fmt.Println(groupPartitionNumber(3, 3))
fmt.Println(groupPartitionNumber(3, 4))
fmt.Println(groupPartitionNumber(3, 5))
}
●実行結果
----- P31 ----- [2 3 1] [3 1 2] [2 1 4 3] [2 3 4 1] [2 4 1 3] [3 1 4 2] [3 4 1 2] [3 4 2 1] [4 1 2 3] [4 3 1 2] [4 3 2 1] ----- P32 ----- 1 : 0 2 : 1 3 : 2 4 : 9 5 : 44 6 : 265 7 : 1854 10 : 1334961 20 : 895014631192902121 30 : 97581073836835777732377428235481 40 : 300158458444475693321518926221316715906770469041 50 : 11188719610782480504630258070757734324011354208865721592720336801 ----- P33 ----- ((())) (()()) (())() ()(()) ()()() (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()() ----- P34 ----- 1 : 1 2 : 2 3 : 5 4 : 14 5 : 42 6 : 132 7 : 429 8 : 1430 9 : 4862 10 : 16796 30 : 3814986502092304 50 : 1978261657756160653623774456 100 : 896519947090131496687170070074100632420837521538745909320 ----- P35 ----- 1 : 1 2 : 2 3 : 3 4 : 5 5 : 7 6 : 11 7 : 15 8 : 22 9 : 30 10 : 42 50 : 204226 100 : 190569292 1000 : 24061467864032622473692149727991 ----- P36 ----- [5] [4 1] [3 2] [3 1 1] [2 2 1] [2 1 1 1] [1 1 1 1 1] [6] [5 1] [4 2] [4 1 1] [3 3] [3 2 1] [3 1 1 1] [2 2 2] [2 2 1 1] [2 1 1 1 1] [1 1 1 1 1 1] ----- P37 ----- [[1 2 3]] [[1 2] [3]] [[1 3] [2]] [[1] [2 3]] [[1] [2] [3]] [[1 2 3 4]] [[1 2 3] [4]] [[1 2 4] [3]] [[1 2] [3 4]] [[1 2] [3] [4]] [[1 3 4] [2]] [[1 3] [2 4]] [[1 3] [2] [4]] [[1 4] [2 3]] [[1] [2 3 4]] [[1] [2 3] [4]] [[1 4] [2] [3]] [[1] [2 4] [3]] [[1] [2] [3 4]] [[1] [2] [3] [4]] ----- P38 ----- 0 : 1 1 : 1 2 : 2 3 : 5 4 : 15 5 : 52 6 : 203 7 : 877 8 : 4140 9 : 21147 10 : 115975 20 : 51724158235372 40 : 157450588391204931289324344702531067 60 : 976939307467007552986994066961675455550246347757474482558637 80 : 991267988808424794443839434655920239360814764000951599022939879419136287216681744888844 ----- P39 ----- [[1 2] [3 4]] [[1 3] [2 4]] [[1 4] [2 3]] [[1 2] [3 4] [5 6]] [[1 2] [3 5] [4 6]] [[1 2] [3 6] [4 5]] [[1 3] [2 4] [5 6]] [[1 3] [2 5] [4 6]] [[1 3] [2 6] [4 5]] [[1 4] [2 3] [5 6]] [[1 5] [2 3] [4 6]] [[1 6] [2 3] [4 5]] [[1 4] [2 5] [3 6]] [[1 4] [2 6] [3 5]] [[1 5] [2 4] [3 6]] [[1 6] [2 4] [3 5]] [[1 5] [2 6] [3 4]] [[1 6] [2 5] [3 4]] ----- P40 ----- 3 15 280 15400 1401400
改訂 2021 年 12 月 19 日