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 q = 1 while q < len(seq) and seq > seq[q]: q += 1 # if cannot find q, then seq is the highest permutation if q == len(seq): return None # swap seq and seq[q] seq, seq[q] = seq[q], seq return seq else: return [seq] + 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.