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(string):
    perms = sorted(set(permutations(string)))
    for perm in perms:
        print("".join(perm))

# Get user input
string = "abc"
permute(string)

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

Method 2: Using Next Permutation Algorithm

This method generates permutations using the next permutation algorithm.

from itertools import permutations

def next_permutation(string):
    perms = sorted(set("".join(p) for p in permutations(string)))
    for perm in perms:
        print(perm)

# Get user input
string = "abc"
next_permutation(string)

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

Method 3: Using Recursion with Sorting

This method generates and sorts permutations manually.

def permute_sorted(string, prefix=""):
    if len(string) == 0:
        print(prefix)
    else:
        for i in range(len(string)):
            permute_sorted(string[:i] + string[i+1:], prefix + string[i])

# Get user input
string = "abc"
permute_sorted("".join(sorted(string)))

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