Python finding next word permutation with function generator

Question

Learning how to use function generators in Python I practiced with the following code that finds the next permutation of a word and then uses this new word as input for the next one until there are no further permutations. So for example 'dbac' is followed by 'dacb' followed by 'dabc' and so on.

Basically two questions: 1) the use of two times break to stop the two for-loops is there a better way to break out of the loops, and 2) the final part try: return finally: StopIteration is this a proper construction?

def nextperm(word):

    stoploop = True
    while stoploop:
        wordlist = [*word]
        length = len(wordlist)-1
        stoploop = False
        for index_1 in range(length-1, -1, -1):
            for index_2 in range(length, index_1-1, -1):
                if wordlist[index_2] < wordlist[index_1]:
                    wordlist[index_2], wordlist[index_1] = wordlist[index_1], wordlist[index_2]
                    _first = wordlist[0:index_1+1]
                    _second = wordlist[-1:index_1:-1]
                    wordlist = _first + _second
                    word = ''.join(wordlist)
                    stoploop = True
                    yield word
                    break
            if stoploop:
                break

    try:
        return print('no further permutation possible')
    finally:
        raise StopIteration

so if you do:

for i, word in enumerate(nextperm('dcba')):
    print(f'{i:2}, {word}')

output is:

 0, dcab
 1, dbca
 2, dbac
 3, dacb
 4, dabc
 5, cdba
 6, cdab
 7, cbda
 8, cbad
 9, cadb
10, cabd
11, bdca
12, bdac
13, bcda
14, bcad
15, badc
16, bacd
17, adcb
18, adbc
19, acdb
20, acbd
21, abdc
22, abcd
no further permutation possible

Answer 1

1. Review

1. The name nextperm is misleading as (i) it generates permutations that precede its argument; (ii) it generates multiple permutations, not just one. So a name like preceding_permutations would be clearer.

2. There is no need for try: ... finally: or raise StopIteration or return. If we try to get additional values from a generator that has finished, then Python automatically raises StopIteration. For example:

   >>> def generator():
   ...     yield 1
   >>> g = generator()
   >>> next(g)
   1
   >>> next(g)
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   StopIteration
   

3. It's not necessary to convert word to a list on each iteration of the while loop, because on subsequent iterations we already have this list in the variable wordlist.

4. All the permutations are the same length, so it is not necessary to reassign length on each loop.

5. This loop goes all the way down to index_1:

   for index_2 in range(length, index_1-1, -1):
   

   But when index_2 == index_1, the condition wordlist[index_2] < wordlist[index_1] can never be true. So this iteration is wasted. It would be better to write the second loop like this:

   for index_2 in range(length, index_1, -1):
   

6. Reversed ranges are quite tricky to reason about, and this kind of mistake is easy to make, so we should consider using reversed instead to make things simpler:

   for index_2 in reversed(range(index_1 + 1, length + 1)):
   

   (And similarly for index_1.)

7. When I read the name "length", I expect this to be the length of the word, not the length of the word minus one. So it would be easier to follow the logic if we had length = len(wordlist), and adjusted the ranges accordingly.

8. The code reverses the last part of wordlist, leaving the first part unchanged:

   _first = wordlist[0:index_1+1]
   _second = wordlist[-1:index_1:-1]
   wordlist = _first + _second
   

   It would make sense to implement this using a slice assignment:

   wordlist[index_1 + 1:] = reversed(wordlist[index_1 + 1:])
   

   This has several advantages: we avoid having to take the slice for the first part of the list, we reuse the memory in wordlist, and the use of reversed makes it clear what is happenig and reduces the risk of getting the slice indexes wrong.

9. The names index_1 and index_2 are used a lot: it would shorten the code and make it easier to read if we had names like i and j.

10. The stoploop logic can be removed if we introduce a local function that generates pairs of indexes:

    def indexes():
        for i in reversed(range(length - 1)):
            for j in reversed(range(i + 1, length)):
                yield i, j
    

    Now the two loops over the indexes can be combined into one:

    for i, j in indexes():
    

    and since we now have a single loop, we can break out of it using break, with no need for stoploop.

2. Revised code

def preceding_permutations(word):
    """Generate the permutations of word that precede it, in reverse
    lexicographical order.

    >>> ' '.join(preceding_permutations('bdca'))
    'bdac bcda bcad badc bacd adcb adbc acdb acbd abdc abcd'

    """
    word = list(word)
    length = len(word)
    def indexes():
        for i in reversed(range(length - 1)):
            for j in reversed(range(i + 1, length)):
                yield i, j
    while True:
        for i, j in indexes():
            if word[j] < word[i]:
                word[j], word[i] = word[i], word[j]
                word[i + 1:] = reversed(word[i + 1:])
                yield ''.join(word)
                break
        else:
            break