Hadron DaVinci

Full Permutations

17 Oct 2020 - Hadron DaVinci

Most code challenges are based on combinatorics so having an understanding of the fundamentals is
essential. In this problem, we’ll calculate full permutations of a given array.

Problem

Given array A, calculate the full permutation.
Note, in a full permutation, all of the items are selected.
A = [3, 6, 9]

Truths

Using insights obtained from doing permutations by hand, we can generalize some truths:

1. Given array A, the subset array sa, is defined as: A[1:]
   • this means subarray is composed of all the elements in A that come after the first element
2. The Spatial Complexity is: (n P n) * n
   • the number of permutation possible, (n P n), times the size of each permutation, n

Methods

Method 1 Summary
Time Complexity: Factorial
Spatial Complexity: (n P n) * n

This method uses top-down recursion to calculate full permutations given an array.
Specifically,

1) obtain the first element, fe, and determine the subset array
2) determine the permutations of the subset array
3) for each subset permutation, loop through the indices of A and insert the fe into the ith index

Method 1 Pseudo Code
for each element in array, do the following:

      If length is 1,
        function yields the A as a tuple
        
      otherwise...
        function defines a subset of array, sa = A[1:]
        calculates the subset permutations for sa, sp = Permutations(A[1:])
        For each sp:
            For each index in A, insert fe into ith position of sp
            yield result as a new tuple       

Method 1 Solution

def permutation(a: list) -> tuple:
  """
  Finds permutation using recursion

  :param a: an iterable
  :yields: a tuple
  """
  length_a = len(a)
  first_element_as_tuple = (a[0],)

  if length_a <= 1:
    yield first_element_as_tuple
  else:
    subset_a = a[1:]

    for p in permutation(subset_a):
      for i in range(length_a):
        a_with_first_element_inserted_into_the_ith_position = p[:i] + first_element_as_tuple + p[i:]
        yield a_with_first_element_inserted_into_the_ith_position



# Try Code
A = [3, 6, 9]
for p in permutation(A):
  print(p)

Method 1 Result

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

Method 2 Summary

Time Complexity: Factorial
Spatial Complexity: n

This method does swapping and unswapping of indices along with recursion to calculate permutations.
One of the benefits of this method over Method 1 is that it doesn’t create a new subset object
each time which keeps the spatial complexity at n.

1) If current_index is the length of array, yield array (Base Case)
2) Else, Loop through all of the indices greater than or equal to current index and do the following:
    3) Swap current_index with other index
    4) Find permutation of array with current_index + 1, via recursion
    5) Unswap current_index with other index (Back Tracking)

Method 2 Pseudo Code
for each element in array, do the following:

      If ci == length,
        function yields the A as a tuple
        
      otherwise...
        For each i >= ci in A:
            swap elements at i and ci
            yield result from permution of A with ci+1
            unswap elements at i and ci

Method 2 Solution

def permutation(a: list, ci: int = 0) -> tuple:
  """
  Finds permutations using index swapping and recursion
  :param a: an iterable
  :param ci: current index of interest
  :yields: a tuple
  """
  if ci == len(a):
    yield tuple(a)
    
  else:
    for i in range(ci, len(a)):
      a[ci], a[i] = a[i], a[ci]
      yield from permutation(a, ci + 1)
      a[ci], a[i] = a[i], a[ci]


# Try Code
A = [3, 6, 9]
for p in permutation(A):
  print(p)

Method 2 Result

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