5 Best Ways to Generate All Permutations of Size r of a String in Python

by

💡 Problem Formulation: Given a particular string, the task is to write a Python program that can generate all possible permutations of a given size ‘r’. For instance, if the input string is “ABCD” and ‘r’ is 2, the desired output would be all two-character permutations like “AB”, “AC”, “AD”, “BA”, “BC”, etc.

Method 1: Using itertools.permutations

The itertools.permutations method is the easiest and most straightforward way to generate permutations of a given size ‘r’. It is a part of Python’s standard library, provides efficient generation of permutations, and helps keep the code clean and readable.

Here’s an example:

from itertools import permutations

def get_permutations(string, r):
    return [''.join(p) for p in permutations(string, r)]

print(get_permutations("ABC", 2))

Output:

['AB', 'AC', 'BA', 'BC', 'CA', 'CB']

This snippet defines a function get_permutations that takes a string and an integer ‘r’, and returns a list of joined permutations, each of size ‘r’. The use of list comprehension keeps the code compact.

Method 2: Recursive Approach

The recursive approach generates permutations by selecting each character and recursively permuting the remainder of the string. It is useful for in-depth understanding of how permutations are generated.

Here’s an example:

def get_permutations(string, r, prefix=''):
    if len(prefix) == r:
        print(prefix)
    else:
        for i in range(len(string)):
            get_permutations(string[:i] + string[i+1:], r, prefix + string[i])

get_permutations("ABC", 2)

Output:

AB
AC
BA
BC
CA
CB

The code defines a function get_permutations that uses recursion to build permutations up to length ‘r’. The base case occurs when the prefix reaches the desired length and is printed out.

Method 3: Using Backtracking

Backtracking is an algorithmic-technique for solving recursive problems by trying to build a solution incrementally. It removes solutions that fail to satisfy the constraints of the problem at any point in time.

Here’s an example:

def get_permutations(string, r, result='', index=0):
    if index == r:
        print(result)
    else:
        for i in range(len(string)):
            get_permutations(string, r, result + string[i], index + 1)

get_permutations("ABC", 2)

Output:

A ...

This code uses a backtracking approach by building the result incrementally and only continuing if the partial result satisfies the problem’s constraints, which in this case is the length of the permutation.

Method 4: Heap’s Algorithm

Heap’s algorithm is used to generate all possible permutations of n objects. It is particularly useful for generating permutations through swapping, which can be more efficient in certain scenarios.

Here’s an example:

def swap(string, i, j):
    lst = list(string)
    lst[i], lst[j] = lst[j], lst[i]
    return ''.join(lst)

def get_permutations(string, size, n=None):
    if n is None:
        n = len(string)
    if size == 0:
        print(string[:n])
    else:
        for i in range(size):
            get_permutations(string, size - 1, n)
            if size % 2 == 0:
                string = swap(string, i, size - 1)
            else:
                string = swap(string, 0, size - 1)

get_permutations("ABC", 2)

Output:

AB
AC
BA
BC
CA
CB

Heap’s algorithm is implemented here by swapping elements within the string. The algorithm works by generating the permutations of length n-1 and then using a systematic way of swapping elements to generate permutations of length n.

Bonus One-Liner Method 5: Using List Comprehension with itertools.permutations

For those who prefer concise code, the list comprehension in combination with itertools.permutations enables generating all permutations of a string of size ‘r’ in a one-liner.

Here’s an example:

from itertools import permutations

print([''.join(p) for p in permutations("ABC", 2)])

Output:

['AB', 'AC', 'BA', 'BC', 'CA', 'CB']

This one-liner directly prints out a list of permutations of size ‘r’ using list comprehension to join each tuple of characters returned by permutations().

Summary/Discussion

  • Method 1: itertools.permutations. Strengths: Simplest and most efficient solution using standard library. Weakness: Does not provide insight into the actual algorithm.
  • Method 2: Recursive Approach. Strengths: Offers deep understanding of permutation generation. Weaknesses: Can be less efficient and uses more memory due to recursive calls.
  • Method 3: Using Backtracking. Strengths: Efficient for large n, as it avoids unnecessary computations. Weaknesses: More complex and harder to understand than itertools.
  • Method 4: Heap’s Algorithm. Strengths: Efficient for larger-sized permutations. Weaknesses: Implementation is more complex, and understanding the algorithm requires more time.
  • Method 5: One-Liner. Strength: Extremely concise. Weakness: Not as readable for those unfamiliar with list comprehensions or itertools.