Enumerate All Possible Combinations In Labeled Balls And Labeled Bins Problem In Python

I'm looking for a Pythonic way of enumerating all possible options for the 'labeled balls into labeled bins' problem. For example, given 2 labeled balls and 2 labeled bins I would

Solution 1:

Counting the objects

These objects are also called k-partitions in many places.

We could count them at first, and then use the counting methods to test if we're generating the right amount of objects.

The Stirling numbers of the 2nd kind are counting the number of placements of n balls into bnon-empty bins.

We can extend that to the following formula to allow for empty bins

\sum_{e=0}^{b} {b\choose e} S(n,b-e) (b-e)!

In the sum above, e represents the number of empty bins, so we're allowing between 0 and b empty bins, the term binomial(b,e) will account for any position of the empty bins, while the remaining b-e non-empty bins are counted by S(n,b-e), but we still need to allow for all permutations of the non-empty bins which we're doing through (b-e)!.

We can count this using the following program:

#!/usr/bin/python3from sympy import *
from sympy.functions.combinatorial.numbers import stirling

## Counting the number of ways to place n balls into b boxes, allowing# for empty boxes.#defcount_k_partitions(n,b):
    ans = 0for e inrange(0,b+1):
        ans += binomial(b,e) * stirling(n,b-e,kind=2) * factorial(b-e)
    return ans

print("c(2,2):",count_k_partitions(2,2))
print("c(3,3):",count_k_partitions(3,3))
print("c(6,7):",count_k_partitions(6,7))

OUTPUT:

c(2,2): 4c(3,3): 27c(6,7): 117649

See also:

• This thread derives the same formula

• These two threads discuss the probability of having e empty bins after placing the balls link1 , link2

Generating the objects

Here is a recursive algorithm that generates the placements of balls into bins. Each ball is placed in one of the bins, then the algorithm recurses further into the remaining balls to place the next ball. When there are no more balls to place, we're printing the contents of all bins.

#!/usr/bin/python3import string
import copy
## This generates all the possible placements of# balls into boxes (configurations with empty boxes are allowed).#classBinPartitions:

    def__init__(self, balls, num_bins):
        self.balls = balls
        self.bins = [{} for x inrange(num_bins)]

    defprint_bins(self, bins):
        L = []
        for b in bins:
            buf = ''.join(sorted(b.keys()))
            L += [buf]
        print(",".join(L))

    def_gen_helper(self,balls,bins):
        iflen(balls) == 0:
            self.print_bins(bins)
        else:
            A,B = balls[0],balls[1:]
            for i inrange(len(bins)):
                new_bins = copy.deepcopy(bins)
                new_bins[i].update({A:1})
                self._gen_helper(B,new_bins)

    defget_all(self):
        self._gen_helper(self.balls,self.bins)

BinPartitions(string.ascii_uppercase[:3],3).get_all()
#BinPartitions(string.ascii_uppercase[:2],2).get_all()#BinPartitions(string.ascii_uppercase[:3],3).get_all()#BinPartitions(string.ascii_uppercase[:6],3).get_all()

OUTPUT:

ABC,,
AB,C,
AB,,C
AC,B,
A,BC,
A,B,C
AC,,BA,C,BA,,BC
BC,A,
B,AC,
B,A,C
C,AB,
,ABC,
,AB,C
C,A,B
,AC,B
,A,BC
BC,,AB,C,AB,,AC
C,B,A
,BC,A
,B,AC
C,,AB
,C,AB
,,ABC

Other algorithms for generating the objects

Partition-based algorithms: link1 ; link2

Knuth's Algorithm U: link1 ; link2 ; link3

All the code used in this post is also available here