8
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – BurnsBA Sep 22 '17 at 15:49
12
\$\begingroup\$

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]

\$\endgroup\$
  • \$\begingroup\$ 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:]. \$\endgroup\$ – user2357112 Sep 22 '17 at 16:50
8
\$\begingroup\$

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)
\$\endgroup\$
  • 6
    \$\begingroup\$ That's not the point if you implement an algorithm for yourself just as an exercise. I am aware of the libs. \$\endgroup\$ – Nils Sep 22 '17 at 8:43
  • 12
    \$\begingroup\$ @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. \$\endgroup\$ – Peilonrayz Sep 22 '17 at 10:02
  • \$\begingroup\$ Would it be appropriate to delete this answer? \$\endgroup\$ – Daniel Sep 22 '17 at 10:08
  • 3
    \$\begingroup\$ @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.) \$\endgroup\$ – Peilonrayz Sep 22 '17 at 10:09
  • \$\begingroup\$ 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. \$\endgroup\$ – user2357112 Sep 22 '17 at 16:52
7
\$\begingroup\$

A miscellaneous improvement:

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

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.)

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.