Hadron DaVinci

Partial Combinations

03 Oct 2020 - Hadron DaVinci

Most code challenges are based on combinatorics so having an understanding of the fundamentals is
essential. A partial combination is known as a C(n,k) problem which means we must select combinations
of size k out of n objects.

In this problem, we’ll calculate combinations of a given array.

Problem

Given array A, calculate the combinations when selecting k items.
A = [3, 6, 9, 12, 15], k = 3

Truths

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

1. Given array A, the subarray for each element at index i, is defined as: A[i+1:]
   • this means subarray is composed of all the elements in A that come after i
   • b/c of this truth, as i increases, the size of the subarray decreases
     • this helps avoid redundancy in results

2. If k = 1, combinations are formed by each element in array
3. The Spatial Complexity is: (n C k) * k
   • the number of combinations possible, (n C k), times the size of each combination, k

Method

Time Complexity: Exponential
Spatial Complexity: (n C k) * k

Method Summary
This method uses top-down recursion to calculate combinations given an array and k.
Specifically, for each element in array A, combinations are generated when that element is added to the combinations from all its subarrays, with k-1.

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

      If k is 1,
        function yields the current element as a tuple
        
      otherwise...
        function defines a subset of array, 
        calculates the combination for subset with k-1 items selected,
        forms a new tuple by using the result of calculation and the current element as a tuple,
        and yields the new tuple

Solution

def get_combinations(array, k):
  """
  :param array: an iterable
  :param k: number of items selected
  :yields: a tuple
  """

  array_length = len(array)

  for i in range(array_length):
    current_element_as_tuple = (array[i],)

    if k == 1:
      yield current_element_as_tuple
    else:
      next_index = i + 1
      k_with_one_less_degree_of_freedom = k - 1

      array_subset = array[next_index:]
      combination_generator_for_subset = get_combinations(array_subset, k_with_one_less_degree_of_freedom)

      for combination_subset in combination_generator_for_subset:
        yield current_element_as_tuple + combination_subset

# Try Code
a = [3, 6, 9, 12, 15]
for combination in get_combinations(a, 3):
  print(combination)

Result

(3, 6, 9)
(3, 6, 12)
(3, 6, 15)
(3, 9, 12)
(3, 9, 15)
(3, 12, 15)
(6, 9, 12)
(6, 9, 15)
(6, 12, 15)
(9, 12, 15)