6

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.

Jaime
  • 65,696
  • 17
  • 124
  • 159

5 Answers5

5

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.

Eevee
  • 47,412
  • 11
  • 95
  • 127
3

An (inefficient) alternative method:

>>> ['{0:03b}'.format(x) for x in range(8)]
['000', '001', '010', '011', '100', '101', '110', '111']

Or as tuples:

>>> [tuple(int(j) for j in list('{0:03b}'.format(x))) for x in range(8)]

[(0, 0, 0),
 (0, 0, 1),
 (0, 1, 0),
 (0, 1, 1),
 (1, 0, 0),
 (1, 0, 1),
 (1, 1, 0),
 (1, 1, 1)]

Sorted by number of vertices:

>>> sorted(_, key=lambda x: sum(x))

[(0, 0, 0),
 (0, 0, 1),
 (0, 1, 0),
 (1, 0, 0),
 (0, 1, 1),
 (1, 0, 1),
 (1, 1, 0),
 (1, 1, 1)]

Or using itertools:

>>> sorted(itertools.product((0, 1), repeat=3), key=lambda x: sum(x))

[(0, 0, 0),
 (0, 0, 1),
 (0, 1, 0),
 (1, 0, 0),
 (0, 1, 1),
 (1, 0, 1),
 (1, 1, 0),
 (1, 1, 1)]
Alex L
  • 8,748
  • 5
  • 49
  • 75
2

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

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]
Cam
  • 14,930
  • 16
  • 77
  • 128
  • Nice! This is the sort of thing I was looking for. Isn't the `set` operation unnecessary? – Jaime Jan 15 '13 at 03:23
  • @Jaime: No because sets have constant time access, which is needed for the part below. However you raise a good point which is that that section's a bit verbose. I've updated it to be more clear and probably a little faster – Cam Jan 15 '13 at 04:17
  • for your reference here was my original solution: https://gist.github.com/4536013 – Cam Jan 15 '13 at 04:21
1

It is not a bad idea to count depending on what you will do with the vertices because if you have to iterate over all of them doing something O(f(n)) is at least O(f(n)*2n), sorting them is O(n*2n). So it basically depends if f(n) majors n.

Aside from that here is a possible magic expression:

def magic_expression(ones, n):
    a = (0,) * (n - ones) + (1,) * ones
    previous = tuple()
    for p in itertools.permutations(a):
        if p > previous:
            previous = p
            yield p

With help from permutations with unique values.

This works because itertools.permutations yield sorted results. Note that a is initially sorted because zeros come first.

Community
  • 1
  • 1
Jan Segre
  • 574
  • 5
  • 12
  • this does not solve the problem. it asks for a way to iterate over the vertices of a cube sorted by the number of ones - this does not do that. – Cam Jan 15 '13 at 02:10
  • although not the best solution this does what's expected from the magic_expression of the question, that when combined with `for ones in xrange(3): ...` will yield the expected output. – Jan Segre Jan 15 '13 at 02:27
  • Oops! Indeed it does. Thanks for clarifying. – Cam Jan 15 '13 at 02:32
1

Following is some code that runs faster (for medium n) and several times faster (for large n) than that of Cam or Eevee. A time comparison follows.

def cornersjc (n):   # Re: jw code
    from itertools import product
    m = (n+1)/2
    k = n-m
    # produce list g of lists of tuples on k bits
    g = [[] for i in range(k+1)]
    for j in product((0,1), repeat=k):
        g[sum(j)].append(tuple(j))
    # produce list h of lists of tuples on m bits
    if k==m:
        h = g
    else:
        h = [[] for i in range(m+1)]
        for j in product((0,1), repeat=m):
            h[sum(j)].append(tuple(j))
    # Now deliver n-tuples in proper order
    for b in range(n+1):  # Deliver tuples with b bits set
        for lb in range(max(0, b-m), min(b+1,k+1)):
            for l in g[lb]:
                for r in h[b-lb]:
                    yield l+r

The timing results shown below are from a series of %timeit calls in ipython. Each call was of a form like
%timeit [x for x in cube1s.f(n)]
with the names cornersjc, cornerscc, cornersec, cornerses in place of f (standing for my code, Cam's code, Eevee's code, and my version of Eevee's method) and a number in place of n.

n    cornersjc    cornerscc    cornersec    cornerses

5      40.3 us      45.1 us      36.4 us      25.2 us    
6      51.3 us      85.2 us      77.6 us      46.9 us    
7      87.8 us      163 us       156 us       88.4 us    
8     132 us       349 us       327 us       178 us    
9     250 us       701 us       688 us       376 us    
10    437 us      1.43 ms      1.45 ms       783 us
11    873 us      3 ms         3.26 ms      1.63 ms
12   1.87 ms      6.66 ms      8.34 ms      4.9 ms

Code for cornersjc was given above. Code for cornerscc, cornersec, and cornerses is as follows. These produce the same output as cornersjc, except that Cam's code produces a list of lists instead of a list of tuples, and within each bit-count group produces in reverse.

def cornerscc(n):   # Re: Cam's code
    from itertools import combinations
    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

def cornersec (n):   # Re:  Eevee's code
    from itertools import product
    vertices = ((v.count(1), v)
                for v in product((0, 1), repeat=n))
    for count, vertex in sorted(vertices):
        yield vertex

def cornerses (n):   # jw mod. of Eevee's code
    from itertools import product
    for vertex in sorted(product((0, 1), repeat=n), key=sum):
        yield vertex

Note, the last three lines of cornersjc can be replaced by

            for v in product(g[lb], h[b-lb]):
                yield v[0]+v[1]

which is cleaner but slower. Note, if yield v is used instead of yield v[0]+v[1], the code runs faster than cornersjc but (at n=5) produces pair-of-tuple results like ((1, 0), (1, 1, 0)); when yield v[0]+v[1] is used, the code runs slower than cornersjc but produces identical results, a list of tuples like (1, 0, 1, 1, 0). An example timing follows, with cornersjp being the modified cornersjc.

In [93]: for n in range(5,13):
    %timeit [x for x in cube1s.cornersjp(n)]
   ....:     
10000 loops, best of 3: 49.3 us per loop
10000 loops, best of 3: 64.9 us per loop
10000 loops, best of 3: 117 us per loop
10000 loops, best of 3: 178 us per loop
1000 loops, best of 3: 351 us per loop
1000 loops, best of 3: 606 us per loop
1000 loops, best of 3: 1.28 ms per loop
100 loops, best of 3: 2.74 ms per loop
James Waldby - jwpat7
  • 8,593
  • 2
  • 22
  • 37