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?

• BurnsBA: If I understand correctly this exercise was to practice python; I'm not sure how much you want to create an algorithm from scratch. If you are familiar with C++, I might recommend the lexicographic order permutations algorithm from the fxtbook (AKA "Matters Computational") as a reference.

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]

• user2357112: Your second point is wrong. a[k + 1::-1] doesn't do what you think it does; it starts from a[k+1] and goes back towards a[0], rather than reversing 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)

• Nils: That's not the point if you implement an algorithm for yourself just as an exercise. I am aware of the libs.
• Peilonrayz: @Nils It's best if you state that you know that there is a function that can already do this in your question. Heck we even have a tag for it, reinventing-the-wheel, so situations like this don't happen.
• Daniel: Would it be appropriate to delete this answer?
• Peilonrayz: @Coal_ IMO no, the OP changed the goal posts after posting the question, you shouldn't suffer due to that. (And your answer would have been the best, with the old goal posts.)
• user2357112: list(some_iter)[0] is an inefficient way to get the first element from an iterator; next(some_iter) is better, or next(iter(some_iterable)) if it's an arbitrary iterable rather than an iterator.

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.