Search code examples
pythonlistpermutationbins

Get all possible ways to put variable list of items into N bins


I have a list of items which can be any length (but will never contain duplicates of the same item), and a set of N bins which can each hold zero or one item. What's the easiest way to get all possible ways to put the items into the bins? I'm pretty sure I have a recursive solution that would work, but I want to know if there's a simpler option.

Ideally I only need permutations that fill as many bins as possible.

Examples for N = 3:

[A,B] -> [[A,B,_],[A,_,B],[B,A,_],[_,A,B],[B,_,A],[_,B,A]]

[A,B,C,D] -> [[A,B,C],[A,C,B],[B,A,C],[B,C,A],[C,A,B],[C,B,A],
              [A,B,D],[A,D,B],[B,A,D],[B,D,A],[D,A,B],[D,B,A],
              [A,D,C],[A,C,D],[D,A,C],[D,C,A],[C,A,D],[C,D,A],
              [D,B,C],[D,C,B],[B,D,C],[B,C,D],[C,D,B],[C,B,D]]

Solution

  • itertools.permutations() does what I'm looking for, I just need to pad the list with blanks if it has fewer than N values and specify N as the max permutation length. Thanks to John and Copperfield for pointing me in the right direction.

    import itertools
    
    def BinObjects(objects, binCount):
        objectsPadded = objects[:]  # Make a copy so we don't modify the original list
        if len(objects) < binCount:
            objectsPadded.extend(["_"] * (binCount - len(objects)))
        permutations = itertools.permutations(objectsPadded, binCount)
        print(list(permutations))
    
    BinObjects(["A", "B"], 3)
    BinObjects(["A", "B", "C", "D"], 3)
    
    
    Output:
    [('A', 'B', '_'), ('A', '_', 'B'), ('B', 'A', '_'), ('B', '_', 'A'), ('_', 'A', 'B'), ('_', 'B', 'A')]
    [('A', 'B', 'C'), ('A', 'B', 'D'), ('A', 'C', 'B'), ('A', 'C', 'D'), ('A', 'D', 'B'), ('A', 'D', 'C'),
     ('B', 'A', 'C'), ('B', 'A', 'D'), ('B', 'C', 'A'), ('B', 'C', 'D'), ('B', 'D', 'A'), ('B', 'D', 'C'),
     ('C', 'A', 'B'), ('C', 'A', 'D'), ('C', 'B', 'A'), ('C', 'B', 'D'), ('C', 'D', 'A'), ('C', 'D', 'B'),
     ('D', 'A', 'B'), ('D', 'A', 'C'), ('D', 'B', 'A'), ('D', 'B', 'C'), ('D', 'C', 'A'), ('D', 'C', 'B')]