如果我们希望覆盖搜索空间,就好说了所有三胞胎(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)
,等...
还有会产生这种模式的算法的名称吗?
这段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] 删除。
我来说两句