●問題51
前回に引き続き、今回も Lisp 風のシンプルな連結リストライブラリ slist を作成します。
n から m までの整数を格納したリストを生成する関数 Iota, 要素 x を n 個持つリストを生成する関数 MakeList, 整数 n から m までの値に関数 f を適用した結果をリストに格納して返す関数 Tabulate を定義してください。
func Iota(n, m int) *Cell func MakeList(n int, x Any) *Cell func Tabulate(f func(x Any) Any, n, m int) *Cell
Iota(1, 8) => (1 2 3 4 5 6 7 8)
Iota(1, 1) => (1)
MakeList(8, 0) => (0 0 0 0 0 0 0 0)
MakeList(4, "a") => (a a a a)
square := func (x Any) Any { return x.(int) * x.(int) }
Tabulate(square, 1, 5) => (1 4 9 16 25)
●問題52
リストを木とみなして、木を操作する関数を定義します。要素 (葉) を数える関数 CountLeaf, x と等しい要素を y に置換する関数 Subst, リストを平坦化する関数 Flatten, マッピングした結果を平坦化する関数 FlatMap を定義してください。
func CountLeaf(xs *Cell) int func Subst(x, y Any, xs *Cell) *Cell func Flatten(xs *Cell) *Cell func FlatMap(f func(x Any) Any, xs *Cell) *Cell
CountLeaf(List(1, List(2, List(3, 4), 5), 6)) => 6
Subst(1, 10, List(1, 2, List(1, 2, 3), 1)) => (10 2 (10 2 3) 10)
Flatten(List(List(1,2), List(3,4), List(5,6))) => (1 2 3 4 5 6)
FlatMap(func (x Any) Any { return List(x, x) }, List(1,2,3)) => (1 1 2 2 3 3)
●問題53
リスト xs から n 個の要素を選ぶ順列を求める関数 Permutation とリスト xs から重複を許して n 個の要素を選ぶ順列を求める関数 RepeatPperm を定義してください。なお、生成した順列はリストに格納して返すものとします。
Permutation(n int, xs *Cell) *Cell RepeatPerm(n int, xs *Cell) *Cell
Permutation(3, List(1,2,3)) => ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)) RepeatPerm(2, List(1,2,3)) => ((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))
●問題54
リスト xs から n 個の要素を選ぶ組み合わせを求める関数 Combination とリスト xs から重複を許して n 個の要素を選ぶ組み合わせを求める関数 RepeatComb を定義してください。なお、生成した組み合わせはリストに格納して返すものとします。
Combination(n int, xs *Cell) *Cell RepeatComb(n int, xs *Cell) *Cell
Combination(3, List(1,2,3,4,5)) => ((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)) RepeatComb(2, List(1,2,3,4)) => ((1 1) (1 2) (1 3) (1 4) (2 2) (2 3) (2 4) (3 3) (3 4) (4 4))
●問題55
リストを集合とみなして、次の集合演算を定義してください。
func RemoveDup(xs *Cell) *Cell // リスト xs から重複要素を取り除く func IsSubset(xs, ys *Cell) bool // 集合 xs が ys の部分集合であれば真を返す func EqSet(xs, ys *Cell) bool // 集合 xs と ys が等しければ真を返す func Union(xs, ys *Cell) *Cell // 集合 xs, ys の和を求める func Intersection(xs, ys *Cell) *Cell // 集合 xs, ys の積を求める func Difference(xs, ys *Cell) *Cell // 集合 xs, ys の差を求める
RemoveDup(List(1,1,2,1,2,3,1,2,3,4)) => (1 2 3 4) IsSubset(List(1,2,3), List(4,3,2,1)) => true IsSubset(List(1,2,5), List(4,3,2,1)) => false EqSet(List(1,2,3), List(3,1,2)) => true EqSet(List(1,2,3), List(3,1,0)) => false xs := List(1,2,3,4) ys := List(3,4,5,6) Union(xs, ys) => (1 2 3 4 5 6) Intersection(xs, ys) => (3 4) Difference(xs, ys) => (1 2)
●問題56
リスト xs を挿入ソートする関数 InsertSort を定義してください。
func InsertSort(xs *Cell, f func(x, y Any) bool) *Cell
lt := func(x, y Any) bool { return x.(int) < y.(int) }
InsertSort(List(3,4,2,5,1), lt) => (1 2 3 4 5)
●問題57
リスト xs を述語 f の真偽で二分割する関数 Partition を定義してください。
func Partition(xs *Cell, f func (x Any) bool) (*Cell, *Cell)
xs, ys := Partition(List(1,2,3,4,5,6), func (x Any) bool { return x.(int) % 2 == 0 })
xs => (6 4 2)
ys => (5 3 1)
●問題58
リスト xs をクイックソートする関数 QuickSort を定義してください。
func QuickSort(xs *Cell, f func (x, y Any) bool) *Cell
lt := func(x, y Any) bool { return x.(int) < y.(int) }
QuickSort(List(5,6,4,7,3,8,2,9,1,0), lt)) => (0 1 2 3 4 5 6 7 8 9)
●問題59
リスト xs, ys をマージする関数 MergeList を定義してください。
func MergeList(xs, ys *Cell, f func (x, y Any) bool) *Cell
xs := List(2,4,6,8)
ys := List(1,3,5,7)
lt := func(x, y Any) bool { return x.(int) < y.(int) }
MergeList(xs, ys, lt) => (1 2 3 4 5 6 7 8)
●問題60
リスト xs をマージソートする関数 MergeSort を定義してください。
lt := func(x, y Any) bool { return x.(int) < y.(int) }
func MergeSort(xs *Cell, n int, f func(x, y Any) bool) *Cell
MergeSort(List(5,6,4,7,3,8,2,9,1,0), 10, lt)) => (0 1 2 3 4 5 6 7 8 9)
●解答51
リスト : リストの生成
func Iota(n, m int) *Cell {
var xs *Cell
for ; m >= n; m-- {
xs = Cons(m, xs)
}
return xs
}
func Tabulate(f func(x Any) Any, n, m int) *Cell {
var xs *Cell
for ; m >= n; m-- {
xs = Cons(f(m), xs)
}
return xs
}
func MakeList(n int, x Any) *Cell {
var xs *Cell
for ; n > 0; n-- {
xs = Cons(x, xs)
}
return xs
}
関数 Iota は簡単です。m, m - 1, ..., n + 1, n までの数値を生成して、リスト xs の先頭に追加していることに注意してください。m が n よりも小さくなったならばリスト xs を返します。関数 Tabulate は、整数値 m に関数 f を適用して、その結果をリスト xs の先頭に追加します。関数 MakeList はリスト xs に引数の x を n 個追加するだけです。
●解答52
リスト : 葉の個数を求める
func CountLeaf(x Any) int {
xs, ok := x.(*Cell)
if ok {
if xs == nil {
return 0
}
return CountLeaf(Car(xs)) + CountLeaf(Cdr(xs))
}
return 1
}
関数 CountLeaf も簡単です。xs がコンスセルならば左右の部分木にたいして CountLeaf を再帰呼び出しし、その結果を足し算して返します。xs が空リストならば 0 を返します。それ以外であれば要素なので 1 を返します。
リスト : 木の置換
func Subst(x, y Any, zs *Cell) *Cell {
if Null(zs) {
return nil
}
a, ok := Car(zs).(*Cell)
if ok {
return Cons(Subst(x, y, a), Subst(x, y, Cdr(zs)))
} else if Eq(x, Car(zs)) {
return Cons(y, Subst(x, y, Cdr(zs)))
}
return Cons(Car(zs), Subst(x, y, Cdr(zs)))
}
関数 Subst は引数 zs と返り値の型が *Cell になっていることに注意してください。引数 zs が空リストであれば nil を返します。次に、要素 Car(zs) がコンスセルかチェックします。zs の型が *Cell なので、Car(zs) に Subst をそのまま適用することはできません。コンスセルであれば、左右の部分木に対して Subst を再帰呼び出しし、その結果を Cons で連結して返します。x と Car(zs) が等しい場合は、Car(zs) のかわりに y を Cons で連結します。それ以外の場合は Car(zs) をそのまま Cons で連結します。
リスト : 平坦化
func Flatten(x Any) *Cell {
xs, ok := x.(*Cell)
if !ok {
return List(x)
} else if Null(xs) {
return nil
}
return Append(Flatten(Car(xs)), Flatten(Cdr(xs)))
}
Flatten は簡単です。Subst と違って、引数 x の型が Any になっていることに注意してください。x がコンスセルでなければ x をリストに格納して返します。空リストの場合は nil を返します。それ以外の場合は Car(xs) と Cdr(xs) を Flatten で平坦化し、それらを Append で連結するだけです。引数 x の型が Any なので、Car(xs) に Flatten をそのまま適用することができます。
リスト : マップの結果を平坦化する
// 複数のリストを連結する
func appends(xs *Cell) *Cell {
if !Null(xs) && Null(Cdr(xs)) {
return Car(xs).(*Cell)
}
return Append(Car(xs).(*Cell), appends(Cdr(xs)))
}
func FlatMap(f func (x Any) Any, xs *Cell) *Cell {
return appends(MapCar(f, xs))
}
関数 FlatMap はリストを一段階だけ平坦化することに注意してください。FlatMap は複数のリストを連結する関数 appends を定義すると簡単です。MapCar でリストの要素に関数 f を適用し、その結果を appends で連結するだけです。
関数 appends の引数 xs はリストで、その要素はリストであることを前提としています。xs の要素が一つの場合、その要素を取り出して返します。要素の型は Any なので、型アサーションで *Cell に変換していることに注意してください。そうでなければ、先頭要素 Car(xs) と appends(Cdr(xs)) の返り値を Append で連結します。これでリストの要素を連結することができます。
●解答53
リスト : 順列の生成
func Permutation(n int, xs *Cell) *Cell {
if n == 0 {
return List((*Cell)(nil))
}
return FlatMap(func (x Any) Any {
return MapCar(
func (y Any) Any { return Cons(x, y.(*Cell)) },
Permutation(n - 1, Remove(x, xs)))},
xs)
}
// 重複順列
func RepeatPerm(n int, xs *Cell) *Cell {
if n == 0 {
return List((*Cell)(nil))
}
return FlatMap(func (x Any) Any {
return MapCar(
func (y Any) Any { return Cons(x, y.(*Cell)) },
RepeatPerm(n - 1, xs))},
xs)
}
関数 Permutation は引数のリスト xs から n 個を選ぶ順列を生成し、それをリストに格納して返します。n が 0 のときが再帰の停止条件で、空リストを格納したリストを返します。このリストに対して要素を追加します。この処理は MapCar を二重に使うと簡単に実現できます。このとき、リストを平坦化します。これを関数 FlatMap で行っています。
あとはラムダ式の中で Permutation を再帰呼び出しをして、n - 1 個を選ぶ順列を生成します。そして、その返り値にリスト xs の要素 x を追加すれば、n 個を選ぶ順列を生成することができます。
重複順列も簡単です。選んだ要素を取り除く必要がないので、RepeatPerm を再帰呼び出しするとき、リスト xs をそのまま渡すだけです。
●解答54
組み合わせの生成は、次に示す組み合わせの公式と同じ考え方でプログラムすることができます。
nＣ0 = nＣn = 1 nＣr = n-1Ｃr-1 + n-1Ｃr
プログラムは次のようになります。
リスト : 組み合わせの生成
func Combination(n int, xs *Cell) *Cell {
if n == 0 {
return List((*Cell)(nil))
} else if Length(xs) == n {
return List(xs)
}
return Append(MapCar(func (x Any) Any { return Cons(Car(xs), x.(*Cell)) },
Combination(n - 1, Cdr(xs))),
Combination(n, Cdr(xs)))
}
// 重複組み合わせ
func RepeatComb(n int, xs *Cell) *Cell {
if n == 0 {
return List((*Cell)(nil))
} else if !Null(xs) && Null(Cdr(xs)) {
return List(MakeList(n, Car(xs)))
}
return Append(MapCar(func (x Any) Any { return Cons(Car(xs), x.(*Cell)) },
RepeatComb(n - 1, xs)),
RepeatComb(n, Cdr(xs)))
}
n が 0 の場合、選択する要素がないので空リストを格納したリストを返します。次の if で、n と xs の要素数が同じ場合は、その要素を全て選択するので xs をリストに格納して返します。
そうでなければ、先頭要素 Car(xs) を選びます。残りのリスト Cdr(xs) から n - 1 個を選ぶ組み合わせを生成して、その先頭に Car(xs) を追加します。あとは、Cdr(xs) から n 個を選ぶ組み合わせを Combination で求めて、関数 Append で連結するだけです。
重複組み合わせを求める RepeatComb も簡単です。2 番目の if で、リスト xs に要素が一つしかない場合は、その要素を n 個選びます。MakeList で Car(xs) を n 個格納したリストを生成します。最後の処理では、先頭の要素を選んだあと、それを取り除かないで xs から n - 1 個の要素を選びます。
●解答55
リスト : 集合演算
// 重複要素を取り除く
func RemoveDup(xs *Cell) *Cell {
var ys *Cell
for ; !Null(xs); xs = Cdr(xs) {
if !Find(Car(xs), ys) {
ys = Cons(Car(xs), ys)
}
}
return Reverse(ys)
}
// 部分集合の判定
func IsSubset(xs, ys *Cell) bool {
for ; !Null(xs); xs = Cdr(xs) {
if !Find(Car(xs), ys) {
return false
}
}
return true
}
// 等値の判定
func EqSet(xs, ys *Cell) bool {
return IsSubset(xs, ys) && IsSubset(ys, xs)
}
関数 RemoveDup はリストから重複要素を取り除きます。for ループでリストの要素を順番に取り出し、それがリスト ys に含まれていなければ、それを ys に追加するだけです。最後に Reverse でリストを反転して返します。集合の場合、要素の順序は関係ないので、最後の Reverse は削除してもかまいません。
関数 IsSubset はリスト xs の要素がすべて ys にあることを確認するだけです。関数 EqSet は簡単で、xs が ys の部分集合で、かつ、ys が xs の部分集合であれば、xs と ys は等しい集合であると判定できます。
リスト : 和集合
func Union(xs, ys *Cell) *Cell {
if Null(xs) {
return ys
} else if Find(Car(xs), ys) {
return Union(Cdr(xs), ys)
} else {
return Cons(Car(xs), Union(Cdr(xs), ys))
}
}
最初の if は空集合 (空リスト) と集合 ys の和は ys であることを表しています。次の if で、要素 Car(xs) が集合 ys に含まれていれば、それを新しい集合に加えません。else 節で Car(xs) が ys に含まれていなければ、それを集合に追加します。
リスト : 積集合
func Intersection(xs, ys *Cell) *Cell {
if Null(xs) {
return nil
} else if Find(Car(xs), ys) {
return Cons(Car(xs), Intersection(Cdr(xs), ys))
} else {
return Intersection(Cdr(xs), ys)
}
}
最初の if は空集合 (空リスト) と集合 ys の積は空集合であることを表しています。次の if で、要素 Car(xs) が集合 ys に含まれていれば、それを新しい集合に追加します。そうでなければ、else 節で要素 Car(xs) を集合に追加しません。
リスト : 差集合
func Difference(xs, ys *Cell) *Cell {
if Null(xs) {
return nil
} else if Find(Car(xs), ys) {
return Difference(Cdr(xs), ys)
} else {
return Cons(Car(xs), Difference(Cdr(xs), ys))
}
}
最初の if は、空集合と集合 ys の差は空集合であることを表しています。次の if で、要素 Car(xs) が ys に含まれいる場合は集合にそれを追加しません。そうでなければ、else 節で要素 Car(xs) を集合に追加します。
●解答56
挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。たとえば、リスト (2 4 6) に 5 を挿入する場合、リストの要素 n と 5 を順番に比較して、5 < n を満たす位置に 5 を挿入すればいいわけです。この場合は、4 と 6 の間に 5 を挿入すればいいですね。
プログラムは次のようになります。
リスト : 挿入ソート
func insertSub(x Any, xs *Cell, f func(x, y Any) bool) *Cell {
if Null(xs) || f(x, Car(xs)) {
return Cons(x, xs)
}
return Cons(Car(xs), insertSub(x, Cdr(xs), f))
}
func InsertSort(xs *Cell, f func(x, y Any) bool) *Cell {
var ys *Cell
for ; !Null(xs); xs = Cdr(xs) {
ys = insertSub(Car(xs), ys, f)
}
return ys
}
リストにデータをひとつ挿入する関数が insertSub です。再帰呼び出しでリストをたどり、データ x を挿入する位置を探します。比較関数 f の返り値が真であれば、その位置にデータを挿入します。関数 InsertSort は for ループでリスト xs の要素を順番に取り出して、それを insertSub でリスト ys に挿入していくだけです。
●解答57
リスト : リストの分割
func Partition(xs *Cell, f func(x Any) bool) (*Cell, *Cell) {
var ys *Cell
var zs *Cell
for ; !Null(xs); xs = Cdr(xs) {
if f(Car(xs)) {
ys = Cons(Car(xs), ys)
} else {
zs = Cons(Car(xs), zs)
}
}
return ys, zs
}
関数 Partition は簡単です。述語 f が真を返す要素を変数 ys のリストに、魏を返す要素を zs に格納します。あとは、リスト xs から要素を順番に取り出して f に適用し、真であれば ys に、偽であれば zs に追加していくだけです。
●解答58
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選んでいいのですが、リストの場合は任意の箇所を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。
リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。
5 3 7 6 9 8 1 2 4
5 を枢軸に分割
(3 1 2 4) 5 (7 6 9 8)
3を枢軸に分割 7を枢軸に分割
(1 2) 3 (4) | 5 | (6) 7 (9 8)
・・・分割を繰り返していく・・・
図 : クイックソート
このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを Append で結合すればいいわけです。プログラムは次のようになります。
リスト : クイックソート
func QuickSort(xs *Cell, f func(x, y Any) bool) *Cell {
if Null(xs) {
return nil
}
ys, zs := Partition(
Cdr(xs),
func(x Any) bool { return f(x, Car(xs)) })
return Append(QuickSort(ys, f), Cons(Car(xs), QuickSort(zs, f)))
}
引数 xs が空リストの場合は nil を返します。これが再帰呼び出しの停止条件になります。次に、Partition を呼び出して、枢軸 Car(xs) を基準にリスト Cdr(xs) を二分割します。あとは、その結果を Append で結合するだけです。
クイックソートの実行時間は、データ数を N とすると平均して N * log2 N に比例します。ところが、枢軸の選び方によっては、最悪で N の 2 乗に比例するまで劣化します。クイックソートはリストには不向きのアルゴリズムといえます。
●解答59
リストのマージは簡単です。次の図を見てください。
図 : リストのマージ
2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。 a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。
プログラムは次のようになります。
リスト : マージ
func MergeList(xs, ys *Cell, f func(x, y Any) bool) *Cell {
if Null(xs) {
return ys
} else if Null(ys) {
return xs
}
if f(Car(xs), Car(ys)) {
return Cons(Car(xs), MergeList(Cdr(xs), ys, f))
}
return Cons(Car(ys), MergeList(xs, Cdr(ys), f))
}
最初の if は、空リストとリスト ys をマージすると ys になることを表しています。次の if は、リスト xs と空リストをマージすると xs になることを表しています。この 2 つの節が、再帰呼び出しの停止条件になります。最後の if で、それぞれのリストの先頭要素を述語 f で比較し、f が真を返す場合は Car(xs) をマージしたリストの先頭に追加し、そうでなければ Car(ys) をマージしたリストの先頭に追加します。MergeList を再帰呼び出しするときは、xs または ys の先頭要素を取り除いて呼び出すことに注意してください。
●解答60
マージソートはリストの長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。まず、ソートするリストを 2 つに分割して、前半部分をソートします。次に、後半部分をソートして、その結果をマージすればいいわけです。
再帰呼び出しするたびにリストは 2 つに分割されるので、最後にリストの要素はひとつとなります。これはソート済みのリストなので、ここで再帰呼び出しを終了してマージ処理を行えばいいわけです。プログラムは次のようになります。
リスト : マージソート
func MergeSort(xs *Cell, n int, f func(x, y Any) bool) *Cell {
if n == 1 {
return List(Car(xs))
}
m := n / 2
return MergeList(
MergeSort(xs, m, f),
MergeSort(Drop(xs, m), n - m, f),
f)
}
関数 MergeSort の引数 f が要素を比較する述語、引数 xs がソートするリスト、引数 n がリストの長さを表します。MergeSort はリストを分割する処理で、新しいリストを作らないことに注意してください。MergeSort はソートするリストの範囲を開始位置と長さで表しています。リストを二分割する場合、前半部分は xs と m (= n / 2) で表し、後半部分を Drop(xs, m) と n - m で表します。
あとは MergeSort を再帰呼び出しでリストを分割していき、リストの長さが 1 になったならば新しいリストを返します。そして、MergeSort でソートしたリストを MergeList でマージすればいいわけです。
●プログラムリスト
//
// slist1.go : Lisp 風連結リストライブラリ
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package slist
// リストの生成
func Iota(n, m int) *Cell {
var xs *Cell
for ; m >= n; m-- {
xs = Cons(m, xs)
}
return xs
}
func Tabulate(f func(x Any) Any, n, m int) *Cell {
var xs *Cell
for ; m >= n; m-- {
xs = Cons(f(m), xs)
}
return xs
}
func MakeList(n int, x Any) *Cell {
var xs *Cell
for ; n > 0; n-- {
xs = Cons(x, xs)
}
return xs
}
// 木の操作
func CountLeaf(x Any) int {
xs, ok := x.(*Cell)
if ok {
if xs == nil {
return 0
}
return CountLeaf(Car(xs)) + CountLeaf(Cdr(xs))
}
return 1
}
// 置換
func Subst(x, y Any, zs *Cell) *Cell {
if Null(zs) {
return nil
}
a, ok := Car(zs).(*Cell)
if ok {
return Cons(Subst(x, y, a), Subst(x, y, Cdr(zs)))
} else if Eq(x, Car(zs)) {
return Cons(y, Subst(x, y, Cdr(zs)))
}
return Cons(Car(zs), Subst(x, y, Cdr(zs)))
}
// 平坦化
func Flatten(x Any) *Cell {
xs, ok := x.(*Cell)
if !ok {
return List(x)
} else if Null(xs) {
return nil
}
return Append(Flatten(Car(xs)), Flatten(Cdr(xs)))
}
// 複数のリストを連結する
func appends(xs *Cell) *Cell {
if !Null(xs) && Null(Cdr(xs)) {
return Car(xs).(*Cell)
}
return Append(Car(xs).(*Cell), appends(Cdr(xs)))
}
func FlatMap(f func (x Any) Any, xs *Cell) *Cell {
return appends(MapCar(f, xs))
}
// 順列の生成
func Permutation(n int, xs *Cell) *Cell {
if n == 0 {
return List((*Cell)(nil))
}
return FlatMap(func (x Any) Any {
return MapCar(
func (y Any) Any { return Cons(x, y.(*Cell)) },
Permutation(n - 1, Remove(x, xs)))},
xs)
}
func RepeatPerm(n int, xs *Cell) *Cell {
if n == 0 {
return List((*Cell)(nil))
}
return FlatMap(func (x Any) Any {
return MapCar(
func (y Any) Any { return Cons(x, y.(*Cell)) },
RepeatPerm(n - 1, xs))},
xs)
}
// 組み合わせの生成
func Combination(n int, xs *Cell) *Cell {
if n == 0 {
return List((*Cell)(nil))
} else if Length(xs) == n {
return List(xs)
}
return Append(MapCar(func (x Any) Any { return Cons(Car(xs), x.(*Cell)) },
Combination(n - 1, Cdr(xs))),
Combination(n, Cdr(xs)))
}
func RepeatComb(n int, xs *Cell) *Cell {
if n == 0 {
return List((*Cell)(nil))
} else if !Null(xs) && Null(Cdr(xs)) {
return List(MakeList(n, Car(xs)))
}
return Append(MapCar(func (x Any) Any { return Cons(Car(xs), x.(*Cell)) },
RepeatComb(n - 1, xs)),
RepeatComb(n, Cdr(xs)))
}
// 集合演算
// 重複要素を取り除く
func RemoveDup(xs *Cell) *Cell {
var ys *Cell
for ; !Null(xs); xs = Cdr(xs) {
if !Find(Car(xs), ys) {
ys = Cons(Car(xs), ys)
}
}
return Reverse(ys)
}
// 部分集合の判定
func IsSubset(xs, ys *Cell) bool {
for ; !Null(xs); xs = Cdr(xs) {
if !Find(Car(xs), ys) {
return false
}
}
return true
}
func EqSet(xs, ys *Cell) bool {
return IsSubset(xs, ys) && IsSubset(ys, xs)
}
// 和集合
func Union(xs, ys *Cell) *Cell {
if Null(xs) {
return ys
} else if Find(Car(xs), ys) {
return Union(Cdr(xs), ys)
} else {
return Cons(Car(xs), Union(Cdr(xs), ys))
}
}
// 積集合
func Intersection(xs, ys *Cell) *Cell {
if Null(xs) {
return nil
} else if Find(Car(xs), ys) {
return Cons(Car(xs), Intersection(Cdr(xs), ys))
} else {
return Intersection(Cdr(xs), ys)
}
}
// 差集合
func Difference(xs, ys *Cell) *Cell {
if Null(xs) {
return nil
} else if Find(Car(xs), ys) {
return Difference(Cdr(xs), ys)
} else {
return Cons(Car(xs), Difference(Cdr(xs), ys))
}
}
// 挿入ソート
func insertSub(x Any, xs *Cell, f func(x, y Any) bool) *Cell {
if Null(xs) || f(x, Car(xs)) {
return Cons(x, xs)
}
return Cons(Car(xs), insertSub(x, Cdr(xs), f))
}
func InsertSort(xs *Cell, f func(x, y Any) bool) *Cell {
var ys *Cell
for ; !Null(xs); xs = Cdr(xs) {
ys = insertSub(Car(xs), ys, f)
}
return ys
}
// リストの分割
func Partition(xs *Cell, f func(x Any) bool) (*Cell, *Cell) {
var ys *Cell
var zs *Cell
for ; !Null(xs); xs = Cdr(xs) {
if f(Car(xs)) {
ys = Cons(Car(xs), ys)
} else {
zs = Cons(Car(xs), zs)
}
}
return ys, zs
}
// クイックソート
func QuickSort(xs *Cell, f func(x, y Any) bool) *Cell {
if Null(xs) {
return nil
}
ys, zs := Partition(
Cdr(xs),
func(x Any) bool { return f(x, Car(xs)) })
return Append(QuickSort(ys, f), Cons(Car(xs), QuickSort(zs, f)))
}
// マージ
func MergeList(xs, ys *Cell, f func(x, y Any) bool) *Cell {
if Null(xs) {
return ys
} else if Null(ys) {
return xs
}
if f(Car(xs), Car(ys)) {
return Cons(Car(xs), MergeList(Cdr(xs), ys, f))
}
return Cons(Car(ys), MergeList(xs, Cdr(ys), f))
}
// マージソート
func MergeSort(xs *Cell, n int, f func(x, y Any) bool) *Cell {
if n == 1 {
return List(Car(xs))
}
m := n / 2
return MergeList(
MergeSort(xs, m, f),
MergeSort(Drop(xs, m), n - m, f),
f)
}
●簡単なテスト
//
// yagp06.go : Yet Another Golang Problems
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import (
"fmt"
. "yagp/slist"
)
func main() {
fmt.Println("----- P51 -----")
Println(Iota(1, 8))
Println(Iota(1, 1))
Println(MakeList(8, 0))
Println(MakeList(4, "a"))
square := func (x Any) Any { return x.(int) * x.(int) }
Println(Tabulate(square, 1, 5))
fmt.Println("----- P52 -----")
fmt.Println(CountLeaf(List(1, List(2, List(3, 4), 5), 6)))
Println(Subst(1, 10, List(1, 2, List(1, 2, 3), 1)))
Println(Flatten(List(List(1,2), List(3,4), List(5,6))))
Println(FlatMap(func (x Any) Any { return List(x, x) }, List(1,2,3)))
fmt.Println("----- P53 -----")
Println(Permutation(3, List(1,2,3)))
Println(RepeatPerm(2, List(1,2,3)))
fmt.Println("----- P54 -----")
Println(Combination(3, List(1,2,3,4,5)))
Println(RepeatComb(2, List(1,2,3,4)))
fmt.Println("----- P55 -----")
Println(RemoveDup(List(1,1,2,1,2,3,1,2,3,4)))
fmt.Println(IsSubset(List(1,2,3), List(4,3,2,1)))
fmt.Println(IsSubset(List(1,2,5), List(4,3,2,1)))
fmt.Println(EqSet(List(1,2,3), List(3,1,2)))
fmt.Println(EqSet(List(1,2,3), List(3,1,0)))
xs := List(1,2,3,4)
ys := List(3,4,5,6)
Println(Union(xs, ys))
Println(Intersection(xs, ys))
Println(Difference(xs, ys))
fmt.Println("----- P56 -----")
lt := func(x, y Any) bool { return x.(int) < y.(int) }
Println(InsertSort(List(3,4,2,5,1), lt))
fmt.Println("----- P57 -----")
xs, ys = Partition(List(1,2,3,4,5,6), func (x Any) bool { return x.(int) % 2 == 0 })
Println(xs)
Println(ys)
fmt.Println("----- P58 -----")
Println(QuickSort(List(5,6,4,7,3,8,2,9,1,0), lt))
fmt.Println("----- P59 -----")
xs = List(2,4,6,8)
ys = List(1,3,5,7)
Println(MergeList(xs, ys, lt))
fmt.Println("----- P60 -----")
Println(MergeSort(List(5,6,4,7,3,8,2,9,1,0), 10, lt))
}
●実行結果
$ cd yagp $ ls go.mod slist yagp01.go yagp02.go yagp03.go yagp04.go yagp05.go yagp06.go $ ls slist slist.go slist1.go $ go run yagp06.go ----- P51 ----- (1 2 3 4 5 6 7 8) (1) (0 0 0 0 0 0 0 0) (a a a a) (1 4 9 16 25) ----- P52 ----- 6 (10 2 (10 2 3) 10) (1 2 3 4 5 6) (1 1 2 2 3 3) ----- P53 ----- ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)) ((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3)) ----- P54 ----- ((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 1) (1 2) (1 3) (1 4) (2 2) (2 3) (2 4) (3 3) (3 4) (4 4)) ----- P55 ----- (1 2 3 4) true false true false (1 2 3 4 5 6) (3 4) (1 2) ----- P56 ----- (1 2 3 4 5) ----- P57 ----- (6 4 2) (5 3 1) ----- P58 ----- (0 1 2 3 4 5 6 7 8 9) ----- P59 ----- (1 2 3 4 5 6 7 8) ----- P60 ----- (0 1 2 3 4 5 6 7 8 9)
改訂 2021 年 12 月 22 日