Как конвертировать IEnumerable в массив?

Question

Выполняю учебную задачу по поиску кратчайшего маршрута для обхода списка чекпоинтов роботом-пылесосом)) Нужно написать класс, основной метод которого при помощи пары вспомогательных переберет все возможные варианты маршрутов, оценит расстояния и вернет лучший найденный маршрут. Как я не ломал голову, а всё же мне кажется, что здесь лучшим решением будет применение "ленивой" генерации маршрутов (yield return). Проблема в том, что в этом случае возвращаемое значение у такого метода должно быть одним из этих четырех:

IEnumerable,
IEnumerable<T>,
IEnumerator,
IEnumerator<T>.

С интерфейсами я ещё не знаком, это будет объясняться в курсе далее. Может скажу глупость, но мне нужно вместо IEnumerable<T> получить обычный массив. Вроде бы это можно сделать так же, как и с любой другой коллекцией - метод ToArray(), и дело в шляпе. Только вот для IEnumerable используется какая-то незнакомая мне перегрузка этого метода, и я никак не могу понять, как же все таки этот несчастный массив получить. Подскажите, пожалуйста. Было бы здорово посмотреть правильную запись - вроде бы это должна быть всего одна строка. Заранее спасибо!

Answer 1

Вам нужно решить задачу или пообсуждать IEnumerable?

Поскольку набор маршрутов представляет из себя дерево, то для решения нужно использовать рекурсию.

Я бы собрал координаты чекпоинтов в двухсвязный список.

Беру (вырываю) из списка чекпоинты по очереди и спрашиваю у каждого кратчайший маршрут (список чекпоинтов и длину) по оставшимся в списке. Прибавляю к длине маршрута расстояние до этого чекпоинта и нахожу минимальный маршрут.

P. S. Вот вариант решения. Из оптимизации здесь матрица расстояний между точками и отсечение длинных веток. Причём, если сделать матрицу треугольной, то время выполнения увеличивается. Входные данные - строки с координатами точек, разделёнными табуляцией. В первой строке - начальная точка. Конечная точка - произвольная. Если нужна определённая конечная точка, то алгоритм нужно немного изменить.

namespace VCRobot;

internal class Program {

    class Point {
        public int X, Y, Id; public int Next, Previous;
        public Point() { }
        public Point(int x, int y, int id) {
            X = x; Y = y; Id = id; Next = id + 1; Previous = id - 1;
        }
        public double DistanceM(Point p) {
            return r[Id, p.Id] ??=
                Math.Sqrt(Math.Pow(p.X - X, 2) + Math.Pow(p.Y - Y, 2));
        }
    }

    static int N;
    static Point[] points;
    static int[] route, shroute;
    static double?[,] r;
    static double shdist;

    static void Remove(int i) {
        var p = points[i];
        points[p.Previous].Next = p.Next; points[p.Next].Previous = p.Previous;
    }

    static void Restore(int i) {
        var p = points[i]; points[p.Previous].Next = points[p.Next].Previous = i;
    }

    static double? GetRoute(int rootnode, int M, double baseroute) {
        Remove(rootnode); var curnode = points[0].Next; double? mindist = null;
        for (int i = 0; i < M; i++) {
            route[N - M - 1] = rootnode;
            var dist = points[rootnode].DistanceM(points[curnode]);
            var basedist = baseroute + dist;
            if (basedist < shdist) {
                var tailor = M == 1 ? 0 : GetRoute(curnode, M - 1, basedist);
                if (tailor != null) {
                    var curdist = baseroute + dist + (double)tailor;
                    mindist = shdist - baseroute;
                    if (M == 1 && curdist < shdist) {
                        shdist = curdist; route[N - 1] = curnode;
                        Array.ConstrainedCopy(route, 0, shroute, 0, N);
                    }
                }
            }
            curnode = points[curnode].Next;
        }
        Restore(rootnode); return mindist;
    }

    static void Main(string[] args) {
        var lines = File.ReadAllLines("data.txt");
        var pts = new List<Point>([new Point() { Next = N = 1 }]);
        pts.AddRange(lines.Select(s => { var sa = s.Split('\t');
            return new Point(Convert.ToInt32(sa[0]), Convert.ToInt32(sa[1]), N++);
        }));
        pts.Add(new Point() { Previous = N - 1 }); points = pts.ToArray();
        r = new double?[N, N]; route = new int[--N]; shroute = new int[N];
        shdist = double.MaxValue; var t = DateTime.Now; GetRoute(1, N - 1, 0);
    var s = DateTime.Now - t;
    Console.WriteLine($"Shortest route is {shdist}: {string.Join(' ', shroute)}");
        Console.WriteLine($"Execution time is {s.TotalMilliseconds:F0} ms");
    }
}

Тест 1 - "data.txt" и результат:

1   2
3   4
1   4
3   2
1   3
4   2
-3  -4
-1  -4
-3  -2
-1  -3
-4  -2
1   1
-1  -1

-->

Shortest route is 20,30056307974577: 1 5 3 2 6 4 12 13 10 8 7 9 11
Execution time is 27 ms

Тест 2 - "data.txt" и результат:

1   1
8   8
5   5
3   3
9   9
6   6
11  11
2   2
13  13
10  10
12  12
4   4
7   7

-->

Shortest route is 16,970562748477146: 1 8 4 12 3 6 13 2 5 10 7 11 9
Execution time is 15 ms

P. P. S. Задача не для новичка, конечно.

Answer 2

У вас ошибка в том что после преобразования коллекции в массив, которая внутри содержит массив, получается двойной(зубчатый) массив. Соответственно чтобы принять его вам нужно переменную int[][] bestOrder = ...

А по поводу yield return представьте что он возращает одно значение в последовательности, каждый раз когда это понадобиться при перечеслении этой последовательности например в Foreach, чтобы взять один элемент он будет обращаться к вашему методу брать элемент в Yield return и возращаться обратно в логику foreach, либо в том же методе .ToArray() будет происходить тоже самое, потому что .ToArray внутри себя переберает вашу последовательность, примерно так же как и foreach, но только с сохранением кажого элемента в результирующий массив.

Answer 3

Чтобы получить один элемент из коллекции IEnumerable<int[]>, которую возвращает метод MakeTrivialPermutation, необходимо к нему обратиться конкретно. Либо, допустим, через ElementAt(int index), либо через Last(), First() и т.д. После чего этот элемент уже не нужно будет преобразовывать в одномерный массив посредством ToArray().

int[] bestOrder = MakeTrivialPermutation(checkpoints.Length).ElementAt(0);
int[] bestOrder = MakeTrivialPermutation(checkpoints.Length).Last();

БЛОГ НА HUSL

Как конвертировать IEnumerable в массив?

Ответы (3 шт):