从向量列表中创建所有可能组合的算法函数

本文关键字：组合 算法 函数 有可能 向量 列表 创建 | 更新日期: 2023-09-27 18:07:04

我有一个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();
        }
    }

工作得很好，但忽略了问题的方向方面。

方法不一定是递归的，尽管我认为这可能是最明智的方法

从向量列表中创建所有可能组合的算法函数

看起来像广度优先搜索:

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

测试
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)
相关文章：