python - Python中的重复排列

我想遍历大小为1的n维多维数据集的所有顶点。我知道我可以使用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 s。而不是使用上面的迭代器，然后计算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)

我的高中数学老师会把这些称为排列，一次包含n的2个元素，其中第一个元素重复n - ones时间，第二个元素重复，很容易表明它们中有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! / ones! / (n - ones)!计数完整的笛卡尔积，然后对n >= 10计数，这才是返回，这不是典型的用例。是否可以通过一些强大的ones < 2 voodoo或完全使用其他算法来加快上述代码的速度，这是一种优雅的方法吗？如果有什么不同，我将不在乎所产生排列的顺序。还是我应该辞职计数？

编辑

我对建议的解决方案做了一些时间安排。以itertools的顺序消耗顶点会生成顶点，计数始终是最快的。但是要使它们按数量排序生成，Eevee的列表排序解决方案是itertools.product最快的，从那时起Cam的解决方案是两者中最快的。

我接受了Cam的解决方案，因为它是最好地回答了所要求的解决方案。但是就我要在代码中实现的内容而言，我将辞职以计数。

最佳答案

对于您的3d多维数据集用例，Eevee的解决方案是正确的。

但是，为了娱乐并展示itertools的功能，以下是线性时间解决方案，可以推广到更高的维度:

from itertools import combinations

# n is the number of dimensions of the cube (3 for a 3d cube)
def generate_vertices(n):
    for number_of_ones in xrange(0, n + 1):
        for location_of_ones in combinations(xrange(0, n), number_of_ones):
            result = [0] * n
            for location in location_of_ones:
                result[location] = 1
            yield result

for vertex in generate_vertices(3):
    print vertex


# result:
# [0, 0, 0]
# [1, 0, 0]
# [0, 1, 0]
# [0, 0, 1]
# [1, 1, 0]
# [1, 0, 1]
# [0, 1, 1]
# [1, 1, 1]