例3は単純ミスということなんで、とりあえず再帰的に総当たりをするためのアルゴリズムを示しておきます。「特に言語にこだわりません」と言いつつ、アルゴリズムの記述にSwiftを使うなんて想定している人はいないでしょうが、こちらが一番使い慣れているものなのでご容赦を。
まずはデータ構造の準備
//点を表す構造体
struct Point: Hashable {
var x: Int
var y: Int
}
//線分を表す構造体
struct Line: Hashable {
var p1: Point
var p2: Point
//入力データを書きやすくするためのイニシャライザ
init(_ p1: (x: Int, y: Int), _ p2: (x: Int, y: Int)) {
self.p1 = Point(x: p1.x, y: p1.y)
self.p2 = Point(x: p2.x, y: p2.y)
}
//補助メソッド: 線分をたどった隣側の点
func next(to: Point) -> Point {
if to == self.p1 {return p2}
if to == self.p2 {return p1}
fatalError("Invalid line used")
}
}
//閉路を表す構造体
struct ClosedPath: Hashable {
var start: Point //始点(結果を表示しやすくするためだけに使っている)
var path: [Line] //閉路に含まれるすべての線分
let lineSet: Set<Line> //同一性判定用
//初期化, pathは必ず閉路を表していないといけない
init(start: Point, path: [Line]) {
self.start = start
self.path = path
self.lineSet = Set(path)
}
//
//線分の集合が等しければ同一の閉図形と判定する
//
func hash(into hasher: inout Hasher) {
self.lineSet.hash(into: &hasher)
}
static func == (lhs: ClosedPath, rhs: ClosedPath) -> Bool {
return lhs.lineSet == rhs.lineSet
}
}
重複を防ぐために集合型を多用しているので、そのためにHashable
なんてものが出てきてますが、Set
(やDictionary
のキー)に使うためのおまじないくらいに思ってください。
上記の構造体を使うと、「閉路」探索は次のように書けます。
//閉路探索
func findClosedPaths(lines: [Line]) -> Set<ClosedPath> {
//結果は重複を防ぐため集合型で持つ
var result: Set<ClosedPath> = []
//前処理:ある頂点から辿れる線分を全部リストアップしておく
var availablePaths: [Point: Set<Line>] = [:]
for line in lines {
availablePaths[line.p1] = (availablePaths[line.p1] ?? []).union([line])
availablePaths[line.p2] = (availablePaths[line.p2] ?? []).union([line])
}
//関数型プログラミング的には美しくないが、現在の状態を再帰処理関数の外に持っておく
var currentPath: [Line] = [] //現在までの経路
var visitedLines: Set<Line> = [] //訪問済みの線分
//深さ優先探索用の内部関数
func searchClosedPath(start: Point, current: Point) {
//currentから辿れる未訪問の線分について繰り返し
for nextLine in availablePaths[current]! where !visitedLines.contains(nextLine){
currentPath.append(nextLine)
//その線分をたどった時の次の点を求める
let nextPoint = nextLine.next(to: current)
if nextPoint == start {
//ゴール(==始点)に達していたら現在の経路を結果に追加して終了
result.insert(ClosedPath(start: start, path: currentPath))
} else {
//まだなら再帰的に探索
visitedLines.insert(nextLine)
searchClosedPath(start: start, current: nextPoint)
visitedLines.remove(nextLine)
}
currentPath.removeLast()
}
}
//線分に含まれる全ての点について繰り返す
for start in availablePaths.keys {
searchClosedPath(start: start, current: start)
}
return result
}
詳細はコメントを参照してください。内部関数やそこから参照されている変数類を外出しすれば、リスト型(可変長配列)、集合型、辞書型(Hash, HashMap)のある言語なら移植は容易だと思います。
そのままだと結果が見辛くなるので、少しばかりごそごそ。
/*
* 表示整形用
*/
extension Point: CustomStringConvertible {
var description: String {
return String(format: "[%2d,%2d]", x, y)
}
}
extension Line: CustomStringConvertible {
var description: String {
return "\(p1)-\(p2)"
}
}
extension ClosedPath: CustomStringConvertible {
var description: String {
var currPoint = start
var points: [Point] = []
for line in path {
points.append(currPoint)
currPoint = line.next(to: currPoint)
}
return points.map {$0.description}.joined(separator: "-")
}
}
func prettyPrintInput(lines: [Line]) {
for (index, line) in lines.enumerated() {
let heading = index == 0 ? "input : " : " "
print("\(heading)線分\(index+1) \(line)")
}
}
func prettyPrintOutput(closedPaths: Set<ClosedPath>) {
print("output : 閉図形の数=\(closedPaths.count)")
for closedPath in closedPaths {
print(" : \(closedPath)")
}
}
func showClosedPaths(title: String, lines: [Line]) {
print(title)
prettyPrintInput(lines: lines)
let result = findClosedPaths(lines: lines)
prettyPrintOutput(closedPaths: result)
print()
}
出来合いのパッケージなら内部で全部やってくれることを自前でやらないといけないので、ちょっと長くなりますが、メインの閉路探索については再帰処理の典型例なので、しっかり頭の中でトレースしていけばイメージはつかめるかと思います。
では実行。
/*
* 実行
*/
showClosedPaths(title: "例1", lines: [
Line(( 0, 0), (10, 0)),
Line((10, 0), ( 0,10)),
Line(( 0,10), ( 0, 0)),
Line((-5, 0), (-5,10)),
])
showClosedPaths(title: "例2(8の字の形:1つとします)", lines: [
Line(( 0, 0), (10,10)),
Line((10,10), (10, 0)),
Line((10, 0), ( 0,10)),
Line(( 0,10), ( 0, 0)),
Line((-5, 0), (-5,10)),
])
showClosedPaths(title: "例3(▽△)", lines: [
Line(( 0, 0), ( 5, 5)),
Line(( 5, 5), ( 0,10)),
Line((10, 0), ( 0, 0)),
Line(( 5, 5), (10, 0)),
Line((10, 0), (10,10)),
Line((10,10), ( 5, 5)),
])
showClosedPaths(title: "例5(▽△)", lines: [
Line(( 0, 0), ( 5, 5)),
Line(( 5, 5), ( 0,10)),
Line(( 0,10), ( 0, 0)),
Line(( 5, 5), (10, 0)),
Line((10, 0), (10,10)),
Line((10,10), ( 5, 5)),
])
結果です。
例1
input : 線分1 [ 0, 0]-[10, 0]
線分2 [10, 0]-[ 0,10]
線分3 [ 0,10]-[ 0, 0]
線分4 [-5, 0]-[-5,10]
output : 閉図形の数=1
: [ 0, 0]-[ 0,10]-[10, 0]
例2(8の字の形:1つとします)
input : 線分1 [ 0, 0]-[10,10]
線分2 [10,10]-[10, 0]
線分3 [10, 0]-[ 0,10]
線分4 [ 0,10]-[ 0, 0]
線分5 [-5, 0]-[-5,10]
output : 閉図形の数=1
: [10,10]-[ 0, 0]-[ 0,10]-[10, 0]
例3(▽△)
input : 線分1 [ 0, 0]-[ 5, 5]
線分2 [ 5, 5]-[ 0,10]
線分3 [10, 0]-[ 0, 0]
線分4 [ 5, 5]-[10, 0]
線分5 [10, 0]-[10,10]
線分6 [10,10]-[ 5, 5]
output : 閉図形の数=3
: [10,10]-[10, 0]-[ 0, 0]-[ 5, 5]
: [10,10]-[10, 0]-[ 5, 5]
: [ 0, 0]-[10, 0]-[ 5, 5]
例5(▽△)
input : 線分1 [ 0, 0]-[ 5, 5]
線分2 [ 5, 5]-[ 0,10]
線分3 [ 0,10]-[ 0, 0]
線分4 [ 5, 5]-[10, 0]
線分5 [10, 0]-[10,10]
線分6 [10,10]-[ 5, 5]
output : 閉図形の数=3
: [10,10]-[10, 0]-[ 5, 5]
: [10,10]-[10, 0]-[ 5, 5]-[ 0,10]-[ 0, 0]-[ 5, 5]
: [ 0, 0]-[ 0,10]-[ 5, 5]
例5が例3とは別の理由で3つ出てきています。これは
▽ ▽
△ △
を別の閉路として捉えているためです。単に「閉路」と言った場合、同じ点を2度通っても良いのでこのような結果になります。(上のコードでは、経路としては別ものでも、同じ「閉図形」になるものは一つと数えるようにしています。)
同じ点を2度通らない場合を「単純閉路」と言います。上記のコードを単純閉路用に書き換えたものがこちら。
//単純閉路探索
func findSimpleClosedPaths(lines: [Line]) -> Set<ClosedPath> {
//結果は重複を防ぐため集合型で持つ
var result: Set<ClosedPath> = []
//前処理:ある頂点から辿れる線分を全部リストアップしておく
var availablePaths: [Point: Set<Line>] = [:]
for line in lines {
availablePaths[line.p1] = (availablePaths[line.p1] ?? []).union([line])
availablePaths[line.p2] = (availablePaths[line.p2] ?? []).union([line])
}
//関数型プログラミング的には美しくないが、現在の状態を再帰処理関数の外に持っておく
var currentPath: [Line] = [] //現在までの経路
var visitedLines: Set<Line> = [] //訪問済みの線分
var visitedPoints: Set<Point> = [] //訪問済みの点
//深さ優先探索用の内部関数
func searchClosedPath(start: Point, current: Point) {
//currentから辿れる未訪問の線分について繰り返し
for nextLine in availablePaths[current]! where !visitedLines.contains(nextLine){
currentPath.append(nextLine)
//その線分をたどった時の次の点を求める
let nextPoint = nextLine.next(to: current)
if nextPoint == start {
//ゴール(==始点)に達していたら現在の経路を結果に追加して終了
result.insert(ClosedPath(start: start, path: currentPath))
} else if !visitedPoints.contains(nextPoint) {
//まだなら再帰的に探索
visitedPoints.insert(current)
visitedLines.insert(nextLine)
searchClosedPath(start: start, current: nextPoint)
visitedLines.remove(nextLine)
visitedPoints.remove(current)
}
currentPath.removeLast()
}
}
//線分に含まれる全ての点について繰り返す
for start in availablePaths.keys {
searchClosedPath(start: start, current: start)
}
return result
}
で実行。
/*
* 表示整形用
*/
func showSimpleClosedPaths(title: String, lines: [Line]) {
print(title)
prettyPrintInput(lines: lines)
let result = findSimpleClosedPaths(lines: lines)
prettyPrintOutput(closedPaths: result)
print()
}
/*
* 実行
*/
showSimpleClosedPaths(title: "例1", lines: [
Line(( 0, 0), (10, 0)),
Line((10, 0), ( 0,10)),
Line(( 0,10), ( 0, 0)),
Line((-5, 0), (-5,10)),
])
showSimpleClosedPaths(title: "例2(8の字の形:1つとします)", lines: [
Line(( 0, 0), (10,10)),
Line((10,10), (10, 0)),
Line((10, 0), ( 0,10)),
Line(( 0,10), ( 0, 0)),
Line((-5, 0), (-5,10)),
])
showSimpleClosedPaths(title: "例3(▽△)", lines: [
Line(( 0, 0), ( 5, 5)),
Line(( 5, 5), ( 0,10)),
Line((10, 0), ( 0, 0)),
Line(( 5, 5), (10, 0)),
Line((10, 0), (10,10)),
Line((10,10), ( 5, 5)),
])
showSimpleClosedPaths(title: "例5(▽△)", lines: [
Line(( 0, 0), ( 5, 5)),
Line(( 5, 5), ( 0,10)),
Line(( 0,10), ( 0, 0)),
Line(( 5, 5), (10, 0)),
Line((10, 0), (10,10)),
Line((10,10), ( 5, 5)),
])
結果。
例1
input : 線分1 [ 0, 0]-[10, 0]
線分2 [10, 0]-[ 0,10]
線分3 [ 0,10]-[ 0, 0]
線分4 [-5, 0]-[-5,10]
output : 閉図形の数=1
: [ 0, 0]-[ 0,10]-[10, 0]
例2(8の字の形:1つとします)
input : 線分1 [ 0, 0]-[10,10]
線分2 [10,10]-[10, 0]
線分3 [10, 0]-[ 0,10]
線分4 [ 0,10]-[ 0, 0]
線分5 [-5, 0]-[-5,10]
output : 閉図形の数=1
: [10,10]-[ 0, 0]-[ 0,10]-[10, 0]
例3(▽△)
input : 線分1 [ 0, 0]-[ 5, 5]
線分2 [ 5, 5]-[ 0,10]
線分3 [10, 0]-[ 0, 0]
線分4 [ 5, 5]-[10, 0]
線分5 [10, 0]-[10,10]
線分6 [10,10]-[ 5, 5]
output : 閉図形の数=3
: [10,10]-[10, 0]-[ 0, 0]-[ 5, 5]
: [10,10]-[10, 0]-[ 5, 5]
: [ 0, 0]-[10, 0]-[ 5, 5]
例5(▽△)
input : 線分1 [ 0, 0]-[ 5, 5]
線分2 [ 5, 5]-[ 0,10]
線分3 [ 0,10]-[ 0, 0]
線分4 [ 5, 5]-[10, 0]
線分5 [10, 0]-[10,10]
線分6 [10,10]-[ 5, 5]
output : 閉図形の数=2
: [10,10]-[10, 0]-[ 5, 5]
: [ 0, 0]-[ 0,10]-[ 5, 5]
例3までの結果は「閉路」と同じですが、例5では結果が2個になっています。同じ点を2度通るような経路は省かれているためです。
結果だけが欲しいのであれば出来合いのパッケージで良いでしょうが、再帰処理による総当たりの良い練習問題になりますので、ご自身の得意な言語で実装しなおしてみることをお勧めします。
(注)Swiftの実行ができちゃうという人は試してもらうとわかるんですが、点や閉路の表示順が実行するたびに変化します。これは現在のSwift(4.2)の仕様です。
[ 0, 0]-[10, 0]-[10,10]-[ 5, 5]
なんて閉路もあるようなんですが、これを省かないといけないようなルールがあるんでしょうか?