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

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

测试

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)