はじめに
勉強のためにAtCoderを始めたが、せっかくなら強くなりたいと思いアルゴリズムを学んでいる。
そんな中こちらの記事で、単純な数え上げでは解けない問題として、順列全探索が挙げられていた。
私の記事では順列全探索の簡単な応用例をC#で見たのち、ABC 145 C-AverageLength という問題の回答記録に入っていく。
順列全探索とは
例えば、3, 1, 2という数列があったとする。この列を並べる方法は3!=6通りある。
この3!=6通りの並べ方全てについて何らかの処理を行いたい、特定の並べ方を見つけたい、そんなときに使われるのが順列全探索である。
サンプルコードを以下に示す。大きく2つのメソッドが動いている。
順列全探索はPermuteメソッドが行っている。
PermutePrintメソッドは内部でPermuteメソッドを呼び出して順列全探索を行い、
探索された順列を表示していく。
Permuteメソッドは再帰処理を行っており、順々に数値・文字を確定させていく構造になっている。今回は並び替えた順列を辞書順に表示させたかったので、useフラグを加えている。辞書順でなくても良いなら少しだけシンプルに書ける。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Practice
{
class Program
{
static void Main()
{
Console.WriteLine("=== int: 3, 1, 2 ===");
PrintPermutations(new[] { 3, 1, 2 });
Console.WriteLine("\n=== char: c, a, b ===");
PrintPermutations(new[] { 'c', 'a', 'b' });
}
/// <summary>
/// 並び替え結果を順に表示するメソッド
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="elements">並び替えたい配列</param>
static void PrintPermutations<T>(T[] elements) where T : IComparable<T>
{
Array.Sort(elements); // 辞書順に出力するための昇順ソート
List<T[]> results = new List<T[]>(); // 順列の保存用
// 配列を実際に並び替えるメソッドを呼ぶ
Permute(elements, new bool[elements.Length], new T[elements.Length], 0, results);
// 表示処理を行う
Console.WriteLine($"総数: {results.Count}通り");
foreach (var perm in results)
{
Console.WriteLine(string.Join(", ", perm));
}
}
/// <summary>
/// 実際に配列を並び替えるメソッド
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="elements">並び替えたい配列</param>
/// <param name="used">各要素を使ったか否かのフラグ</param>
/// <param name="current">現在構築中の配列(作業台)</param>
/// <param name="depth">何桁目を決めているか</param>
/// <param name="results">並び替えの結果を格納する</param>
static void Permute<T>(T[] elements, bool[] used, T[] current, int depth, List<T[]> results)
{
// 全桁確定したら保存して戻る
if (depth == elements.Length)
{
results.Add((T[])current.Clone());
return;
}
for (int i = 0; i < elements.Length; i++)
{
if (used[i]) continue; // 使用済みはスキップ
used[i] = true; // 使用済みフラグを立てる
current[depth] = elements[i]; // depth桁目を確定させる
Permute(elements, used, current, depth + 1, results); // 次の桁へ移行する
used[i] = false; // バックトラック(これが無いと上手く行かなかった)
}
}
}
}
where以降は、Array.Sort()を行うため(ソートの基準を教えるため)に必要
PrintPermutationsが受け入れる型Tは比較可能なもの (IComparable<T>を実装している型) のみに限定している
new bool[サイズ]はfalseで初期化された配列を作る
new T[サイズ]は値型なら0,参照型ならnullで初期化された配列を作る
ABC 145 C-Average Length
順列全探索が何なのかは何となく分かった気がする。
ただ何に使うのかはやっぱり実際に解いてみた方が良い。
というわけで練習として以下の問題を使う。
XY座標上にあるN個の街を、1つずつ順番に回ることを考える。
回り方はN!通りあるが、その移動距離の平均を求めて出力せよ。
......短くまとめるとこんな感じ。
このN!通りの回り方を1つ1つ数え挙げるために順列全探索を利用する。
回答
私の最終的な回答はこんな感じになった。
using System;
using System.Collections.Generic;
using System.Linq;
namespace C_AverageLength
{
internal class Program
{
static void Main(string[] args)
{
// 街数
int countOfTown = int.Parse(Console.ReadLine());
// 街ごとの座標
Dictionary<int, (int, int)> point = new Dictionary<int, (int, int)>(countOfTown);
// 順列探索用
int[] array = Enumerable.Range(1, countOfTown).ToArray();
// 順列格納用
List<int[]> result = new List<int[]>();
// 答え(距離合計)格納用
double answer = 0;
// 街数の階乗を取得
int factorial = 1;
for(int i = 1; i <= countOfTown; i++)
{
factorial *= i;
}
// 街ごとに座標を取得する
for (int i = 0; i < countOfTown; i++)
{
string[] input = Console.ReadLine().Split(' ');
int x = int.Parse(input[0]);
int y = int.Parse(input[1]);
point.Add(i+1, (x, y));
}
// 順列全探索を行う
Permute(0, array, result);
// 計算
for (int i = 0; i < factorial; i++)
{
// 計算対象の順列(街の番号の配列)を抜き出す
int[] tmp = result[i];
// 距離を計算
for(int j = 0; j < tmp.Length - 1; j++)
{
(int x1, int y1) = point[tmp[j]];
(int x2, int y2) = point[tmp[j + 1]]; // 辞書に街の番号を入れて座標を出す
answer += Math.Sqrt(Math.Pow(x1-x2, 2) + Math.Pow(y1-y2, 2));
}
}
// 答えを出力
Console.WriteLine(answer / factorial);
}
// 深さは0,arrayの数値を入れ替える
static void Permute(int depth, int[] array, List<int[]> result)
{
if (depth == array.Length)
{
result.Add(array.ToArray()); // コピーを追加
return;
}
for (int index = depth; index < array.Length; index++)
{
(array[depth], array[index]) = (array[index], array[depth]);
Permute(depth + 1, array, result);
(array[depth], array[index]) = (array[index], array[depth]);
}
}
}
}
反省点
偉そうに書いてきたけど、自力では解けなかったのでAIの力も借りている。
及ばなかった点は以下の点。
-
staticに対する知識不足
Mainはstaticなのに、最初はPermuteメソッドにstaticが付いておらず、インスタンス生成無しで呼び出せなかった。staticメソッドか非staticメソッドは呼べないと学んだ。 -
arrayインスタンスの共有・複製に対する知識不足
配列が保持するのはインスタンスの参照だということを忘れたままPermuteを改造していた。焦っていたということもあるが配列そのものを差し替えたい場合はコピーが必要と心得ておく。
総じて「やりたいことをコーディングに落とし込む」技能が足りていないなと感じた。(だから競技プログラミングを通して鍛えているわけではあるのだけれど)
ひな形
ひな型を作るとしたらこんな感じだろうか...？
と言っても上のコードを日本語で書き直したものに過ぎないが。
// 0,1,2,...,要素数-1 の配列を作る
int[] 順列 = Enumerable.Range(0, 要素数).ToArray();
List<int[]> 全順列 = new List<int[]>();
// 順列全探索
Permute(0, 順列, 全順列);
// 全順列に対して処理
foreach (int[] ひとつの順列 in 全順列)
{
// 処理
}
// 順列構築メソッド
static void Permute(確定済み桁数, int[] 順列, List<int[]> 全順列)
{
if (確定済み桁数が順列の長さと同じ)
{
全順列.Add(順列.ToArray()); // コピーして保存
return;
}
for (index = 確定済み桁数; 候補 < 順列.Length; 候補++)
{
// 確定済み桁数の位置に候補を持ってくる
(順列[確定済み桁数], 順列[index]) = (順列[index], 順列[確定済み桁数]);
// 次の桁を確定しに行く
Permute(確定済み桁数 + 1, 順列, 全順列);
// 元に戻す（バックトラック）
(順列[確定済み桁数], 順列[index]) = (順列[index], 順列[確定済み桁数]);
}
}
参考