Q46 ソートの交換回数の最少化

C#のソース

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

class Program
{
    static void Main()
    {
        Console.WriteLine("N=3での解={0}", Solve(3));
        Console.WriteLine("N=7での解={0}", Solve(7));
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal int[] BanArr;
    }

    static int Solve(int pN)
    {
        var que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Level = 0;
        WillEnqueue.BanArr = Enumerable.Range(1, pN).ToArray();
        int UB = WillEnqueue.BanArr.GetUpperBound(0);
        que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<int>();
        VisitedSet.Add(BanToInt(WillEnqueue.BanArr));

        int AnswerCnt = 0;
        while (que.Count > 0) {
            JyoutaiDef Dequeued = que.Dequeue();
            AnswerCnt += Dequeued.Level;

            for (int I = 0; I <= UB; I++) {
                for (int J = I + 1; J <= UB; J++) {
                    WillEnqueue.Level = Dequeued.Level + 1;
                    WillEnqueue.BanArr = (int[])Dequeued.BanArr.Clone();
                    WillEnqueue.BanArr[I] = Dequeued.BanArr[J];
                    WillEnqueue.BanArr[J] = Dequeued.BanArr[I];

                    if (VisitedSet.Add(BanToInt(WillEnqueue.BanArr)))
                        que.Enqueue(WillEnqueue);
                }
            }
        }
        return AnswerCnt;
    }

    static int BanToInt(int[] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= pBanArr.GetUpperBound(0); I++) {
            sb.Append(pBanArr[I]);
        }
        return int.Parse(sb.ToString());
    }
}

実行結果

N=3での解=7
N=7での解=22212

解説

ゴールから逆方向に幅優先探索して、
全ノードのレベルの合計を求めてます。