广度第一次迭代？

debugcn 发表于 Dev

戴夫·库西诺（Dave Cousineau）

如果我们希望覆盖搜索空间，就好说了所有三胞胎(x, y, z)，其中x，y和z是之间1和n，我们可以使用嵌套的循环，从而做到这一点：

for (int x = 1; x <= n; x++)
   for (int y = 1; y <= n; y++)
      for (int z = 1; z <= n; z++)

这会产生三胞胎：(1, 1, 1)，(1, 1, 2)，(1, 1, 3)，(1, 1, 4)，等等，并且是有效的“深度优先搜索”或深度第一次迭代。

有没有办法以更“广度优先”的方式进行迭代？这样的迭代将以类似于以下的顺序生成三元组：

(1, 1, 1)，(2, 1, 1)，(1, 2, 1)，(1, 1, 2)，(2, 2, 1)，(2, 1, 2)，(1, 2, 2)，(2, 2, 2)，(3, 1, 1)，等...

还有会产生这种模式的算法的名称吗？

戴夫·库西诺（Dave Cousineau）

这段C＃代码以良好的顺序生成了我描述的模式，但是我觉得有更好的方法来实现。

void Visit(ISet<Tuple<int, int, int>> pSet, int pX, int pY, int pZ) {
   var value = Tuple.Create(pX, pY, pZ);
   if (pSet == null)
      Console.WriteLine(value);
   else if (!pSet.Contains(value)){
      pSet.Add(value);
      Console.WriteLine(value);
   }
}

void Iterate() {
   const int n = 5;
   for (int x = 1; x <= n; x++) {
      var set = new HashSet<Tuple<int, int, int>>();
      for (int y = 1; y <= x; y++)
         for (int z = 1; z <= y; z++) {
            Visit(set, z, y, x);
            Visit(set, z, x, y);
            Visit(set, y, z, x);
            Visit(set, y, x, z);
            Visit(set, x, z, y);
            Visit(set, x, y, z);
         }
   }
}

该代码生成模式，而无需维护任何列表或进行任何冲突检查。我已经确认它会生成无重复的n³元组（最多n = 500）。唯一的问题是，这仅适用于迭代3个元组的int的特定情况，而不适用于任何数量的任何类型的collection。

static void Iterate() {
   const int n = 500;
   for (int x = 1; x <= n; x++) {
      for (int y = 1; y <= x; y++)
         for (int z = 1; z <= y; z++) {
            Visit(z, y, x);
            if (x == y && y == z && x == z)
               continue;

            if (x != y)
               Visit(z, x, y);

            if (z != y) {
               Visit(y, z, x);
               Visit(y, x, z);
            }

            if (x != y && x != z) {
               Visit(x, z, y);
               if (z != y)
                  Visit(x, y, z);
            }
         }
   }
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。