Doing Partial Combinations by Hand

02 Oct 2020 - Hadron DaVinci

We will do combinations by hand with the bottom up approach.
The insights from this can be used to create code which does this automatically.

Note, a partial combination is known as a C(n,k) problem which means we must select combinations
of size k out of n objects.

Problem

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

Key Terms:

i = index
ce = current element, A[i]
sa = subset array, everything excluding current element and all items before it, A[i+1:]
sc = sub combinations, all combinations of subset array with a certain k, C(sa, k)

Problem When k = 1

    k=1, array = [3, 6, 9, 12, 15]
    
    i = 0
    ce = 3
        k==1 so yield 3

    i = 1
    ce = 6
        k==1 so yield 6

    i = 2
    ce = 9
        k==1 so yield 9

    i = 3
    ce = 12
        k==1 so yield 12

    i = 4
    ce = 15
        k==1 so yield 15


    # Combinations Generated:
    (3), (6), (9), (12), (15)

Problem When k = 2

    k=2, array = [3, 6, 9, 12, 15]

    i = 0
    ce = 3
        k==1, sa = [6, 9, 12, 15]
        sub_combinations = (6), (9), (12), (15)

        for each sub_combination: yield ce + sub_combination
            this yields: (3,6), (3,9), (3,12), (3,15)

    i = 1
    ce = 6
        k==1, sa = [9, 12, 15]
        sub_combinations = (9), (12), (15)

        for each sub_combination: yield ce + sub_combination
            this yields: (6,9), (6,12), (6,15)


    i = 2
    ce = 9
        k==1, sa = [12, 15]
        sub_combinations = (12), (15)

        for each sub_combination: yield ce + sub_combination
            this yeilds: (9,12), (9,15)

    i = 3
    ce = 12
        k==1, sa = [15]
        sub_combinations = (15)

        for each sub_combination: yield ce + sub_combination
            this yields: (12,15)

    i = 4
    ce = 15
        k==1, sa = []
        sub_combinations = None

        for each sub_combination: yield ce + sub_combination
            since (15) has less elements than k,
            this yields no combination



    # Combinations Generated:
    (3,6), (3,9), (3,12), (3,15)
    (6,9), (6,12), (6,15)
    (9,12), (9,15)
    (12,15)

Problem When k = 3

    k=3, array = [3, 6, 9, 12, 15]
    i = 0
    ce = 3
        k==2, sa = [6, 9, 12, 15]
        sub_combinations = (6,9), (6,12), (6,15), (9,12), (9,15), (12,15)

        for each sub_combination: yield ce + sub_combination
            this yields: (3,6,9), (3,6,12), (3,6,15), (3,9,12), (3,9,15), (3,12,15)

    i = 1
    ce = 6
        k==2, sa = [9, 12, 15]
        sub_combinations = (9,12), (9,15), (12,15)

        for each sub_combination: yield ce + sub_combination
            this yields: (6,9,12), (6,9,15), (6,12,15)


    i = 2
    ce = 9
        k==2, sa = [12, 15]
        sub_combinations = (12,15)

        for each sub_combination: yield ce + sub_combination
            this yeilds: (9,12,15)

    i = 3
    ce = 12
        k==2, sa = [15]
        sub_combinations = []

        for each sub_combination: yield ce + sub_combination
            since (12, 15) has less elements than k,
            this yields no combination

    i = 4
    ce = 15
        k==2, sa = []
        sub_combinations = None

        for each sub_combination: yield ce + sub_combination
            since (15) has less elements than k,
            this yields no combination



    #Combinations Generated:
    (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)

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)    