python - Python 中的重复排列

Question

我想遍历 n 的所有顶点尺寸为 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 的数量对每个顶点进行不同的处理s 在其坐标中找到，即 (0, 1, 1) , (1, 0, 1)和 (1, 1, 0)都会得到相同的待遇，因为他们都有两个 1秒。而不是使用上面的迭代器，然后统计1的个数s，我想生成按 1 的数量排序的笛卡尔积s，类似以下内容:

>>> 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)!

根据 wikipedia我可以用这样的东西按字典顺序生成它们:

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生成它们，计数总是最快的。但是为了让它们按个数排序，Eevee 的列表排序解决方案对于 n <= 6 是最快的。 ，从那时起，Cam 的解决方案是两者中最快的。

我接受了 Cam 的解决方案，因为它能更好地回答问题。但就我要在我的代码中实现的内容而言，我将辞职以进行计数。

Answer 1

如果您编写了超过八行的代码来生成八个常量值，则说明出了问题。

除了嵌入我想要的列表之外，我会采用愚蠢的方式:

vertices = (
    (v.count(1), v)
    for v in itertools.product((0, 1), repeat=3)
)
for count, vertex in sorted(vertices):
    print vertex

除非您使用 1000 个超立方体，否则您不应该有任何巨大的性能担忧。