在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)都将接收相同的tratment,因为它们都有两个1s.而不是使用上面的迭代器,然后计算1s 的数量,我想生成按1s 的数量排序的笛卡尔积,类似于:

>>> 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生成它们,计数总是最快的.但是为了让它们按照数量排序,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超立方体,否则不应该有任何巨大的性能担忧.

Answer 2

对于您的 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]