あみだくじ

ある人の課題を手伝ったのでメモ。下のあみだくじで、「上の 1, 2, 3, 4, 5 がそれぞれ下の同じ数字に行くように横線を引きなさい」という問題でした。

パッと見で全然わからなかったのですが、線形代数の問題とのことで、置換とか互換とか、そのあたりの「対称群」の概念で解けるようです。まあ線形代数なんて既に忘却の彼方ですが、再び勉強しつつプログラムで解いてみました。またきっと忘れるので記録しておきます。

（以下、多分数学的には全然正確でないのでご容赦ください）

置換

上と下の数字をまとめて書くと、
$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 2 & 1 & 4 \end{pmatrix}$
となります。これを置換と言うそうです。まあ名前なんてどうでもいいんですが、とにかく上の行の 1 2 3 4 5 を下の行の 5 3 2 1 4 にどうやったら変形できるかということを考えます。

互換

変形にあたって使える手段は、隣同士の数字を入れ替えるだけとします。たとえば 4 5 3 2 1 の1番目と2番目を入れ替えて 5 4 3 2 1 にすると言った具合です。入れ替えた数字の位置を使って、この変形を (1 2) とあらわすことにします。これを互換と言うそうです。

では、1 2 3 4 5 を、隣同士を入れ替えることによって 5 3 2 1 4 に変えてみます。

変形手順をまとめると、次の通りです。（互換の積）

(4 5)(3 4)(2 3)(1 2)(3 4)(2 3)(3 4)

さてここであみだくじを思い出します。「隣同士の数字を入れ替える」というのは、あみだくじで言うと「横線を一つ引く」ことに相当します。つまり、今求めたそれぞれの互換を始めから順に、数字の線同士を横線で結べば、これで問題が解けたことになります。

実際になぞってみると、題意は満たせていることが確認できます。もっとも、これが最適解かどうかはよくわかりません。

今回互換を隣同士の入れ替えに限ったのは問題があみだくじであるためです。互換自体は隣同士でなくても良いものです。

C#で実装

ある意味ここが本題。なんでもプログラムにしてみないと気が済まない性質なので書いてみました。LINQをいっぱい使ってみようとしましたが、結局コアの部分は信頼と実績のforで書きました。

このプログラムでは互換が絶対転倒しないのがまずい気もしますが、あみだを解くことに限ればどうでもいいと思うので見なかったことにします。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Amida
{
    class Program
    {
        /// <summary>
        /// 配列の要素を入れ替え
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        /// <param name="i1"></param>
        /// <param name="i2"></param>
        static void Swap<T>(IList<T> list, int i1, int i2)
        {
            T temp = list[i2];
            list[i2] = list[i1];
            list[i1] = temp;
        }
        /// <summary>
        /// デバッグ用のリスト要素出力
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        static void PrintList<T>(IList<T> list)
        {
            foreach(T item in list)
            {
                Console.Write("{0} ", item.ToString()));
            }
            Console.WriteLine();
        }
        /// <summary>
        /// エラーメッセージを赤で表示
        /// </summary>
        /// <param name="format"></param>
        /// <param name="arg"></param>
        static void ErrorMessage(string format, params object[] arg)
        {
            ConsoleColor colorTemp = Console.ForegroundColor;
            Console.ForegroundColor = ConsoleColor.Red;
            Console.WriteLine(format, arg);
            Console.ForegroundColor = colorTemp;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            // 数値の入力
            List<int> vecTopOrig;
            List<int> vecBottomOrig;
            while (true)
            {
                try
                {
                    Console.Write("上の数 > ");
                    vecTopOrig = Console.ReadLine().Split(' ').Select(str => int.Parse(str)).ToList();
                    Console.Write("下の数 > ");
                    vecBottomOrig = Console.ReadLine().Split(' ').Select(str => int.Parse(str)).ToList();
                }
                catch
                {
                    continue;
                }

                if (vecTopOrig.Count != vecBottomOrig.Count)
                    ErrorMessage("上と下で数の個数が違います");
                else if (vecTopOrig.Count < 2)
                    ErrorMessage("数の個数が少なすぎます");
                else if (vecTopOrig.Count != vecTopOrig.Distinct().Count() || vecBottomOrig.Count != vecBottomOrig.Distinct().Count())
                    ErrorMessage("数の重複があります");
                else if(!vecTopOrig.TrueForAll(item => vecBottomOrig.Contains(item)))
                    ErrorMessage("上もしくは下のみにしか含まれない数があります");
                else
                    break;
            }

            //PrintList(vecTopOrig);
            //PrintList(vecBottomOrig);

            List<int> vecTop = new List<int>(vecTopOrig);
            List<int> vecBottom = new List<int>(vecBottomOrig);

            // 上の数字をswapにより下の数字の並びと同じにする
            for (int i = 0; i < vecBottom.Count - 1; i++)
            {
                int j = vecTop.FindIndex(item => item == vecBottom[i]);
                for (int k = j; k > i; k--)
                {
                    Console.WriteLine("({0} {1})", k - 1 + 1, k + 1);
                    Swap(vecTop, k - 1, k);
                }
            }

            //PrintList(vecTop);
            //PrintList(vecBottom);

            Console.WriteLine();
            Console.WriteLine("何かキーを押すと終了します");
            Console.Read();
        }
    }
}

数字の個数に制限はありません。スペース区切りで数字を上の分と下の分それぞれ入力すると、互換の積を出力します。以下、出力例です。