CODEWITHSUNDEEP
pythonlistpermutationbins
CWRules
CWRules

Reputation: 87

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]]

Upvotes: -4

Views: 74

Answers (1)

CWRules
CWRules

Reputation: 87

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')]

Upvotes: -1

Related Questions