我想要遍历大小为1的维立方体的所有顶点。我知道可以使用itertools.product
来实现:
>>> n = 3
>>> for j in it.product((0,1), repeat=n) :
... print j
...
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
但我需要根据坐标中的 1
的数量,对每个顶点进行不同的处理,例如 (0, 1, 1)
、(1, 0, 1)
和 (1, 1, 0)
将会接受相同的处理,因为它们都有两个 1
。我不想使用上面的迭代器,然后再计算 1
的数量,我想生成按 1
的数量排序的笛卡尔积,例如:
>>> for ones in xrange(n) :
... for seq in magic_expression(ones, n) :
... print ones, seq
...
0 (0, 0, 0)
1 (0, 0, 1)
1 (0, 1, 0)
1 (1, 0, 0)
2 (0, 1, 1)
2 (1, 0, 1)
2 (1, 1, 0)
3 (1, 1, 1)
我的高中数学老师会称这些为2个元素的排列组合,每次取
n
个元素,第一个元素重复n-ones
次,第二个元素重复ones
次,很容易证明共有n!/ ones!/(n-ones)!
种排列组合。
根据维基百科的描述,我们可以使用类似以下的方式以字典序生成它们:
def lexicographical(ones, n) :
perm = [0] * (n - ones) + [1] * ones
yield tuple(perm)
while True :
k = None
for j in xrange(n - 1) :
if perm[j] < perm[j + 1] :
k = j
if k is None :
break
l = k + 1
for j in xrange(k + 2, n) :
if perm[k] < perm[j] :
l = j
perm[k], perm[l] = perm[l], perm[k]
perm[k+1:] = perm[-1:k:-1]
yield tuple(perm)
但是,仅在完整的笛卡尔积中计数时,这只有在
n >= 10
且ones < 2
的情况下才会开始产生回报,而这并不是典型的用例。是否有一种优雅的方式可以加速上述代码,也许使用一些强大的itertools
魔法或完全使用不同的算法?如果有任何区别,我对生成的排列顺序毫不在意。或者我应该放弃计数吗?
编辑
我对提出的解决方案进行了一些时间测量。按照itertools.product
生成它们的顺序来消耗顶点,计数始终是最快的。但是,为了按照1的数量排序生成它们的顺序,Eevee对列表进行排序的解决方案在n <= 6
时最快,并且从那时起,Cam的解决方案是两个解决方案中最快的。
我接受了Cam的解决方案,因为它更好地回答了问题。但就我要在我的代码中实现的内容而言,我将放弃计数。
set
操作是不是没必要? - Jaime