There is such a data set:

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

There is an array of arrays, these arrays are aggregated:

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

It is necessary to build all possible routes. The routes will be as follows:

 123 423 723 156 456 756 ...

The number of arrays can be unlimited, as well as their length. In essence, it is a tree with many vertices. Can you please tell us how you can implement an algorithm that collects all possible routes? Obviously, you can implement recursively, but my vain attempts have come to nothing.

Solution with a fixed number of arrays:

  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(); } } }

1 answer 1

As correctly written in the comments, you need a Cartesian product of sets (or you incorrectly described the problem and gave the wrong example for a fixed number of sets).

For a previously unknown number of sets, you can write this recursive version:

 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; } } }

A simpler option, using an iterator, but returning sequences in a slightly different order:

 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; } }

We use:

 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));
  • Thank you so much, great decision! As an alternative, wrote his own, also recursive, but from an academic point of view it is not in any comparison with yours. Thank you so much! - Sleeeper