Enumerate 3-permutations with lowest numbers first in Python

Question

This works in Python to display all the 3-permutations of [0, 1, 2, 3, 4] :

import itertools
N = 5
for p in itertools.permutations(range(N), r=3):
    print p

#(0, 1, 2)
#(0, 1, 3)
#(0, 1, 4)
#(0, 2, 1)
#(0, 2, 3)
#(0, 2, 4)
#(0, 3, 1)
#...

But I'd like to have them enumerated in this order: lowest number firsts, i.e.:

#display 3-permutations of [0]
# (none)

#display 3-permutations of [0, 1] that haven't been displayed before
# (none)

#display 3-permutations of [0, 1, 2] that haven't been displayed before
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)

#display 3-permutations of [0, 1, 2, 3] that haven't been displayed before
(0, 1, 3)
(0, 2, 3)
(0, 3, 1)
(0, 3, 2)
...

#display remaining 3-permutations of [0, 1, 2, 3, 4] that haven't been displayed before
...

Is there a way to quickly enumerate 3-permutations of [0, ..., N-1] with this order?

---

Note: In my use case, N > 2000, so it has to be fast (I'm using Cython as well for other computations to make it fast, but this is another topic).

Edit (thanks to @RoryDaulton): the order within each group does not matter and I only care about the grouping.

Answer 1

There is a one liner for @Rory Daulton 's solution:

from itertools import *
a=[0,1,2,3,4]
print '\n'.join(['\n'.join([str(list(permutations(t)))  for t in list(combinations(a[:i+1],3)) if t not in list(combinations(a[:i],3))]) for i in range(2,len(a))])

Output:

[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
[(0, 1, 3), (0, 3, 1), (1, 0, 3), (1, 3, 0), (3, 0, 1), (3, 1, 0)]
[(0, 2, 3), (0, 3, 2), (2, 0, 3), (2, 3, 0), (3, 0, 2), (3, 2, 0)]
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
[(0, 1, 4), (0, 4, 1), (1, 0, 4), (1, 4, 0), (4, 0, 1), (4, 1, 0)]
[(0, 2, 4), (0, 4, 2), (2, 0, 4), (2, 4, 0), (4, 0, 2), (4, 2, 0)]
[(0, 3, 4), (0, 4, 3), (3, 0, 4), (3, 4, 0), (4, 0, 3), (4, 3, 0)]
[(1, 2, 4), (1, 4, 2), (2, 1, 4), (2, 4, 1), (4, 1, 2), (4, 2, 1)]
[(1, 3, 4), (1, 4, 3), (3, 1, 4), (3, 4, 1), (4, 1, 3), (4, 3, 1)]
[(2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 2, 3), (4, 3, 2)]

Answer 2

Here is an algorithm that is pretty fast and uses almost no extra memory.

First, use itertools to enumerate the 3-permuations of [0, 1, 2].

Then, enumerate the 2-permutations of [0, 1, 2], and just before yielding each permutation insert a 3 at the end. Then enumerate those 2-permutations again and insert a 3 at the middle position. Then enumerate them again and insert a 3 at the beginning position.

Then enumerate the 2-permutations of [0, 1, 2, 3] and insert a 4 at the end. Then enumerate those 2-permutations again and insert a 4 at the middle position. Then...

You get the idea. You might save some time by saving the 2-permutations after the first generation so you can just insert the large value at the proper place.

NOTE: I proposed this algorithm to get the exact order of 3-permutations given in the example. If the order within a group can differ, other algorithms are possible and are faster than mine. My algorithm works just fine and gives the stated order completely, but it is slower than the algorithms with a different order.

Answer 3

An abstracted, generator function variant of @Uvar's post:

Code

import itertools as it


def unique_permute(iterable, r=3, verbose=False):
    seen = set()
    for i, _ in enumerate(iterable):
        part = iterable[:i+1]
        if verbose: print("# Display 3-permutations of {} that haven't been displayed before".format(part))
        for p in it.permutations(part, r=r):
            if p not in seen:
                yield p
            seen.add(p)

Demo

lst = [0, 1, 2, 3, 4]
for p in unique_permute(lst, verbose=True):
    print("", p)

Output

# Display 3-permutations of [0] that haven't been displayed before
# Display 3-permutations of [0, 1] that haven't been displayed before
# Display 3-permutations of [0, 1, 2] that haven't been displayed before
 (0, 1, 2)
 (0, 2, 1)
 (1, 0, 2)
 (1, 2, 0)
 (2, 0, 1)
 (2, 1, 0)
# Display 3-permutations of [0, 1, 2, 3] that haven't been displayed before
 (0, 1, 3)
 (0, 2, 3)
 (0, 3, 1)
 (0, 3, 2)
 ...

Answer 4

Your answer looks like the best approach, but you can make it a little more compact (and improve the ordering) by using permutations.

from itertools import permutations

num = 5
for i in range(2, num):
    for j in range(i):
        for k in range(j):
            for t in permutations((k, j, i)):
                print(t)

output

(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
(0, 1, 3)
(0, 3, 1)
(1, 0, 3)
(1, 3, 0)
(3, 0, 1)
(3, 1, 0)
(0, 2, 3)
(0, 3, 2)
(2, 0, 3)
(2, 3, 0)
(3, 0, 2)
(3, 2, 0)
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
(0, 1, 4)
(0, 4, 1)
(1, 0, 4)
(1, 4, 0)
(4, 0, 1)
(4, 1, 0)
(0, 2, 4)
(0, 4, 2)
(2, 0, 4)
(2, 4, 0)
(4, 0, 2)
(4, 2, 0)
(1, 2, 4)
(1, 4, 2)
(2, 1, 4)
(2, 4, 1)
(4, 1, 2)
(4, 2, 1)
(0, 3, 4)
(0, 4, 3)
(3, 0, 4)
(3, 4, 0)
(4, 0, 3)
(4, 3, 0)
(1, 3, 4)
(1, 4, 3)
(3, 1, 4)
(3, 4, 1)
(4, 1, 3)
(4, 3, 1)
(2, 3, 4)
(2, 4, 3)
(3, 2, 4)
(3, 4, 2)
(4, 2, 3)
(4, 3, 2)

---

Here's some code I came up with earlier. It's more compact, but it uses a lot of RAM when N is large.

from itertools import permutations

num = 5
a = [(i, 1<<i) for i in range(num)]
perms = sorted(permutations(a, 3), key=lambda t: sum(u[1] for u in t))
for t in perms:
    print(tuple(u[0] for u in t))

This produces the same output (in the same order) as the above code.

---

FWIW, here's an implementation of Rory Daulton' algorithm. Note that the output order is slightly different.

from itertools import permutations, combinations

num = 5
for i in range(2, num):
    for u, v in combinations(range(i), 2):
        for t in permutations((u, v, i)):
            print(t)

output

(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
(0, 1, 3)
(0, 3, 1)
(1, 0, 3)
(1, 3, 0)
(3, 0, 1)
(3, 1, 0)
(0, 2, 3)
(0, 3, 2)
(2, 0, 3)
(2, 3, 0)
(3, 0, 2)
(3, 2, 0)
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
(0, 1, 4)
(0, 4, 1)
(1, 0, 4)
(1, 4, 0)
(4, 0, 1)
(4, 1, 0)
(0, 2, 4)
(0, 4, 2)
(2, 0, 4)
(2, 4, 0)
(4, 0, 2)
(4, 2, 0)
(0, 3, 4)
(0, 4, 3)
(3, 0, 4)
(3, 4, 0)
(4, 0, 3)
(4, 3, 0)
(1, 2, 4)
(1, 4, 2)
(2, 1, 4)
(2, 4, 1)
(4, 1, 2)
(4, 2, 1)
(1, 3, 4)
(1, 4, 3)
(3, 1, 4)
(3, 4, 1)
(4, 1, 3)
(4, 3, 1)
(2, 3, 4)
(2, 4, 3)
(3, 2, 4)
(3, 4, 2)
(4, 2, 3)
(4, 3, 2)

Answer 5

I've finally found a solution, which seems to be optimal:

for i in range(N):            # i is the biggest
    print 'biggest = %i' % i
    for j in range(i):        # j is the second
        for k in range(j):    # k is the smallest
                print i, j, k
                print j, k, i
                print k, i, j
                print j, i, k
                print k, j, i
                print i, k, j

Here is the output

biggest = 0
biggest = 1
biggest = 2
2 1 0
1 0 2
0 2 1
1 2 0
0 1 2
2 0 1
biggest = 3
3 1 0
1 0 3
0 3 1
1 3 0
0 1 3
3 0 1
3 2 0
2 0 3
0 3 2
2 3 0
0 2 3
3 0 2
3 2 1
2 1 3
1 3 2
2 3 1
1 2 3
3 1 2
biggest = 4
4 1 0
1 0 4
0 4 1
1 4 0
0 1 4
4 0 1
4 2 0
2 0 4
0 4 2
2 4 0
0 2 4
4 0 2
4 2 1
2 1 4
1 4 2
2 4 1
1 2 4
4 1 2
4 3 0
3 0 4
0 4 3
3 4 0
0 3 4
4 0 3
4 3 1
3 1 4
1 4 3
3 4 1
1 3 4
4 1 3
4 3 2
3 2 4
2 4 3
3 4 2
2 3 4
4 2 3

Answer 6

The search for p in the set can probably be optimized, but one way to achieve the goal of displaying the permutations themselves it is by using sets:

import itertools
N = 5
spam = set()
for i in range(N):
    print('new permutation', list(range(i+1)))
    for p in itertools.permutations(range(i+1), r=3):
        if p not in spam:
            print(p)
            spam.add(p)