Permutations with repetition in Python

Question

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)

But I need to treat differently each of the vertices, depending on the number of 1s found in its coordinates, i.e. (0, 1, 1), (1, 0, 1) and (1, 1, 0) will all receive the same tratment, as they all have two 1s. Rather than using the above iterator, and then counting the number of 1s, I would like to generate the cartesian product ordered by number of 1s, something along the lines of:

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

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)

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

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.

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.

Answer 1

If you've written more than eight lines of code to generate eight constant values, something has gone wrong.

Short of just embedding the list I want, I'd do it the dumb way:

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

Unless you're working with 1000-hypercubes, you shouldn't have any huge performance worries.