алгоритмическая функции для создания всех возможных комбинаций из списка векторов

Question

у меня есть список списков Int <List<List<int>>, который представляет собой направленный вектор

, например

(1,2) 
(1,3) 
(2,4) 
(3,5) 
(4,3) 
(5,1) 

и я хочу, чтобы создать все возможные маршруты с этими векторами, так что конечный маршрут не создает бесконечный круг (заканчивается на себя)

так:

(1,2) 
(1,3) 
(2,4) 
(3,5) 
(4,3) 
(5,1) 
(1,2,4) 
(1,2,4,3) 
(1,2,4,3,5) 
(1,2,4,3,5,1) 
(1,3,5) 
(1,3,5,1) 
(2,4,3) 
(2,4,3,5) 
(2,4,3,5,1) 
(2,4,3,5,1,2) 
(3,5,1) 
etc... 

Я не нашел эффективного способа совершения такой вещи.

Я предыдущий попытался создать все возможные комбинации, используя

private IEnumerable<int> constructSetFromBits(int i) 
    { 
     for (int n = 0; i != 0; i /= 2, n++) 
     { 
      if ((i & 1) != 0) 
       yield return n; 
     } 
    } 

    public IEnumerable<List<T>> ProduceWithRecursion(List<T> allValues) 
    { 
     for (var i = 0; i < (1 << allValues.Count); i++) 
     { 
      yield return ConstructSetFromBits(i).Select(n => allValues[n]).ToList(); 
     } 
    } 

, который работал хорошо, но игнорировали направление аспект проблемы.

Метод не должен быть рекурсивными, хотя я подозреваю, что может быть наиболее разумным способом пойти об этом

Answer 1

Похоже широта первого поиска:

private static IEnumerable<List<int>> BreadthFirstSearch(IEnumerable<List<int>> source) { 
    List<List<int>> frontier = source 
    .Select(item => item.ToList()) 
    .ToList(); 

    while (frontier.Any()) { 
    for (int i = frontier.Count - 1; i >= 0; --i) { 
     List<int> path = frontier[i]; 

     yield return path; 

     frontier.RemoveAt(i); 

     // prevent loops 
     if (path.IndexOf(path[path.Count - 1]) < path.Count - 1) 
     continue; 

     int lastVertex = path[path.Count - 1]; 

     var NextVertexes = source 
     .Where(edge => edge[0] == lastVertex) 
     .Select(edge => edge[1]) 
     .Distinct(); 

     foreach (var nextVertex in NextVertexes) { 
     var nextPath = path.ToList(); 

     nextPath.Add(nextVertex); 

     frontier.Add(nextPath); 
     } 
    } 
    } 
} 

Test

List<List<int>> list = new List<List<int>>() { 
    new List<int>() {1, 2}, 
    new List<int>() {1, 3}, 
    new List<int>() {2, 4}, 
    new List<int>() {3, 5}, 
    new List<int>() {4, 3}, 
    new List<int>() {5, 1}, 
}; 

var result = BreadthFirstSearch(list) 
    .Select(way => string.Format("({0})", string.Join(",", way))); 

Console.Write(string.Join(Environment.NewLine, result)); 

Результат:

(5,1) 
(4,3) 
(3,5) 
(2,4) 
(1,3) 
(1,2) 
(1,2,4) 
(1,3,5) 
(2,4,3) 
(3,5,1) 
(4,3,5) 
(5,1,3) 
(5,1,2) 
(5,1,2,4) 
(5,1,3,5) 
(4,3,5,1) 
(3,5,1,3) 
(3,5,1,2) 
(2,4,3,5) 
(1,3,5,1) 
(1,2,4,3) 
(1,2,4,3,5) 
(2,4,3,5,1) 
(3,5,1,2,4) 
(4,3,5,1,3) 
(4,3,5,1,2) 
(5,1,2,4,3) 
(5,1,2,4,3,5) 
(4,3,5,1,2,4) 
(3,5,1,2,4,3) 
(2,4,3,5,1,3) 
(2,4,3,5,1,2) 
(1,2,4,3,5,1)