List all permutations of a given string in dictionary order in Python

Understanding String Permutations

String permutations refer to all possible arrangements of characters in a given string. The dictionary order means sorting them lexicographically.

We will explore three different methods to list all permutations of a given string in Python.

Method 1: Using Recursion

This method generates permutations recursively by swapping characters.

from itertools import permutations

def permute(s, answer):
    if len(s) == 0:
        print(answer)
        return
    for i in range(len(s)):
        ch = s[i]
        rest = s[:i] + s[i+1:]
        permute(rest, answer + ch)

s = "abc"
permute(s, "")

Input: abc
Output: abc, acb, bac, bca, cab, cba

Method 2: Using itertools.permutations

This method uses Python's built-in permutations function.

from itertools import permutations

s = "abc"
perm_list = sorted("".join(p) for p in permutations(s))
for perm in perm_list:
    print(perm)

Input: abc
Output: abc, acb, bac, bca, cab, cba

Method 3: Using Recursion with Sorting

This method generates and sorts permutations manually.

def generate_permutations(prefix, s, permutations):
    if not s:
        permutations.append(prefix)
    else:
        for i in range(len(s)):
            generate_permutations(prefix + s[i], s[:i] + s[i+1:], permutations)

s = "abc"
permutations = []
generate_permutations("", s, permutations)
permutations.sort()
for perm in permutations:
    print(perm)

Input: abc
Output: abc, acb, bac, bca, cab, cba