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.