Python program to print all permutations of a string in lexicographic order using recursion

Question

An assignment at school required me to print all permutations of a string in lexicographic or dictionary order.

Here is my solution to the task -

from math import factorial
def print_permutations_lexicographic_order(s):
 seq = list(s)
 for _ in range(factorial(len(seq))):
 print(''.join(seq))
 nxt = get_next_permutation(seq)
 # if seq is the highest permutation
 if nxt is None:
 # then reverse it
 seq.reverse()
 else:
 seq = nxt
def get_next_permutation(seq):
 """
 Return next greater lexicographic permutation. Return None if cannot.
 This will return the next greater permutation of seq in lexicographic order. If seq is the highest permutation then this will return None.
 seq is a list.
 """
 if len(seq) == 0:
 return None
 nxt = get_next_permutation(seq[1:])
 # if seq[1:] is the highest permutation
 if nxt is None:
 # reverse seq[1:], so that seq[1:] now is in ascending order
 seq[1:] = reversed(seq[1:])
 # find q such that seq[q] is the smallest element in seq[1:] such that
 # seq[q] > seq[0]
 q = 1
 while q < len(seq) and seq[0] > seq[q]:
 q += 1
 # if cannot find q, then seq is the highest permutation
 if q == len(seq):
 return None
 # swap seq[0] and seq[q]
 seq[0], seq[q] = seq[q], seq[0]
 return seq
 else:
 return [seq[0]] + nxt
s = input('Enter the string: ')
print_permutations_lexicographic_order(s))

Here are some example inputs/outputs:

Enter the string: cow
>>> cow
 cwo
 ocw
 owc
 wco
 woc
Enter the string: dogs
>>> dogs
 dosg
 dsgo
 dsog
 gdos
 gdso
 gods
 gosd
 gsdo
 gsod
 odgs
 odsg
 ogds
 ogsd
 osdg
 osgd
 sdgo
 sdog
 sgdo
 sgod
 sodg
 sogd
 ogds
 ogsd

So, I would like to know whether I could make my program shorter and more efficient.

Any help would be highly appreciated.

• Justin: Why the downvote :( Is anything wrong with the question?
• Sedsarq: I didn't downvote, but I notice that the 2nd example is wrong. "dgos" and "dgso" are missing while "ogds" and "ogsd" occur twice. Also the tag "dictionary" refers to the data structure, not dictionary order.
• Peilonrayz: I've edited the tags, performance doesn't look like an aim, since your code doesn't look to care too much about it.
• Mast: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers . The moment answers arrive, you stop touching the code. That's the rules. It gets awfully messy otherwise.

Answer 1

And in the third time I will recommend you the itertools module:

As I told in another answers, your code is very C/C++ styled, it is not Pythonic. Try to avoid manual iteration with indices as much as possible. Python has an enormous standard library that contains many useful modules. I already recommended you an itertools module. It contains pair of dozens generic functions to work with iterators. One of them - permutations - do 90% of your work:

And in the second time I will recommend you the itertools.permutations function that can solve your problem with literally one line of code:

from itertools import permutations
def get_lexicographic_permutations(s):
 return sorted(''.join(chars) for chars in permutations(s))
print(get_lexicographic_permutations('dogs'))

['dgos', 'dgso', 'dogs', 'dosg', 'dsgo', 'dsog', 'gdos', 'gdso', 'gods', 'gosd', 'gsdo', 'gsod', 'odgs', 'odsg', 'ogds', 'ogsd', 'osdg', 'osgd', 'sdgo', 'sdog', 'sgdo', 'sgod', 'sodg', 'sogd']

• Sedsarq: Title says he's supposed to use recursion though.
• Peilonrayz: @Sedsarq The question isn't tagged with reinventing-the-wheel, and doesn't state they have to use recursion. It is also tagged performance, and this is almost definitely more performant.
• Sedsarq: @Peilonrayz That's a fair point. I read the title to mean that the program should involve recursion, but it could just as well mean simply that his version does.

Answer 2

A basic recursive idea is to repeatedly reduce the problem to a simpler version of the same kind, until it reaches a base case which can no longer be reduced. Recursive solutions are often "simple" in the sense of not using many lines of code, so that's something to look for.

Let's see how this can be applied to this particular problem. Take the word "cow", with the permutations

cow, cwo, ocw, owc, wco, woc

Notice how the first character stays the same, until all permutations of the "tail" has been covered. That's the reduction step you need: For each character in the string, make that the first character, and then call the function again with the rest of the characters. Keep track of the character selection order as that will be the word. Then remember to catch the base case: If there's no characters left in the string, we're done removing characters and the word is complete.

def lexperm(s, word=''):
 if not s:
 print(word)
 for i, char in enumerate(s):
 lexperm(s[:i] + s[i+1:], word + char)

Notice how this doesn't require swapping or reversing anything, because we're removing all characters, in every order.

Answer 3

I would recommend looking at itertools.permutations

from itertools import permutations
for p in permutations("cow"):
 joined = "".join(p)
 print(joined)

Output:

cow
cwo
ocw
owc
wco
woc

You can use it multiple ways:

1. Test your algorithm regarding output
2. Compare to your algorithm regarding speed
3. Check the implementation to get an idea how to it is done

Regarding 3, there is even an equivalent version (optimized but still readable) in the docs.