Brute Force Sorting: Permutation Enumeration

Check all permutations an input and see which one happens to be sorted

Ex) arr = [a, b, c]

[a, b, c] [a, c, b] [b, a, c] [b, c, a] [c, a, b] [c, b, a]

In particular, given an array with $N$ elements, there are $N!$ possible permutation to check.

Algorithm to enumerate all permutations would choose one out of $N$ elements for the first one, then it would choose one out of the remaining $N-1$ elements for the second one, and so and so forth. This would take

$N*(N-1)*(N-2)*...*1 = N!$

In [4]:
def swap(arr, i, j):
    temp = arr[j]
    arr[j] = arr[i]
    arr[i] = temp

def perm(arr, idx = 0):
    """
    Print out all N! permutations of the elements in an array
    
    Parameters
    ----------
    arr: list
        This is a list we're permuting in place
    idx: int
        What is the index of the element we are choosing in the array
    """
    if idx == len(arr)-1:
        print(arr)
    else:
        # Assume that everything before idx is fixed, but 
        # we want to take something that's after idx and swap
        # into idx and keep going
        for i in range(idx, len(arr)):
            swap(arr, i, idx) # Swap in arr[i] for arr[idx]
            perm(arr, idx+1) # Keep going recursively to figure out arr[idx+1]
            swap(arr, i, idx) # Swap back, and try something else

perm(['a', 'b', 'c', 'd'])
        

['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'c', 'b']
['a', 'd', 'b', 'c']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
['b', 'd', 'c', 'a']
['b', 'd', 'a', 'c']
['c', 'b', 'a', 'd']
['c', 'b', 'd', 'a']
['c', 'a', 'b', 'd']
['c', 'a', 'd', 'b']
['c', 'd', 'a', 'b']
['c', 'd', 'b', 'a']
['d', 'b', 'c', 'a']
['d', 'b', 'a', 'c']
['d', 'c', 'b', 'a']
['d', 'c', 'a', 'b']
['d', 'a', 'c', 'b']
['d', 'a', 'b', 'c']
In [ ]: