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

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.

• Why the downvote :( Is anything wrong with the question? Commented May 27, 2019 at 16:16
• 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. Commented May 27, 2019 at 16:25
• I've edited the tags, performance doesn't look like an aim, since your code doesn't look to care too much about it. Commented May 27, 2019 at 16:28
• 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.
– Mast
Commented May 27, 2019 at 18:03

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']

• Title says he's supposed to use recursion though. Commented May 27, 2019 at 16:01
• @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. Commented May 27, 2019 at 16:14
• @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. Commented May 27, 2019 at 16:17

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.

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.