Doing Full Permutations by Hand

10 Oct 2020 - Hadron DaVinci

We will do full permutations by hand with the bottom up approach.
Note, the difference between a full permutation and partial permutation is that in a full permutation,
the number of items selected equals the number of items in the original set. The insights from this can be used to create code which does this automatically.

Problem

Given array A, calculate the full permutations.
A = [3, 6, 9]

Key Terms:

i = index
fe = first element in the original array, A[0]
sa = subset array, everything but the first element, A[1:]
sp = sub permutations, all the permutations of subset array, Permutation(sa)

Problem When A = [3]

    A = [3]
    fe = 3

    Rationale:
        if length of A is 1, just return A

    # Permutations Generated:
    (3)

Problem When A = [6]

    A = [6]
    fe = 6

    Rationale:
        if length of A is 1, just return A

    # Permutations Generated:
    (6)

Problem When A = [3, 6]

    A = [3, 6]
    fe = 3
    sa = [6]
    
    (1) sp = (6)
    (2) For each sp:
            For each index in A, insert fe into ith position of sp
                when sp = (6)
                    when i = 0
                    this yields: (3, 6)
            
                    when i = 1
                    this yields: (6, 3)

    # Permutations Generated:
    (3, 6), (6, 3)

Problem When A = [6, 9]

    A = [6, 9]
    fe = 6
    sa = [9]
    
    (1) sp = (9)
    (2) For each sp:
            For each index in A, insert fe into ith position of sp
                when sp = (9)
                    when i = 0
                    this yields: (6, 9)
            
                    when i = 1
                    this yields: (9, 6)

    # Permutations Generated:
    (6, 9), (9, 6)

Problem When A = [3, 6, 9]

    A = [3, 6, 9]
    fe = 3
    sa = [6, 9]
    
    (1) sp = (6, 9), (9, 6)
    (2) For each sp:
            For each index in A, insert fe into ith position of sp
                when sp = (6, 9)
                    when i = 0
                    this yields: (3, 6, 9)

                    when i = 1
                    this yields: (6, 3, 9)

                    when i = 2
                    this yields: (6, 9, 3)

                when sp = (9, 6)
                    when i = 0
                    this yields: (3, 9, 6)

                    when i = 1
                    this yields: (9, 3, 6)

                    when i = 2
                    this yields: (9, 6, 3)

    # Permutations Generated:
    (3, 6, 9), (6, 3, 9), (6, 9, 3)
    (3, 9, 6), (9, 3, 6), (9, 6, 3)  

Result

(3, 6, 9)
(6, 3, 9)
(6, 9, 3)
(3, 9, 6)
(9, 3, 6)
(9, 6, 3)   