using System;

using System.Collections.Generic;

using System.Drawing;

​

namespace RoutePlanning

{

    public static class PathFinderTask

    {

        public static int[] FindBestCheckpointsOrder(Point[] checkpoints)

        {

            var distance = double.PositiveInfinity;

            var bestOrder = new int[checkpoints.Length];

            var order = new int[checkpoints.Length];

            MakeTrivialPermutation(checkpoints, order, ref bestOrder, 1, ref distance);

            return bestOrder;

        }

​

        //p - позиция

        private static int[] MakeTrivialPermutation(Point[] checkpoints, int[] order, 

                                        ref int[] bestOrder,int p, ref double distance)

        {

            var curOrder = new int[p];

            //for (int i = p; i < curOrder.Length; i++)

            //  curOrder[i] = order[i];

            Array.Copy(order, curOrder, p);

            var length = PointExtensions.GetPathLength(checkpoints, curOrder);

            if ((length < distance) || (p == order.Length))

            {

                bestOrder = (int[])order.Clone();

                distance = length;

                //return order;

                return bestOrder;

            }

            if (length < distance)

            {

                for (int i = 1; i < order.Length; i++)

                {

                    var index = Array.IndexOf(order, i, 0, p);

                    //if (index != -1)

                       // continue;

                    order[p] = i;

                    MakeTrivialPermutation(checkpoints, order, ref bestOrder, p + 1, ref distance);

                }

            }

            //var bestOrder = new int[size];

            //for (int i = 0; i < bestOrder.Length; i++)

            //  bestOrder[i] = i;

            //return bestOrder;

        return bestOrder;

        }

    }

}