Recursively choose K items from N , until empty

Question

An example illustrates it best

Starting with a list of N unique items = ['A','B','C','D','E']

Pick k=2 items

Here we have Python implementation to show the number of possible combinations:

combos = [c for c in combinations(['A','B','C','D','E'],2)]
combos = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'D'), ('C', 'E'), ('D', 'E')]

Now, for each of the 10 combinations, imagine taking that set away from the original list of N, and re-caculate the number of ways to choose the remaining N-k items.

Taking the first set ('A', 'B') leaves us with N items of ['C','D','E']

combos = [c for c in combinations(['C','D','E'],2)]
combos = [('C', 'D'), ('C', 'E'), ('D', 'E')]

Again, we repeat the above procedure for each of the 3 combinations, taking each in-turn away from the current list, eventually in this case leaving only one item in the list, which makes a simple final decision of taking it without the need of any combinatorial expansions.

So to recap we have, what I have been calling a SELECTION PATH of: First we picked ('A', 'B') Then we picked ('C', 'D'). Finally we picked ('E')

So the solution path is a list [('A', 'B'), ('C', 'D'), ('E')] and the recursion has hit the bottom, and terminates for this branch because there are no more items in the list.

The recursion picked back up at the top, had we picked ('A', 'C') the first time, instead, and proceeds to expand out the options, creating a new branch of selections paths.

The end result should be a list of all possible selection paths. This would be a list of lists of tuples, because a solution path itself is a list the picks.

Final Result should resemble:
[ 
[('A', 'B'), ('C', 'D'), ('E')], 
[('A', 'C'), ('B', 'D'), ('E')], 
[('A', 'D'), ('B', 'C'), ('E')], 
... 
[('D', 'E'), ('A', 'B'), ('C')], 
[('D', 'E'), ('A', 'C'), ('B')], 
... 
]

Obviously, this is just an example, I would like to scale it up and vary both N and K.

My first attempt at coding in python has not been very successfull. I can't seem to understand what my function should return each recursion and how to manage the lists between the levels of recursion. I'm really in need of help here.

def get_combo_path(prod_list, phase, k):
    from itertools import combinations
    from collections import defaultdict
    import copy
    prod_list=copy.deepcopy(prod_list) #Worried about pointers, not sure I need this
    phase=copy.deepcopy(phase) #Worried about pointers, not sure I need this

    prod_combos = [c for c in combinations(prod_list,k)]

    print('prod_list',prod_list)
    for x in prod_combos:
        phase.append(x) #Store which combo we are selecting
        prods_left = list(set(prod_list)-set(x)) #Subtract the set from the list
        print('x',x) #Troubleshooting
        print('phase',phase) #Troubleshooting
        print('prods_left',prods_left) #Troubleshooting
        get_combo_path(prods_left, phase, k) #Recursively call func for each combo
    
    print() #Troubleshooting
    return None #What should I return?
    
#Now to run the function
from collections import defaultdict
prod_list = [chr(ord('a')+p).upper() for p in range(0,5)] #Makes initial list of chars
new_groups = get_combo_path(prod_list, [], 2)

Answer 1

A slight modification to @kcsquared solution so that the order of the selection of the groups is taken into account.

The key thing here is that the groups themselves are combinations, and thus order doesnt matter within the groupings, but the order OF the groupings does matter. For example, in a scenario where I was randomly giving a combination of a main course and a side dish to a line of people, the order of the food on the plate doesn't matter but where you are in that line might determine if you got chicken or beef.

def partitions(s, r):
    s = set(s)
    assert (len(s) % r == 0)
    if len(s) == 0:
        yield ()
        return
    for c in itertools.combinations(s, r):
        first_subset = c
        for p in partitions(s.difference(c), r):
            yield (first_subset,) + p

def get_combo_path(prod_list, k):
    """Given distinct elements prod_list, give all partitions into
    bins of size k with possibly 1 remainder bin"""

    prod_set = set(prod_list)
    n = len(prod_set)
    remainder = n % k
    if remainder == 0:
        yield from partitions(prod_set, k)
        return

    for left_overs in itertools.combinations(prod_set, remainder):
        rest = prod_set.difference(left_overs)
        for p in partitions(rest, k):
            yield p + (left_overs,)

Result (compare this to the original answer to see if has many more rows)

(('E', 'B'), ('D', 'A'), ('C',))
(('E', 'D'), ('B', 'A'), ('C',))
(('E', 'A'), ('D', 'B'), ('C',))
(('B', 'D'), ('E', 'A'), ('C',))
(('B', 'A'), ('E', 'D'), ('C',))
(('D', 'A'), ('E', 'B'), ('C',))
(('C', 'E'), ('B', 'A'), ('D',))
(('C', 'B'), ('E', 'A'), ('D',))
(('C', 'A'), ('E', 'B'), ('D',))
(('E', 'B'), ('C', 'A'), ('D',))
(('E', 'A'), ('C', 'B'), ('D',))
(('B', 'A'), ('C', 'E'), ('D',))
(('C', 'B'), ('D', 'A'), ('E',))
(('C', 'D'), ('B', 'A'), ('E',))
(('C', 'A'), ('D', 'B'), ('E',))
(('B', 'D'), ('C', 'A'), ('E',))
(('B', 'A'), ('C', 'D'), ('E',))
(('D', 'A'), ('C', 'B'), ('E',))
(('C', 'E'), ('D', 'A'), ('B',))
(('C', 'D'), ('E', 'A'), ('B',))
(('C', 'A'), ('E', 'D'), ('B',))
(('E', 'D'), ('C', 'A'), ('B',))
(('E', 'A'), ('C', 'D'), ('B',))
(('D', 'A'), ('C', 'E'), ('B',))
(('C', 'E'), ('D', 'B'), ('A',))
(('C', 'B'), ('E', 'D'), ('A',))
(('C', 'D'), ('E', 'B'), ('A',))
(('E', 'B'), ('C', 'D'), ('A',))
(('E', 'D'), ('C', 'B'), ('A',))
(('B', 'D'), ('C', 'E'), ('A',))