Generating Permutations in Python

Question

To brush up my Python knowledge I an algorithm to generate permutations in lexicographic order. I ended up with the following code:

def swap(a, i, j): tmp = a[i] a[i] = a[j] a[j] = tmp def next_permutation(a): n = len(a) if n == 0 or n == 1: return False kFound = False for k in reversed(range(n - 1)): if a[k] < a[k + 1]: kFound = True break if not kFound: return False for l in reversed(range(n)): if a[k] < a[l]: break swap(a, k, l) return a[:k + 1] + [i for i in reversed(a[k + 1:])] 

I did a lot of C++ and miss std::swap(..), what is the proper way to do this in Python? In the last line, because reversed(..) returns an iterator I cannot write simply: a[:k + 1] + reversed(a[k + 1:]), is there a simpler way to trigger the unfolding of the iterator into a list?

Answer 1

Python has so many neat stuff to help you with this one, I feel alot can be rewritten:

I did a lot of C++ and miss std::swap(..)

Luckily you can swap really easy in python

For instance the swap method, can be rewritten like

def swap(a, i, j): a[i], a[j] = a[j], a[i] 

Is there a simpler way to trigger the unfolding of the iterator into a list?

Yes there is list slicing.

Just with list slicing only the reversed could be a[k + 1::-1] Where the last -1 is the step, and -1 means we step over it in reverse This returns a list and not a generator, thus your reverse could be return a[:k + 1] + a[k + 1::-1]

@user2357112, I feel like a rookie now.

I made a mistake, intuitively while fast typing I thought list reversing would be like this list[start:end:step] but instead it works differently, with exclusion.

[first i to include:first i to exclude:step], and becomes:

return a[:k + 1] + a[:k:-1]

Answer 2

Are you allowed to use standard library functions? If so, why not just use itertools.permutations():

>>> import itertools >>> next_permutation([1,2,3]) == next(itertools.permutations([1,2,3])) True 

You can also iterate over permutations:

>>> for permutation in itertools.permutations([1,2,3]): ... print(permutation) ... (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1) 

Answer 3

A miscellaneous improvement:

To make the pattern in your first for-loop cleaner, Python offers for–else:

for k in reversed(range(n - 1)): if a[k] < a[k + 1]: break else: return False 

The semantics are that the else-block is visited if the for-loop completes normally: i.e., if you don't break or return or raise from it. (Note that while and try support else-blocks in the same way.)

(Note: this removes your kFound variable. But if you were to include that variable, it should be called k_found. Variables in Python use camel_case.)

Answer 4

The part with the kfound variable is a standard pattern. You can completely avoid the use of this variable by using the for ... else syntax:

for k in reversed(range(n - 1)): if a[k] < a[k + 1]: break else: return False 

The else part is executed at the end of the for loop if the loop does not exit with a break statement.