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)

CodePudding user response：

Given a way to create all partitions of a set into equal-size bins with no 'left-over'/smaller bins, you can easily write a function to get all partitions with a left-over, by iterating first over all combinations of the 'left-over' size and appending those to each partition of the other elements.

Using the set partitions function from Gareth Rees' answer here, you can do this:

def partitions(s, r):
    s = set(s)
    assert (len(s) % r == 0)
    if len(s) == 0:
        yield ()
        return
    first = next(iter(s))
    rest = s.difference((first,))
    for c in itertools.combinations(rest, r - 1):
        first_subset = (first,)   c
        for p in partitions(rest.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,)

for combo in get_combo_path(['A','B','C','D','E'], 2):
    print(combo)

which gives:

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

Note that this requires distinct elements. If you want to allow duplicates, you'd do the same thing, but pass range(len(prod_list)) instead of prod_list, and use the resulting partitions as holding the indices of the corresponding elements from prod_list.