ひとりで勝手にはじめた蟻本読書会 迷路の最短路 意外と奥が深い全探索 蟻本読書会の続きです。
全探索のなかには n! 通りの全探索やnext_permutationを使うものもあります。C++ には next_permutation 関数があり、これは与えられた配列の並べ替えを辞書順に並べたとき、与えられた配列の次に来るものを返します。すべての順列を探索する際には便利な存在のようですが、C#にはあるのでしょうか？（つくればあるそうです）
n! の値は n が大きくなるとびっくりするようなスピードで増えていきます（だから階乗の記号は「!」であるという説もあります）。なので n! 通りの全探索は小さな n でしか使えません。ただ n! 通りの全探索ができることも上達のための重要なステップになります。n が少し大きくなると bit DP を採用したほうがよいとは思いますが・・・。
n! 通りの全探索
自己ループと二重辺を含まない N 頂点 M 辺の重み無し無向グラフが与えられます。頂点 1 を始点として、すべての頂点を1度だけ訪れるパスは何通りありますか。ただし、パスの始点と終点の頂点も訪れたものとみなします。
入力
N M
a_1 b_1
a_2 b_2
a_3 b_3
…
a_M b_M（ただし
2 ≦ N ≦8
0 ≦ M ≦ N (N – 1) / 2
1 ≦ a_i ＜ b_i ≦ N）
頂点 1（配列の添字は0からはじめるので以降 0 とする） を始点とする深さ優先探索 (DFS) を用いて、候補となるパスを数え上げることを考えます。
まず頂点 0 を訪問済みとします。頂点番号である 0 を引数として再帰関数を呼びます。関数内で訪問済みかどうかチェックするための配列の要素がすべてtrueになっていた場合は「頂点 0 を始点として、すべての頂点を1度だけ訪れるパスがひとつみつかった」ことになるので 1 を返します。これを再起呼び出ししてその戻り地の合計を返すようにすれば頂点 0 を始点として、すべての頂点を1度だけ訪れるパスの個数がわかります。
この再帰関数には訪問済みかどうかチェックするための配列も一緒に渡すのですが、ひとつの配列を使い回すので再帰呼び出しが処理を返したら訪問済みのフラグをクリアします。
この解法の時間計算量は O(N!) です。一見制限時間内に間に合わなさそうですが、N の値が小さいため間に合います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
using System; using System.Collections.Generic; using System.Linq; class Program { static List<int>[] list = { }; // 頂点の隣接リスト static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } list = new List<int>[N]; for (int i = 0; i < N; i++) list[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; // 渡される頂点番号は 1 からはじまるので 0 からに変更する int b = vs[1] - 1; list[a].Add(b); list[b].Add(a); } bool[] visited = new bool[N]; visited[0] = true; Console.WriteLine(dfs(0, visited)); } static int dfs(int v, bool[] visited) { if (visited.All(_ => _ == true)) return 1; int ret = 0; foreach (int next in list[v]) { if(visited[next]) continue; visited[next] = true; ret += dfs(next, visited); visited[next] = false; // 再帰呼び出しが処理を返したら訪問済みのフラグをクリア } return ret; } } |
C#に next_permutation 関数はあるのか？
C++ の next_permutation 関数は与えられた配列の並べ替えを辞書順に並べたとき、与えられた配列の次に来るものを返します。すべての順列を探索する際には便利な存在ですが、C#にはこれに相当するものはあるのでしょうか？
ここにありました。作者いわく「C#だとコーディング時間的に厳しいので、C#で実装しておく。パフォーマンスなんて知りません」とのこと。
これを拝借してちょっとだけ変えたのが以下のコードです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
using System; using System.Collections.Generic; using System.Linq; class Program { /// <summary> /// シーケンスの次の順列を求めます /// </summary> /// <param name="array">次の順列を求めたいシーケンス</param> /// <param name="start">次の順列を求めたい範囲の最初のインデックス</param> /// <returns>引数arrayが最後の順列ならばfalse、そうでないならtrueを返します</returns> public static bool NextPermutation(int[] array, int start) { int length = array.Length; int end = start + length - 1; // 範囲が狭すぎる if (end <= start) return false; int last = end; while (true) { int pos = last--; if (array[last].CompareTo(array[pos]) < 0) { int i; for (i = end + 1; array[last].CompareTo(array[--i]) >= 0;) { } int tmp = array[last]; array[last] = array[i]; array[i] = tmp; Array.Reverse(array, pos, end - pos + 1); return true; } if (last == start) // 最後の順列 { Array.Reverse(array, start, end - start); return false; } } // ここに来ることはない throw new Exception("NextPermutation: Fatal error"); } static void Main() { int[] A = { 1, 2, 3, 4 }; // 昇順にソートしておかないと順列を全列挙できない do { Console.WriteLine(string.Join(", ", A)); } while (NextPermutation(A, 0)); } } |
上記のコードを実行すると、数列 A = { 1, 2, 3, 4 } の順列が表示されます。
C – False Hope
3×3 のマス目に 1 から 9 までの数字が書き込まれており、上から i 行目、左から j 列目 (1 ≦ i ≦ 3, 1 ≦ j ≦ 3) に書き込まれている数字は c [i, j] です。
異なるマスに同じ数字が書き込まれている場合もありますが、同じ数字が縦・横・斜めに 3 つ連続して書き込まれていることはありません。
高橋くんは、それぞれのマスに書かれている数字をランダムな順番で知ります。 高橋くんは、縦・横・斜めの列のうちの 1 つでも次の条件を満たしたときがっかりします。
はじめに知ったほうの 2 マスに書かれた数字が同じであり、最後に知ったマスに書かれた数字がそれと異なる。
高橋くんががっかりせずにすべてのマスに書かれた数字を知る確率を求めてください。入力例
3 1 9
2 5 6
2 7 1出力例
0.666666666666666666666666666667
（ただし絶対誤差が 10^-8 以下であれば正答とみなす）
高橋くん。こんなことでがっかりしないでくれ。鳩はレーティングがなかなか上がらず毎週がっかりだ（←自分が悪い）。冗談はさておき解法は以下のとおりです。
高橋くんが数字を知る順番は 9!=362880 通りあり、これらはすべてが等しい確率で起こりえます。なので全探索でこれらを調べ、高橋くんががっかりするかどうかを判定することができれば、(がっかりしない数字の知り方の総数) / (数字の知り方の総数 = 362880) で計算できます。
がっかりするかどうかの判定は、縦・横・斜めの各列に対して「同じ数字が書かれたマスのペアがあるか」を判定し、存在していれば「同じ数字の 2 マスが先に見られたか」をチェックすることで実現できます。
高橋くんが数字を知るマスの順序は A = { 0，1, 2, 3, 4, 5, 6, 7, 8 } の順列であり、これは上記の拝借したコードから生成できます。
上段、中段、下段、左列、中列、右列、斜め2方向で0～9の整数3つからなる位置のパターンをつくります。それぞれのパターンから a, b, c 3つの変数に値を代入します。このとき「マス a と マス b が同じ数字 であり マス c が最後に開けられた場合」、「マス a と マス c が同じ数字 であり マス b が最後に開けられた場合」、「マス b と マス c が同じ数字 であり マス a が最後に開けられた場合」はがっかりしてしまうパターンとなります。
あとはがっかりしない場合をカウントして全体の数で割れば答えが出力されます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
using System; using System.Collections.Generic; using System.Linq; class Program { // bool NextPermutation(int[] array, int start)の定義は同じなので省略 static void Main() { int[] vs1 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] vs2 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] vs3 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // マスの位置と番号をセットにする Dictionary<int, int> cells = new Dictionary<int, int>(); cells.Add(0, vs1[0]); cells.Add(1, vs1[1]); cells.Add(2, vs1[2]); cells.Add(3, vs2[0]); cells.Add(4, vs2[1]); cells.Add(5, vs2[2]); cells.Add(6, vs3[0]); cells.Add(7, vs3[1]); cells.Add(8, vs3[2]); int[][] patterns = { new int[] {0, 1, 2 }, // 上段横一列 new int[] {3, 4, 5 }, // 中段 new int[] {6, 7, 8 }, // 下段 new int[] {0, 3, 6 }, // 左列縦一列 new int[] {1, 4, 7 }, // 中列 new int[] {2, 5, 8 }, // 右列 new int[] {0, 4, 8 }, // 斜め new int[] {2, 4, 6 }, // 斜め }; int[] order = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; // i 個めのマスが何回目に開けられるか int hopeCount = 0; // がっかりしない回数 int totalCount = 0; // 全体の回数（順列の数 9! = 362880 と一致する） do { bool isDisappoint = false; foreach (int[] pattern in patterns) { int a = pattern[0]; int b = pattern[1]; int c = pattern[2]; if (cells[a] == cells[b] && order[a] < order[c] && order[b] < order[c]) isDisappoint = true; if (cells[a] == cells[c] && order[a] < order[b] && order[c] < order[b]) isDisappoint = true; if (cells[b] == cells[c] && order[b] < order[a] && order[c] < order[a]) isDisappoint = true; } totalCount++; if (!isDisappoint) hopeCount++; } while (NextPermutation(order, 0)); Console.WriteLine((double)hopeCount / totalCount); } } |
