片方向の連結リスト (singly-linked list) です。詳しい説明は拙作のページ Algorithms with Python 連結リスト をお読みください。なお、今回は C# のお勉強ということでインデクサーを実装しましたが、要素数を N とすると、要素のアクセスは O(N) に比例する時間がかかります。配列のようにランダムアクセスする用途には向きません。ご注意くださいませ。
リスト : 連結リスト (lintlist.csx, 非ジェネリック版)
using System.Collections;
class LinkList : IEnumerable {
class Cell {
public object Car { get; set; }
public Cell Cdr { get; set; }
public Cell(object item, Cell next) {
Car = item;
Cdr = next;
}
}
// ヘッダーセル
Cell header;
// 空リストの生成
public LinkList() {
header = new Cell(null, null);
}
// n 番目のセルを求める
private Cell NthCell(int n) {
Cell cp = header;
for (int i = -1; i < n; i++) {
if (cp == null) throw new IndexOutOfRangeException();
cp = cp.Cdr;
}
return cp;
}
// インデクサー
public object this[int n] {
get { return NthCell(n).Car; }
set { NthCell(n).Car = value; }
}
// 挿入
public void Insert(object item, int n) {
Cell cp = NthCell(n - 1);
cp.Cdr = new Cell(item, cp.Cdr);
}
// 削除
public void Delete(int n) {
Cell cp = NthCell(n - 1);
if (cp.Cdr == null) throw new IndexOutOfRangeException();
cp.Cdr = cp.Cdr.Cdr;
}
// イテレータ
public IEnumerator GetEnumerator() {
var cp = header.Cdr;
while (cp != null) {
yield return cp.Car;
cp = cp.Cdr;
}
}
}
void PrintList(LinkList a) {
foreach(object x in a)
Console.Write("{0} ", x);
Console.WriteLine("");
}
void test() {
var a = new LinkList();
for (int i = 0; i < 10; i++) {
a.Insert(i, i);
}
PrintList(a);
for (int i = 0; i < 10; i++) {
a[i] = (int)a[i] * 10;
Console.Write("{0} ", a[i]);
}
Console.WriteLine("");
a.Delete(0);
PrintList(a);
a.Delete(8);
PrintList(a);
a.Delete(4);
PrintList(a);
}
// テスト
test();
$ dotnet script linklist.csx 0 1 2 3 4 5 6 7 8 9 0 10 20 30 40 50 60 70 80 90 10 20 30 40 50 60 70 80 90 10 20 30 40 50 60 70 80 10 20 30 40 60 70 80
リスト : 連結リスト (ジェネリック版, linklist1.cs)
using System.Collections;
using System.Collections.Generic;
class LinkList<T> : IEnumerable<T> where T : IComparable<T> {
class Cell {
public T Car { get; set; }
public Cell Cdr { get; set; }
public Cell(T item, Cell next) {
Car = item;
Cdr = next;
}
}
// ヘッダーセル
Cell header;
// 空リストの生成
public LinkList() {
header = new Cell(default(T), null);
}
// n 番目のセルを求める
private Cell NthCell(int n) {
Cell xs = header;
for (int i = -1; i < n; i++) {
if (xs == null) throw new IndexOutOfRangeException();
xs = xs.Cdr;
}
return xs;
}
// インデクサー
public T this[int n] {
get { return NthCell(n).Car; }
set { NthCell(n).Car = value; }
}
// 挿入
public void Insert(T item, int n) {
Cell xs = NthCell(n - 1);
xs.Cdr = new Cell(item, xs.Cdr);
}
// 削除
public void Delete(int n) {
Cell xs = NthCell(n - 1);
if (xs.Cdr == null) throw new IndexOutOfRangeException();
xs.Cdr = xs.Cdr.Cdr;
}
// イテレータ
public IEnumerator<T> GetEnumerator() {
var xs = header.Cdr;
while (xs != null) {
yield return xs.Car;
xs = xs.Cdr;
}
}
IEnumerator IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
// 探索
public bool Contains(T item) {
foreach(T x in this) {
if (item.CompareTo(x) == 0) return true;
}
return false;
}
public int IndexOf(T item) {
int i = 0;
var xs = header.Cdr;
while (xs != null) {
if (item.CompareTo(xs.Car) == 0) return i;
xs = xs.Cdr;
i++;
}
return -1;
}
public int FindIndex(Func<T, bool> pred) {
int i = 0;
var xs = header.Cdr;
while (xs != null) {
if (pred(xs.Car)) return i;
xs = xs.Cdr;
i++;
}
return -1;
}
}
void PrintList<T>(LinkList<T> a) where T : IComparable<T> {
foreach(T x in a)
Console.Write("{0} ", x);
Console.WriteLine("");
}
void test() {
var a = new LinkList<int>();
for (int i = 0; i < 10; i++) {
a.Insert(i, i);
}
PrintList(a);
for (int i = -1; i < 11; i++) {
Console.WriteLine("{0}, {1}", i, a.Contains(i));
Console.WriteLine("{0}, {1}", i, a.IndexOf(i));
Console.WriteLine("{0}, {1}", i, a.FindIndex(x => x == i));
}
for (int i = 0; i < 10; i++) {
a[i] *= 10;
Console.Write("{0} ", a[i]);
}
Console.WriteLine("");
a.Delete(0);
PrintList(a);
a.Delete(8);
PrintList(a);
a.Delete(4);
PrintList(a);
}
// テスト
test();
$ dotnet script linklist1.csx 0 1 2 3 4 5 6 7 8 9 -1, False -1, -1 -1, -1 0, True 0, 0 0, 0 1, True 1, 1 1, 1 2, True 2, 2 2, 2 3, True 3, 3 3, 3 4, True 4, 4 4, 4 5, True 5, 5 5, 5 6, True 6, 6 6, 6 7, True 7, 7 7, 7 8, True 8, 8 8, 8 9, True 9, 9 9, 9 10, False 10, -1 10, -1 0 10 20 30 40 50 60 70 80 90 10 20 30 40 50 60 70 80 90 10 20 30 40 50 60 70 80 10 20 30 40 60 70 80
リスト : immutable な連結リスト (ジェネリック版, linklist2.cs)
using System.Collections;
using System.Collections.Generic;
// immutable な連結リスト
public class Cell<T> : IEnumerable<T> where T : IComparable {
public T Car { get; }
public Cell<T> Cdr { get; }
public Cell(T item, Cell<T> next) {
Car = item;
Cdr = next;
}
// 終端
public static readonly Cell<T> nil = new Cell<T>(default(T), null);
public bool Null() { return this == nil; }
// イテレータ
public IEnumerator<T> GetEnumerator() {
var xs = this;
while (!xs.Null()) {
yield return xs.Car;
xs = xs.Cdr;
}
}
IEnumerator IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
// リストの生成
public static Cell<T> List(params T[] xs) {
var ys = nil;
for (int i = xs.Length - 1; i >= 0; i--) {
ys = new Cell<T>(xs[i], ys);
}
return ys;
}
// リストの連結
public Cell<T> Append(Cell<T> xs) {
if (this.Null())
return xs;
else
return new Cell<T>(Car, Cdr.Append(xs));
}
// リストの反転
public Cell<T> Reverse() {
var ys = nil;
foreach(T x in this) {
ys = new Cell<T>(x, ys);
}
return ys;
}
// リストの長さ
public int Length() {
int c = 0;
foreach(T x in this) {
c++;
}
return c;
}
// 参照
public T Nth(int n) {
foreach(T x in this) {
if (n-- == 0) return x;
}
throw new IndexOutOfRangeException();
}
// 探索
public Cell<T> Member(T item) {
var xs = this;
while (!xs.Null()) {
if (item.CompareTo(xs.Car) == 0) break;
xs = xs.Cdr;
}
return xs;
}
public bool Contains(T item) {
foreach(T x in this) {
if (item.CompareTo(x) == 0) return true;
}
return false;
}
public int IndexOf(T item) {
int i = 0;
foreach(T x in this) {
if (item.CompareTo(x) == 0) return i;
i++;
}
return -1;
}
public int FindIndex(Func<T, bool> pred) {
int i = 0;
foreach(T x in this) {
if (pred(x)) return i;
i++;
}
return -1;
}
// マッピング
public Cell<U> Map<U>(Func<T, U> func) where U : IComparable {
if (this.Null())
return Cell<U>.nil;
else
return new Cell<U>(func(Car), Cdr.Map(func));
}
// フィルター
public Cell<T> Filter(Func<T, bool> pred) {
if (this.Null())
return nil;
else if (pred(Car))
return new Cell<T>(Car, Cdr.Filter(pred));
else
return Cdr.Filter(pred);
}
// 畳み込み
public U FoldLeft<U>(Func<U, T, U> func, U a) {
foreach(T x in this) {
a = func(a, x);
}
return a;
}
public U FoldRight<U>(Func<T, U, U> func, U a) {
if (this.Null())
return a;
else
return func(Car, Cdr.FoldRight(func, a));
}
// 巡回
public void Each(Action<T> func) {
foreach(T x in this) {
func(x);
}
}
// 表示
public void Print() {
var xs = this;
Console.Write("(");
while (!xs.Null()) {
Console.Write("{0}", xs.Car);
xs = xs.Cdr;
if (!xs.Null()) Console.Write(" ");
}
Console.WriteLine(")");
}
}
void test() {
var a = Cell<int>.List(1, 2, 3, 4, 5);
a.Print();
Console.WriteLine("{0}", a.Length());
a.Reverse().Print();
var b = Cell<int>.List(6, 7, 8, 9, 10);
var c = a.Append(b);
c.Print();
for (int i = 0; i < c.Length(); i++)
Console.Write("{0} ", c.Nth(i));
Console.WriteLine("");
for (int i = 0; i <= 11; i++) {
c.Member(i).Print();
Console.WriteLine("{0}", c.Contains(i));
Console.WriteLine("{0}", c.IndexOf(i));
Console.WriteLine("{0}", c.FindIndex(n => n == i));
}
c.Map(n => n * 10).Print();
c.Filter(n => n % 2 == 0).Print();
Console.WriteLine("{0}", c.FoldLeft((sum, n) => sum + n, 0));
Console.WriteLine("{0}", c.FoldRight((n, sum) => sum + n, 0));
c.Each(n => Console.Write("{0} ", n));
Console.WriteLine("");
foreach(int n in c) {
Console.Write("{0} ", n);
}
Console.WriteLine("");
}
// テスト
test();
$ dotnet script linklist2.csx (1 2 3 4 5) 5 (5 4 3 2 1) (1 2 3 4 5 6 7 8 9 10) 1 2 3 4 5 6 7 8 9 10 () False -1 -1 (1 2 3 4 5 6 7 8 9 10) True 0 0 (2 3 4 5 6 7 8 9 10) True 1 1 (3 4 5 6 7 8 9 10) True 2 2 (4 5 6 7 8 9 10) True 3 3 (5 6 7 8 9 10) True 4 4 (6 7 8 9 10) True 5 5 (7 8 9 10) True 6 6 (8 9 10) True 7 7 (9 10) True 8 8 (10) True 9 9 () False -1 -1 (10 20 30 40 50 60 70 80 90 100) (2 4 6 8 10) 55 55 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
リスト : Lisp ライクな連結リスト (immutable, linklist3.csx)
using System.Collections;
using static Cell;
class Cell : IEnumerable {
public object Car { get; }
public Cell Cdr { get; } // ドットリストはサポートしない
public Cell(object item, Cell next) {
Car = item;
Cdr = next;
}
// 終端
public static readonly Cell nil = new Cell(null, null);
// 述語
public static bool Null(object xs) { return xs == nil; }
public static bool Consp(object xs) { return xs is Cell; }
public static bool Listp(object xs) { return Null(xs) || Consp(xs); }
public static bool Eql(object x, object y) {
return ((IComparable)x).CompareTo((IComparable)y) == 0;
}
// イテレータ
public IEnumerator GetEnumerator() {
var xs = this;
while (!Null(xs)) {
yield return xs.Car;
xs = xs.Cdr;
}
}
// リストの生成
public static Cell List(params object[] xs) {
var ys = nil;
for (int i = xs.Length - 1; i >= 0; i--) {
ys = new Cell(xs[i], ys);
}
return ys;
}
// リストの連結
public Cell Append(Cell ys) {
if (Null(this))
return ys;
else
return new Cell(Car, Cdr.Append(ys));
}
// リストの反転
public Cell Reverse() {
var ys = nil;
foreach(object x in this) {
ys = new Cell(x, ys);
}
return ys;
}
// リストの長さ
public int Length() {
int c = 0;
foreach(object x in this) {
c++;
}
return c;
}
// 参照
public object Nth(int n) {
var xs = this;
while (!Null(xs)) {
if (n-- == 0) return xs.Car;
xs = xs.Cdr;
}
throw new IndexOutOfRangeException();
}
// 探索
public Cell Member(object x) {
var xs = this;
while (!Null(xs)) {
if (Eql(xs.Car, x)) return xs;
xs = xs.Cdr;
}
return xs;
}
public int IndexOf(object x) {
int i = 0;
foreach(object y in this) {
if (Eql(x, y)) return i;
i++;
}
return -1;
}
public int FindIndex(Func<object, bool> pred) {
int i = 0;
foreach(object x in this) {
if (pred(x)) return i;
i++;
}
return -1;
}
// マッピング
public Cell Map(Func<object, object> func) {
if (Null(this))
return nil;
else
return new Cell(func(Car), Cdr.Map(func));
}
// フィルター
public Cell Filter(Func<object, bool> pred) {
if (Null(this))
return nil;
else if (pred(Car))
return new Cell(Car, Cdr.Filter(pred));
else
return Cdr.Filter(pred);
}
// 畳み込み
public object FoldLeft(Func<object, object, object> func, object a) {
foreach(object x in this) {
a = func(a, x);
}
return a;
}
public object FoldRight(Func<object, object, object> func, object a) {
if (Null(this))
return a;
else
return func(Car, Cdr.FoldRight(func, a));
}
// 巡回
public void Each(Action<object> func) {
foreach(object x in this) {
func(x);
}
}
// 連想リスト
public Cell Zip(Cell xs) {
if (Null(this) || Null(xs))
return nil;
else
return new Cell(List(Car, xs.Car), Cdr.Zip(xs.Cdr));
}
public Cell Assoc(object item) {
foreach(object xs in this) {
Cell ys = (Cell)xs;
if (Eql(item, ys.Car)) return ys;
}
return nil;
}
// 表示
public void Print() {
var xs = this;
Console.Write("(");
while (!Null(xs)) {
if (Consp(xs.Car)) {
Cell cp = (Cell)xs.Car;
cp.Print();
} else {
Console.Write("{0}", xs.Car);
}
xs = xs.Cdr;
if (!Null(xs)) Console.Write(" ");
}
Console.Write(")");
}
public void PrintLine() {
this.Print();
Console.WriteLine("");
}
}
void test() {
var a = List(1, 2);
var b = List(3, 4, 5);
var c = List(6, 7, 8, 9);
var d = List(a, b, c);
a.PrintLine();
b.PrintLine();
c.PrintLine();
d.PrintLine();
var e = a.Append(b).Append(c);
e.PrintLine();
e.Reverse().PrintLine();
Console.WriteLine("{0}", e.Length());
foreach(object x in e) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
for (int i = 0; i < e.Length(); i++) {
Console.Write("{0} ", e.Nth(i));
}
Console.WriteLine("");
d.Map(xs => ((Cell)xs).Length()).PrintLine();
e.Map(n => (int)n * 10).PrintLine();
d.Map(xs => ((Cell)xs).Reverse()).PrintLine();
e.Filter(n => (int)n % 2 == 0).PrintLine();
Console.WriteLine("{0}", e.FoldLeft((sum, n) => (int)sum + (int)n, 0));
Console.WriteLine("{0}", e.FoldRight((n, sum) => (int)sum + (int)n, 0));
e.Each(n => Console.Write("{0} ", n));
Console.WriteLine("");
for (int i = 0; i <= 10; i++) {
e.Member(i).PrintLine();
Console.WriteLine("{0}", e.IndexOf(i));
Console.WriteLine("{0}", e.FindIndex(n => (int)n == i));
}
var alist = List("foo", "bar", "baz").Zip(List(1, 2, 3));
alist.PrintLine();
alist.Assoc("foo").PrintLine();
alist.Assoc("bar").PrintLine();
alist.Assoc("baz").PrintLine();
alist.Assoc("oops").PrintLine();
}
// テスト
test();
$ dotnet script linklist3.csx (1 2) (3 4 5) (6 7 8 9) ((1 2) (3 4 5) (6 7 8 9)) (1 2 3 4 5 6 7 8 9) (9 8 7 6 5 4 3 2 1) 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 (2 3 4) (10 20 30 40 50 60 70 80 90) ((2 1) (5 4 3) (9 8 7 6)) (2 4 6 8) 45 45 1 2 3 4 5 6 7 8 9 () -1 -1 (1 2 3 4 5 6 7 8 9) 0 0 (2 3 4 5 6 7 8 9) 1 1 (3 4 5 6 7 8 9) 2 2 (4 5 6 7 8 9) 3 3 (5 6 7 8 9) 4 4 (6 7 8 9) 5 5 (7 8 9) 6 6 (8 9) 7 7 (9) 8 8 () -1 -1 ((foo 1) (bar 2) (baz 3)) (foo 1) (bar 2) (baz 3) ()
リスト : 二分木 (ジェネリック版, tree.cs)
using System.Collections;
using System.Collections.Generic;
class Tree<T> : IEnumerable<T> where T : IComparable<T> {
// 節
class Node {
public T Item { set; get; }
public Node Left { set; get; }
public Node Right { set; get; }
public Node(T item) {
Item = item;
Left = null;
Right = null;
}
}
// ルート
Node root;
// コンストラクタ
public Tree() { root = null; }
// 操作関数
// 挿入
static Node InsertNode(T x, Node node) {
if (node == null)
return new Node(x);
else {
int r = x.CompareTo(node.Item);
if (r < 0)
node.Left = InsertNode(x, node.Left);
else if (r > 0)
node.Right = InsertNode(x, node.Right);
return node;
}
}
// 探索
static bool SearchNode(T x, Node node) {
while (node != null) {
int r = x.CompareTo(node.Item);
if (r == 0) return true;
else if (r < 0)
node = node.Left;
else
node = node.Right;
}
return false;
}
// 最小値の探索
static T SearchMin(Node node) {
while (node.Left != null) node = node.Left;
return node.Item;
}
// 最小値のノードを削除
static Node DeleteMin(Node node) {
if (node.Left == null) return node.Right;
node.Left = DeleteMin(node.Left);
return node;
}
// 削除
static Node DeleteNode(T x, Node node) {
if (node != null) {
int r = x.CompareTo(node.Item);
if (r == 0) {
if (node.Left == null) return node.Right;
if (node.Right == null) return node.Left;
node.Item = SearchMin(node.Right);
node.Right = DeleteMin(node.Right);
} else if (r < 0) {
node.Left = DeleteNode(x, node.Left);
} else if (r > 0) {
node.Right = DeleteNode(x, node.Right);
}
}
return node;
}
// 巡回
static void EachNode(Action<T> func, Node node) {
if (node != null) {
EachNode(func, node.Left);
func(node.Item);
EachNode(func, node.Right);
}
}
// メソッド
// 挿入
public void Insert(T x) {
root = InsertNode(x, root);
}
// 探索
public bool Search(T x) {
return SearchNode(x, root);
}
// 削除
public void Delete(T x) {
root = DeleteNode(x, root);
}
// 巡回
public void Each(Action<T> func) {
EachNode(func, root);
}
// 空の木か
public bool IsEmpty() {
return root == null;
}
// 空にする
public void Clear() {
root = null;
}
// イテレータ
static void NextNode(List<Node> path, Node node) {
while (node != null) {
path.Add(node);
node = node.Left;
}
}
public IEnumerator<T> GetEnumerator() {
var path = new List<Node>();
NextNode(path, root);
while (path.Count > 0) {
var node = path[path.Count - 1];
path.RemoveAt(path.Count - 1);
yield return node.Item;
NextNode(path, node.Right);
}
}
IEnumerator IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
}
void test() {
int[] a = new int[] {5,6,4,3,7,8,1,2,9,0};
var tree = new Tree<int>();
foreach(int x in a) {
tree.Insert(x);
}
for (int i = -1; i < 11; i++) {
Console.WriteLine("{0} {1}", i, tree.Search(i));
}
tree.Each(x => Console.WriteLine("{0}", x));
foreach (int x in tree) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
for (int i = 0; i < 10; i++) {
tree.Delete(i);
Console.WriteLine("{0} {1}", i, tree.Search(i));
tree.Each(x => Console.Write("{0} ", x));
Console.WriteLine("");
}
}
// テスト
test();
$ dotnet script tree.csx -1 False 0 True 1 True 2 True 3 True 4 True 5 True 6 True 7 True 8 True 9 True 10 False 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 False 1 2 3 4 5 6 7 8 9 1 False 2 3 4 5 6 7 8 9 2 False 3 4 5 6 7 8 9 3 False 4 5 6 7 8 9 4 False 5 6 7 8 9 5 False 6 7 8 9 6 False 7 8 9 7 False 8 9 8 False 9 9 False
リスト : 二分木 (immutable, tree1.cs)
using System.Collections;
using System.Collections.Generic;
class Tree<T> : IEnumerable<T> where T : IComparable<T> {
public T Item { get; }
public Tree<T> Left { get; }
public Tree<T> Right { get; }
public Tree(T item, Tree<T> left, Tree<T> right) {
Item = item;
Left = left;
Right = right;
}
// 空の木
public static readonly Tree<T> nil = new Tree<T>(default(T), null, null);
public bool IsEmpty() { return this == nil; }
public static Tree<T> MakeTree() { return nil; }
// 挿入
public Tree<T> Insert(T x) {
if (this == nil)
return new Tree<T>(x, nil, nil);
else {
int r = x.CompareTo(Item);
if (r < 0)
return new Tree<T>(Item, Left.Insert(x), Right);
else if (r > 0)
return new Tree<T>(Item, Left, Right.Insert(x));
else
return this;
}
}
// 探索
public bool Search(T x) {
Tree<T> node = this;
while (node != nil) {
int r = x.CompareTo(node.Item);
if (r == 0) return true;
else if (r < 0)
node = node.Left;
else
node = node.Right;
}
return false;
}
// 最小値の探索
public T SearchMin() {
Tree<T> node = this;
while (node != nil) node = node.Left;
return node.Item;
}
// 最小値のノードを削除
public Tree<T> DeleteMin() {
if (Left == nil) return Right;
return new Tree<T>(Item, Left.DeleteMin(), Right);
}
// 削除
public Tree<T> Delete(T x) {
if (this == nil) {
return nil;
} else {
int r = x.CompareTo(Item);
if (r == 0) {
if (Left == nil) return Right;
if (Right == nil) return Left;
return new Tree<T>(Right.SearchMin(), Left, Right.DeleteMin());
} else if (r < 0) {
return new Tree<T>(Item, Left.Delete(x), Right);
} else {
return new Tree<T>(Item, Left, Right.Delete(x));
}
}
}
// 巡回
public void Each(Action<T> func) {
if (this != nil) {
Left.Each(func);
func(Item);
Right.Each(func);
}
}
// イテレータ
static void NextNode(List<Tree<T>> path, Tree<T> node) {
while (node != nil) {
path.Add(node);
node = node.Left;
}
}
public IEnumerator<T> GetEnumerator() {
var path = new List<Tree<T>>();
NextNode(path, this);
while (path.Count > 0) {
var node = path[path.Count - 1];
path.RemoveAt(path.Count - 1);
yield return node.Item;
NextNode(path, node.Right);
}
}
IEnumerator IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
}
void test() {
int[] a = new int[] {5,6,4,3,7,8,1,2,9,0};
var tree = Tree<int>.MakeTree();
foreach(int x in a) {
tree = tree.Insert(x);
}
for (int i = -1; i < 11; i++) {
Console.WriteLine("{0} {1}", i, tree.Search(i));
}
tree.Each(x => Console.WriteLine("{0}", x));
foreach(int x in tree) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
for (int i = 0; i < 10; i++) {
tree = tree.Delete(i);
Console.WriteLine("{0} {1}", i, tree.Search(i));
tree.Each(x => Console.Write("{0} ", x));
Console.WriteLine("");
}
}
// テスト
test();
$ dotnet script tree1.csx -1 False 0 True 1 True 2 True 3 True 4 True 5 True 6 True 7 True 8 True 9 True 10 False 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 False 1 2 3 4 5 6 7 8 9 1 False 2 3 4 5 6 7 8 9 2 False 3 4 5 6 7 8 9 3 False 4 5 6 7 8 9 4 False 5 6 7 8 9 5 False 6 7 8 9 6 False 7 8 9 7 False 8 9 8 False 9 9 False
皆さんお馴染みの「８パズル」を幅優先探索で解くプログラムです。詳しい説明は拙作のページ Ｃ言語超入門: スライドパズル をお読みください。
//
// eight.csx : 8 パズル (幅優先探索)
//
// Copyright (C) 2016-2022 Makoto Hiroi
//
using System.Collections.Generic;
class State {
public int space;
public int[] board;
public State prev;
public State(int s, int[] b, State st) {
space = s;
board = b;
prev = st;
}
}
// 隣接リスト
// 0 1 2
// 3 4 5
// 6 7 8
const int Size = 9;
int[][] adjacent = new int[Size][] {
new int[] {1, 3},
new int[] {0, 2, 4},
new int[] {1, 5},
new int[] {0, 4, 6},
new int[] {1, 3, 5, 7},
new int[] {2, 4, 8},
new int[] {3, 7},
new int[] {4, 6, 8},
new int[] {5, 7},
};
// キュー
const int MaxSize = 181440;
State[] que = new State[MaxSize];
int rear;
int front;
void enq(State st) { que[rear++] = st; }
State deq() { return que[front++]; }
bool IsEmpty() { return rear == front; }
bool EqualBoard(int[] xs, int[] ys) {
for (int i = 0; i < Size; i++)
if (xs[i] != ys[i]) return false;
return true;
}
int[] CopyBoard(int[] xs) {
int[] ys = new int[Size];
for (int i = 0; i < Size; i++)
ys[i] = xs[i];
return ys;
}
int BoardToInt(int[] xs) {
int a = 0;
foreach(int x in xs) {
a = a * 10 + x;
}
return a;
}
void PrintAnswer(State st) {
if (st.prev != null) PrintAnswer(st.prev);
foreach(int x in st.board) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
}
void bfs(int[] start, int[] goal) {
var ht = new Dictionary<int, bool>();
enq(new State(Array.IndexOf(start, 0), start, null));
ht[BoardToInt(start)] = true;
while (!IsEmpty()) {
State st = deq();
int s = st.space;
int[] b = st.board;
if (EqualBoard(b, goal)) {
PrintAnswer(st);
return;
} else {
foreach(int x in adjacent[s]) {
int[] newBoard = CopyBoard(b);
newBoard[s] = newBoard[x];
newBoard[x] = 0;
int key = BoardToInt(newBoard);
if (!ht.ContainsKey(key)) {
ht[key] = true;
enq(new State(x, newBoard, st));
}
}
}
}
}
// 実行
bfs(new int[] {8,6,7,2,5,4,3,0,1}, new int[] {1,2,3,4,5,6,7,8,0});
$ dotnet script eight.csx 8 6 7 2 5 4 3 0 1 8 6 7 2 0 4 3 5 1 8 0 7 2 6 4 3 5 1 0 8 7 2 6 4 3 5 1 2 8 7 0 6 4 3 5 1 2 8 7 3 6 4 0 5 1 2 8 7 3 6 4 5 0 1 2 8 7 3 6 4 5 1 0 2 8 7 3 6 0 5 1 4 2 8 0 3 6 7 5 1 4 2 0 8 3 6 7 5 1 4 2 6 8 3 0 7 5 1 4 2 6 8 0 3 7 5 1 4 2 6 8 5 3 7 0 1 4 2 6 8 5 3 7 1 0 4 2 6 8 5 3 7 1 4 0 2 6 8 5 3 0 1 4 7 2 6 0 5 3 8 1 4 7 2 0 6 5 3 8 1 4 7 2 3 6 5 0 8 1 4 7 2 3 6 0 5 8 1 4 7 2 3 6 1 5 8 0 4 7 2 3 6 1 5 8 4 0 7 2 3 6 1 5 8 4 7 0 2 3 6 1 5 0 4 7 8 2 3 0 1 5 6 4 7 8 2 0 3 1 5 6 4 7 8 0 2 3 1 5 6 4 7 8 1 2 3 0 5 6 4 7 8 1 2 3 4 5 6 0 7 8 1 2 3 4 5 6 7 0 8 1 2 3 4 5 6 7 8 0
皆さんお馴染みの「８パズル」を反復深化と下限値枝刈り法で解くプログラムです。詳しい説明は拙作のページ Ｃ言語超入門: スライドパズル (2) をお読みください。
//
// eight1.csx : 8 パズル (反復深化＋下限値枝刈り法)
//
// Copyright (C) 2016-2022 Makoto Hiroi
//
using System.Collections.Generic;
// 隣接リスト
// 0 1 2
// 3 4 5
// 6 7 8
const int Size = 9;
static int[][] adjacent = new int[Size][] {
new int[] {1, 3},
new int[] {0, 2, 4},
new int[] {1, 5},
new int[] {0, 4, 6},
new int[] {1, 3, 5, 7},
new int[] {2, 4, 8},
new int[] {3, 7},
new int[] {4, 6, 8},
new int[] {5, 7},
};
// 移動距離
static int[,] distance = {
{0, 0, 0, 0, 0, 0, 0, 0, 0}, // dummy
{0, 1, 2, 1, 2, 3, 2, 3, 4},
{1, 0, 1, 2, 1, 2, 3, 2, 3},
{2, 1, 0, 3, 2, 1, 4, 3, 2},
{1, 2, 3, 0, 1, 2, 1, 2, 3},
{2, 1, 2, 1, 0, 1, 2, 1, 2},
{3, 2, 1, 2, 1, 0, 3, 2, 1},
{2, 3, 4, 1, 2, 3, 0, 1, 2},
{3, 2, 3, 2, 1, 2, 1, 0, 1},
};
// 解の総数
int count;
// 移動距離の計算
int CalcDistance(int[] board) {
int d = 0;
for (int i = 0; i < Size; i++) {
int p = board[i];
d += distance[p, i];
}
return d;
}
bool EqualBoard(int[] xs, int[] ys) {
for (int i = 0; i < Size; i++)
if (xs[i] != ys[i]) return false;
return true;
}
void dfs(int[] board, int s, int[] goal, int limit, int low, List<int> move) {
if (move.Count - 1 == limit) {
if (EqualBoard(board, goal)) {
count++;
foreach(int x in move) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
}
} else {
foreach(int x in adjacent[s]) {
int p = board[x];
if (p == move[move.Count - 1]) continue;
int newLow = low - distance[p, x] + distance[p, s];
if (newLow + move.Count - 1 <= limit) {
board[s] = p;
board[x] = 0;
move.Add(p);
dfs(board, x, goal, limit, newLow, move);
move.RemoveAt(move.Count - 1);
board[x] = p;
board[s] = 0;
}
}
}
}
void idsearch() {
var start = new int[] {8,6,7,2,5,4,3,0,1};
var goal = new int[] {1,2,3,4,5,6,7,8,0};
var move = new List<int>();
move.Add(0); // dummy
int low = CalcDistance(start);
for(int limit = low; limit < 32; limit++) {
Console.WriteLine("----- {0} -----", limit);
dfs(start, 7, goal, limit, low, move);
if (count > 0) break;
}
Console.WriteLine("count = {0}", count);
}
// 実行
idsearch();
$ dotnet script eight1.csx
----- 21 -----
----- 22 -----
----- 23 -----
----- 24 -----
----- 25 -----
----- 26 -----
----- 27 -----
----- 28 -----
----- 29 -----
----- 30 -----
----- 31 -----
0 5 6 8 2 3 5 1 4 7 8 6 3 5 1 4 7 8 6 3 5 1 4 7 8 6 3 2 1 4 7 8
0 5 6 7 4 6 2 3 5 1 6 2 3 8 7 4 2 3 1 5 8 7 4 1 5 8 7 4 1 2 3 6
0 5 2 3 5 1 4 7 6 8 3 2 8 3 2 5 1 4 7 8 5 1 4 7 8 6 3 2 1 4 7 8
・・・ 省略 ・・・
0 1 4 5 2 3 1 4 5 7 6 8 3 2 8 3 2 1 4 5 7 8 5 7 8 6 3 2 1 4 7 8
0 1 4 5 2 3 1 4 5 7 6 2 3 8 2 3 8 1 4 8 7 5 8 7 5 6 3 2 1 4 7 8
0 1 4 5 2 3 1 4 5 7 6 2 3 8 2 3 8 1 4 5 7 8 5 7 8 6 3 2 1 4 7 8
count = 40