I want to iterate over all the vertices of an n dimensional cube of size 1. I know I could do that with itertools.product as follows:

>>> 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，因为它们都具有两个 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 - 那些倍，而第二的人次，然后很容易表明，有 N！ /人！ /（N - 的）！其中

My high school math teacher would have called these something like permutations of 2 elements taken n at a time, where the first element repeats n - ones times, and the second ones times, and it is easy to show that there are n! / ones! / (n - ones)! of them.

根据维基百科我可以生成它们的字典顺序像这样的东西：

According to wikipedia I can generate them in lexicographical order with something like this:

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'GT; = 10 ，然后只对那些＆LT; 2 ，这不是典型的用例。是否有加快我的code以上，或许与一些强大的 itertools 巫术，或者干脆使用不同的算法，一种优雅的方式？如果这有什么差别，我不关心生产的排列顺序。或者我应该辞职，自己去计算？

But timing it, this only starts to pay-off against counting in the full cartesian product for n >= 10, and then only for ones < 2, which is not the typical use case. Is there an elegant way of speeding up my code above, perhaps with some powerful itertools voodoo, or using a different algorithm altogether? If it makes any difference, I couldn't care less about the ordering of the permutations produced. Or should I resign myself to counting?

修改的

EDIT

我没有对提出的解决方案有些计时。消费顶点的顺序 itertools.product 生成它们的计数始终是最快的。但让他们产生订购的那些数量，排序名单伊布的解决方案是最快的 N'LT; = 6 ，并从那时起凸轮的解决方案是最快的二。

I did some timings on the proposed solutions. Consuming the vertices in the order itertools.product generates them an counting is always the fastest. But to have them generated ordered by number of ones, Eevee's solution of sorting the list is the fastest for n <= 6, and from then on Cam's solution is the fastest of the two.

我已经接受了凸轮的解决方案，因为它是一个更好的回答做了哪些要求。但至于什么我打算在我的code来实现，我准备辞职自己计数。

I have accepted Cam's solution, because it is the one that better replied to what was being asked. But as far as what I am going to implement in my code, I am going to resign myself to counting.

推荐答案

有关您的用例的3D立方体，伊布的解决方案是正确的。

For your use-case of 3d cubes, Eevee's solution is the correct one.

不过，对于娱乐和展示itertools的力量，这里有一个线性时间的解决方案，可以推广到更高的维度：

However for fun and to demonstrate the power of itertools, here's a linear-time solution that generalizes to higher dimensions:

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]