Permutations

A permutation algorithm is used to generate all possible orderings of a given set of elements.

P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n - r)!}

Number of Permutations

Number of permutations is equal to N!

Recursive Permutation Algorithm

def permute(nums):
    result = []

    # Base case: when there's only one possible permutation
    if len(nums) == 1:
        return [nums]

    # Recursively build the permutations
    for i in range(len(nums)):
        n = nums[i]
        remaining = nums[:i] + nums[i+1:]

        for p in permute(remaining):
            result.append([n] + p)

    return result

nums = [1, 2, 3]
print(permute(nums))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Backtracking Implementation

from typing import List

def permute(str: List[str], left: int, right: int) -> None:
    if left == right:
        print(''.join(str))  
        return

    for i in range(left, right + 1):
        str[left], str[i] = str[i], str[left]  # Swap characters
        permute(str, left + 1, right)    # Recursively permute the rest
        str[left], str[i] = str[i], str[left]  # Backtrack

lst = list("ABC")  # Convert the string to a list since strings are immutable in Python
permute(lst, 0, len(s) - 1)


Output:
ABC
ACB
BAC
BCA
CAB
CBA

Related Posts