0

Есть такой набор данных:

var replies1 = new List<int>() { 1, 4, 7 };
var replies2 = new List<int>() { 2, 5, 8 };
var replies3 = new List<int>() { 3, 6, 9 };

Есть массив массивов, эти массивы агрегирующий:

var mas =  new List<List<int>>() { replies1, replies2, replies3 };

Необходимо построить все возможные маршруты. Маршруты будут такими:

123
423
723
156
456
756
...

Количество массивов может быть неограниченным, как и их длина. По сути это дерево со множеством вершин. Подскажите пожалуйста, как можно реализовать алгоритм, который соберет все возможные маршруты? Очевидно, что реализовать можно рекурсивно, но мои тщетные попытки ни к чему не привели.

Решение с фиксированным количеством массивов:

 for (int i = 0; i < replies1.Count; i++)
            {
                for (int j = 0; j < replies2.Count; j++)
                {
                    for (int k = 0; k < replies3.Count; k++)
                    {
                        Console.Write(String.Format("{0}, {1}, {2}", replies1[i], replies2[j], replies3[k]));
                        Console.WriteLine();
                    }

                }

            }
2
  • 1
    Какова длина маршрута? Может ли маршрутом быть 1 или 1-2-3-6-9-8-5-4-7? Какое направления маршрутов? Будет ли считаться маршрут 7-8-9 и 9-8-7 одинаковым? Если вы хотите обходить деревья, так сделайте из своей матрицы деревья.
    – Jagailo
    26 июн 2018 в 2:06
  • 4
    Это называется декартово произведение (cartesian product). forum.algolist.ru/source-implementation-programm/… или rsdn.org/forum/cpp.applied/5081640.hot
    – MBo
    26 июн 2018 в 2:29

1 ответ 1

1

Как правильно написали в комментариях, вам нужно декартово произведение множеств (или вы неправильно описали задачу и привели неправильный пример для фиксированного числа множеств).

Для заранее неизвестного числа множеств можно написать такой рекурсивный вариант:

static class Extensions
{
    public static IEnumerable<T> Cartesian<T>(this IEnumerable<IEnumerable<T>> source, Func<T, T, T> aggregator)
    {
        var list = source as List<IEnumerable<T>> ?? source.ToList();
        return CartesianImpl(list, list.Count - 1, aggregator);
    }

    static IEnumerable<T> CartesianImpl<T>(List<IEnumerable<T>> list, int startIndex, Func<T, T, T> aggregator)
    {
        if (startIndex > 0)
        {
            foreach (var y in list[startIndex])
                foreach (var x in CartesianImpl(list, startIndex - 1, aggregator))
                    yield return aggregator(x, y);
        }
        else
        {
            foreach (var e in list[startIndex])
                yield return e;
        }
    }
}

Более простой вариант, с использованием итератора, но возвращающий последовательности немного в другом порядке:

static class Extensions
{
    public static IEnumerable<T> Cartesian<T>(this IEnumerable<IEnumerable<T>> source, Func<T, T, T> aggregator)
    {
        var enumerator = source.GetEnumerator();
        if (!enumerator.MoveNext()) return Enumerable.Empty<T>();
        var result = enumerator.Current;
        while (enumerator.MoveNext())
        {
            var current = enumerator.Current;
            result = result.SelectMany(e => current, (x, y) => aggregator(x, y));
        }
        return result;
    }
}

Используем:

var replies1 = new List<int>() { 1, 4, 7 };
var replies2 = new List<int>() { 2, 5, 8 };
var replies3 = new List<int>() { 3, 6, 9 };
var mas = new List<List<int>>() { replies1, replies2, replies3 };
var res = mas.Cartesian((x, y) => 10 * x + y);
Console.WriteLine(string.Join("\n", res));
1
  • Огромное спасибо, прекрасное решение! В качестве альтернативы написал свое, также рекурсивное, но с академической точки зрения оно не идет ни в какое сравнении с Вашим. Огромнейшее спасибо!
    – Sleeeper
    26 июн 2018 в 20:07

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.