Generating All Permutations of N Balls in M Bins

Generating all permutations of N balls in M bins

library(partitions)
compositions(3,4)

# [1,] 3 2 1 0 2 1 0 1 0 0 2 1 0 1 0 0 1 0 0 0
# [2,] 0 1 2 3 0 1 2 0 1 0 0 1 2 0 1 0 0 1 0 0
# [3,] 0 0 0 0 1 1 1 2 2 3 0 0 0 1 1 2 0 0 1 0
# [4,] 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 3

List of combinations of N balls in M boxes in C++

There's a neat trick to solving this. Imagine that we took the n balls and m − 1 boxes and put them in a row of length n + m − 1 (with the boxes mixed up among the balls). Then put each ball in the box to its right, and add an mth box at the right that gets any balls that are left over.

row containing a box, two balls, a box, one ball, a box, one ball, and an imaginary box

This yields an arangement of n balls in m boxes.

row of boxes containing zero, two, one, and one ball respectively

It is easy to see that there are the same number of arrangements of n balls in sequence with m − 1 boxes (the first picture) as there are arrangements of n balls in m boxes. (To go one way, put each ball in the box to its right; to go the other way, each box empties the balls into the positions to its left.) Each arrangement in the first picture is determined by the positions where we put the boxes. There are m − 1 boxes and n + m − 1 positions, so there are n + m − 1Cm − 1 ways to do that.

So you just need an ordinary combinations algorithm (see this question) to generate the possible positions for the boxes, and then take the differences between successive positions (less 1) to count the number of balls in each box.

In Python it would be very simple since there's a combinations algorithm in the standard library:

from itertools import combinations

def balls_in_boxes(n, m):
"""Generate combinations of n balls in m boxes.

>>> list(balls_in_boxes(4, 2))
[(0, 4), (1, 3), (2, 2), (3, 1), (4, 0)]
>>> list(balls_in_boxes(3, 3))
[(0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0), (3, 0, 0)]

"""
for c in combinations(range(n + m - 1), m - 1):
yield tuple(b - a - 1 for a, b in zip((-1,) + c, c + (n + m - 1,)))

permutations of N balls in M boxes in C++

This C++ code seems to have the same results as your python sample. It is far from the perfect one, still you could understand the algorithm and even use this implementation.

#include <deque>
typedef std::deque<size_t> BoxList;

class Generator {
size_t boxNum, ballNum, ownBox;
Generator* recursive;
public:
~Generator() { if ( recursive == NULL ) delete recursive; }
Generator( size_t boxes, size_t balls ) : boxNum(boxes), ballNum(balls) {
if ( boxes > 1 ) {
recursive = new Generator( boxes-1, balls );
ownBox = 0;
} else {
recursive = NULL;
ownBox = balls;
}
}
BoxList operator()() {
if ( ownBox > ballNum ) throw 1;
if ( boxNum <= 1 ) return BoxList( 1, ownBox++ );
try {
BoxList res = recursive->operator()();
res.push_front( ownBox );
return res;
}
catch(...) {
delete recursive;
ownBox++;
recursive = new Generator( boxNum-1, ballNum-ownBox );
return operator()();
}
}
};

Class interface allows you to use it as a standard generator. Operator () will generate exception when all possible options have been already iterated.

Generator g( boxes, balls );
try{
while( true )
g();
}
catch(...) {}

Enumerate all possible combinations in labeled balls and labeled bins problem in Python

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 b non-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)!

Sample Image

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/python3
from 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.
#

def count_k_partitions(n,b):
ans = 0
for e in range(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): 4
c(3,3): 27
c(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/python3
import string
import copy
#
# This generates all the possible placements of
# balls into boxes (configurations with empty boxes are allowed).
#
class BinPartitions:

def __init__(self, balls, num_bins):
self.balls = balls
self.bins = [{} for x in range(num_bins)]

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

def _gen_helper(self,balls,bins):
if len(balls) == 0:
self.print_bins(bins)
else:
A,B = balls[0],balls[1:]
for i in range(len(bins)):
new_bins = copy.deepcopy(bins)
new_bins[i].update({A:1})
self._gen_helper(B,new_bins)

def get_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,,B
A,C,B
A,,BC
BC,A,
B,AC,
B,A,C
C,AB,
,ABC,
,AB,C
C,A,B
,AC,B
,A,BC
BC,,A
B,C,A
B,,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

How to generate all combinations of assigning balls into bins including empty and full assignments?

for m balls to be put into n bins, there are n^m combinations. But as you accept putting no balls to m-1 balls, the answer to your question is summation of m^0 + mC1 * n^1 + mC2 * n^2 + .... mCm * n^m

eg. for 3 balls into 3 bins, the total number is 1 + 3*3 + 3*9 + 1*27 = 64

Python Solution.

import itertools
#let bins be 'ABC', but u can have your own assignment
bins = 'ABC'
balls = '123'
tmp = []
for no_ball_used in range(len(balls)+1):
bin_occupied = [''.join(list(i)) for i in itertools.product(bins,repeat=no_ball_used)]
ball_used = [''.join(list(i)) for i in itertools.combinations(balls,no_ball_used)]
solution = [i for i in itertools.product(ball_used,bin_occupied)]
tmp.append(solution)

tmp is the complete list, where first part is ball used, and second part is bin used.

print(tmp)
[[('', '')], [('1', 'A'), ('1', 'B'), ('1', 'C'), ('2', 'A'), ('2', 'B'), ('2', 'C'), ('3', 'A'), ('3', 'B'), ('3', 'C')], [('12', 'AA'), ('12', 'AB'), ('12', 'AC'), ('12', 'BA'), ('12', 'BB'), ('12', 'BC'), ('12', 'CA'), ('12', 'CB'), ('12', 'CC'), ('13', 'AA'), ('13', 'AB'), ('13', 'AC'), ('13', 'BA'), ('13', 'BB'), ('13', 'BC'), ('13', 'CA'), ('13', 'CB'), ('13', 'CC'), ('23', 'AA'), ('23', 'AB'), ('23', 'AC'), ('23', 'BA'), ('23', 'BB'), ('23', 'BC'), ('23', 'CA'), ('23', 'CB'), ('23', 'CC')], [('123', 'AAA'), ('123', 'AAB'), ('123', 'AAC'), ('123', 'ABA'), ('123', 'ABB'), ('123', 'ABC'), ('123', 'ACA'), ('123', 'ACB'), ('123', 'ACC'), ('123', 'BAA'), ('123', 'BAB'), ('123', 'BAC'), ('123', 'BBA'), ('123', 'BBB'), ('123', 'BBC'), ('123', 'BCA'), ('123', 'BCB'), ('123', 'BCC'), ('123', 'CAA'), ('123', 'CAB'), ('123', 'CAC'), ('123', 'CBA'), ('123', 'CBB'), ('123', 'CBC'), ('123', 'CCA'), ('123', 'CCB'), ('123', 'CCC')]]

tmp[0] = combination of 0 balls

tmp[1] = combination of 1 balls

tmp[2] = combination of 2 balls

tmp[3] = combination of 3 balls

You can unpack tmp with

[item for sublist in tmp for item in sublist]

Enumerate all possible distributions of n balls into k boxes

Very simple ... sort of.

function alloc(balls, boxes):

if boxes = 1
return [balls]
else
for n in range 0:balls
return alloc(balls-n, boxes-1)

That's the basic recursion logic: pick each possible quantity of balls, then recur on the remaining balls and one box fewer.

The list-gluing methods will be language-dependent; I leave them as an exercise for the student.

All possible ways to place colored balls into bins

Here's a "multi-combinations" implementation that doesn't require eliminating duplicate permutations. The first argument, n, is the list [Na, Nb, Nc, ...].

It is implemented as a recursive generator, so you can iterate through the combinations without having them all in memory at once. You say in a comment that Na + Nb + ... is typically around 20 but could be as high as 50 or 100. That means you almost certainly do not want to store all the combinations in memory. Consider an example with four "colors" where Na = Nb = Nc = Nd = 5. The number of combinations is choose(20, 5) * choose(15, 5) * choose(10, 5) = 11732745024, where choose(n, k) is the binomial coefficient. My computer has just 16 GB of RAM, so the storage required for that number of combinations would far exceed my computer's memory.

from itertools import combinations

def multicombinations(n, bins=None):
if bins is None:
bins = set(range(sum(n)))
if len(n) == 0:
yield []
else:
for c in combinations(bins, n[0]):
for t in multicombinations(n[1:], bins - set(c)):
yield [c] + t

It generates a list of tuples. That is, where your description of the first row is "First row is : R=(0,1) B=(2,3)", the first value generated by multicombinations([2, 2]) is [(0, 1), (2, 3)]. (This might not be the best format for the result, given the description of the weight calculation that you want to do next.)

Some examples:

In [74]: list(multicombinations([2, 2]))
Out[74]:
[[(0, 1), (2, 3)],
[(0, 2), (1, 3)],
[(0, 3), (1, 2)],
[(1, 2), (0, 3)],
[(1, 3), (0, 2)],
[(2, 3), (0, 1)]]

In [75]: list(multicombinations([3, 2]))
Out[75]:
[[(0, 1, 2), (3, 4)],
[(0, 1, 3), (2, 4)],
[(0, 1, 4), (2, 3)],
[(0, 2, 3), (1, 4)],
[(0, 2, 4), (1, 3)],
[(0, 3, 4), (1, 2)],
[(1, 2, 3), (0, 4)],
[(1, 2, 4), (0, 3)],
[(1, 3, 4), (0, 2)],
[(2, 3, 4), (0, 1)]]

In [76]: list(multicombinations([2, 3, 2]))
Out[76]:
[[(0, 1), (2, 3, 4), (5, 6)],
[(0, 1), (2, 3, 5), (4, 6)],
[(0, 1), (2, 3, 6), (4, 5)],
[(0, 1), (2, 4, 5), (3, 6)],
[(0, 1), (2, 4, 6), (3, 5)],
[(0, 1), (2, 5, 6), (3, 4)],
[(0, 1), (3, 4, 5), (2, 6)],
[(0, 1), (3, 4, 6), (2, 5)],
[(0, 1), (3, 5, 6), (2, 4)],
[(0, 1), (4, 5, 6), (2, 3)],
[(0, 2), (1, 3, 4), (5, 6)],
[(0, 2), (1, 3, 5), (4, 6)],
[(0, 2), (1, 3, 6), (4, 5)],
[(0, 2), (1, 4, 5), (3, 6)],
[(0, 2), (1, 4, 6), (3, 5)],
[(0, 2), (1, 5, 6), (3, 4)],
[(0, 2), (3, 4, 5), (1, 6)],
[(0, 2), (3, 4, 6), (1, 5)],
[(0, 2), (3, 5, 6), (1, 4)],
[(0, 2), (4, 5, 6), (1, 3)],
[(0, 3), (1, 2, 4), (5, 6)],
[(0, 3), (1, 2, 5), (4, 6)],
[(0, 3), (1, 2, 6), (4, 5)],
[(0, 3), (1, 4, 5), (2, 6)],
[(0, 3), (1, 4, 6), (2, 5)],
[(0, 3), (1, 5, 6), (2, 4)],
[(0, 3), (2, 4, 5), (1, 6)],
[(0, 3), (2, 4, 6), (1, 5)],
[(0, 3), (2, 5, 6), (1, 4)],
[(0, 3), (4, 5, 6), (1, 2)],
[(0, 4), (1, 2, 3), (5, 6)],
[(0, 4), (1, 2, 5), (3, 6)],
[(0, 4), (1, 2, 6), (3, 5)],
[(0, 4), (1, 3, 5), (2, 6)],
[(0, 4), (1, 3, 6), (2, 5)],
[(0, 4), (1, 5, 6), (2, 3)],
[(0, 4), (2, 3, 5), (1, 6)],
[(0, 4), (2, 3, 6), (1, 5)],
[(0, 4), (2, 5, 6), (1, 3)],
[(0, 4), (3, 5, 6), (1, 2)],
[(0, 5), (1, 2, 3), (4, 6)],
[(0, 5), (1, 2, 4), (3, 6)],
[(0, 5), (1, 2, 6), (3, 4)],
[(0, 5), (1, 3, 4), (2, 6)],
[(0, 5), (1, 3, 6), (2, 4)],
[(0, 5), (1, 4, 6), (2, 3)],
[(0, 5), (2, 3, 4), (1, 6)],
[(0, 5), (2, 3, 6), (1, 4)],
[(0, 5), (2, 4, 6), (1, 3)],
[(0, 5), (3, 4, 6), (1, 2)],
[(0, 6), (1, 2, 3), (4, 5)],
[(0, 6), (1, 2, 4), (3, 5)],
[(0, 6), (1, 2, 5), (3, 4)],
[(0, 6), (1, 3, 4), (2, 5)],
[(0, 6), (1, 3, 5), (2, 4)],
[(0, 6), (1, 4, 5), (2, 3)],
[(0, 6), (2, 3, 4), (1, 5)],
[(0, 6), (2, 3, 5), (1, 4)],
[(0, 6), (2, 4, 5), (1, 3)],
[(0, 6), (3, 4, 5), (1, 2)],
[(1, 2), (0, 3, 4), (5, 6)],
[(1, 2), (0, 3, 5), (4, 6)],
[(1, 2), (0, 3, 6), (4, 5)],
[(1, 2), (0, 4, 5), (3, 6)],
[(1, 2), (0, 4, 6), (3, 5)],
[(1, 2), (0, 5, 6), (3, 4)],
[(1, 2), (3, 4, 5), (0, 6)],
[(1, 2), (3, 4, 6), (0, 5)],
[(1, 2), (3, 5, 6), (0, 4)],
[(1, 2), (4, 5, 6), (0, 3)],
[(1, 3), (0, 2, 4), (5, 6)],
[(1, 3), (0, 2, 5), (4, 6)],
[(1, 3), (0, 2, 6), (4, 5)],
[(1, 3), (0, 4, 5), (2, 6)],
[(1, 3), (0, 4, 6), (2, 5)],
[(1, 3), (0, 5, 6), (2, 4)],
[(1, 3), (2, 4, 5), (0, 6)],
[(1, 3), (2, 4, 6), (0, 5)],
[(1, 3), (2, 5, 6), (0, 4)],
[(1, 3), (4, 5, 6), (0, 2)],
[(1, 4), (0, 2, 3), (5, 6)],
[(1, 4), (0, 2, 5), (3, 6)],
[(1, 4), (0, 2, 6), (3, 5)],
[(1, 4), (0, 3, 5), (2, 6)],
[(1, 4), (0, 3, 6), (2, 5)],
[(1, 4), (0, 5, 6), (2, 3)],
[(1, 4), (2, 3, 5), (0, 6)],
[(1, 4), (2, 3, 6), (0, 5)],
[(1, 4), (2, 5, 6), (0, 3)],
[(1, 4), (3, 5, 6), (0, 2)],
[(1, 5), (0, 2, 3), (4, 6)],
[(1, 5), (0, 2, 4), (3, 6)],
[(1, 5), (0, 2, 6), (3, 4)],
[(1, 5), (0, 3, 4), (2, 6)],
[(1, 5), (0, 3, 6), (2, 4)],
[(1, 5), (0, 4, 6), (2, 3)],
[(1, 5), (2, 3, 4), (0, 6)],
[(1, 5), (2, 3, 6), (0, 4)],
[(1, 5), (2, 4, 6), (0, 3)],
[(1, 5), (3, 4, 6), (0, 2)],
[(1, 6), (0, 2, 3), (4, 5)],
[(1, 6), (0, 2, 4), (3, 5)],
[(1, 6), (0, 2, 5), (3, 4)],
[(1, 6), (0, 3, 4), (2, 5)],
[(1, 6), (0, 3, 5), (2, 4)],
[(1, 6), (0, 4, 5), (2, 3)],
[(1, 6), (2, 3, 4), (0, 5)],
[(1, 6), (2, 3, 5), (0, 4)],
[(1, 6), (2, 4, 5), (0, 3)],
[(1, 6), (3, 4, 5), (0, 2)],
[(2, 3), (0, 1, 4), (5, 6)],
[(2, 3), (0, 1, 5), (4, 6)],
[(2, 3), (0, 1, 6), (4, 5)],
[(2, 3), (0, 4, 5), (1, 6)],
[(2, 3), (0, 4, 6), (1, 5)],
[(2, 3), (0, 5, 6), (1, 4)],
[(2, 3), (1, 4, 5), (0, 6)],
[(2, 3), (1, 4, 6), (0, 5)],
[(2, 3), (1, 5, 6), (0, 4)],
[(2, 3), (4, 5, 6), (0, 1)],
[(2, 4), (0, 1, 3), (5, 6)],
[(2, 4), (0, 1, 5), (3, 6)],
[(2, 4), (0, 1, 6), (3, 5)],
[(2, 4), (0, 3, 5), (1, 6)],
[(2, 4), (0, 3, 6), (1, 5)],
[(2, 4), (0, 5, 6), (1, 3)],
[(2, 4), (1, 3, 5), (0, 6)],
[(2, 4), (1, 3, 6), (0, 5)],
[(2, 4), (1, 5, 6), (0, 3)],
[(2, 4), (3, 5, 6), (0, 1)],
[(2, 5), (0, 1, 3), (4, 6)],
[(2, 5), (0, 1, 4), (3, 6)],
[(2, 5), (0, 1, 6), (3, 4)],
[(2, 5), (0, 3, 4), (1, 6)],
[(2, 5), (0, 3, 6), (1, 4)],
[(2, 5), (0, 4, 6), (1, 3)],
[(2, 5), (1, 3, 4), (0, 6)],
[(2, 5), (1, 3, 6), (0, 4)],
[(2, 5), (1, 4, 6), (0, 3)],
[(2, 5), (3, 4, 6), (0, 1)],
[(2, 6), (0, 1, 3), (4, 5)],
[(2, 6), (0, 1, 4), (3, 5)],
[(2, 6), (0, 1, 5), (3, 4)],
[(2, 6), (0, 3, 4), (1, 5)],
[(2, 6), (0, 3, 5), (1, 4)],
[(2, 6), (0, 4, 5), (1, 3)],
[(2, 6), (1, 3, 4), (0, 5)],
[(2, 6), (1, 3, 5), (0, 4)],
[(2, 6), (1, 4, 5), (0, 3)],
[(2, 6), (3, 4, 5), (0, 1)],
[(3, 4), (0, 1, 2), (5, 6)],
[(3, 4), (0, 1, 5), (2, 6)],
[(3, 4), (0, 1, 6), (2, 5)],
[(3, 4), (0, 2, 5), (1, 6)],
[(3, 4), (0, 2, 6), (1, 5)],
[(3, 4), (0, 5, 6), (1, 2)],
[(3, 4), (1, 2, 5), (0, 6)],
[(3, 4), (1, 2, 6), (0, 5)],
[(3, 4), (1, 5, 6), (0, 2)],
[(3, 4), (2, 5, 6), (0, 1)],
[(3, 5), (0, 1, 2), (4, 6)],
[(3, 5), (0, 1, 4), (2, 6)],
[(3, 5), (0, 1, 6), (2, 4)],
[(3, 5), (0, 2, 4), (1, 6)],
[(3, 5), (0, 2, 6), (1, 4)],
[(3, 5), (0, 4, 6), (1, 2)],
[(3, 5), (1, 2, 4), (0, 6)],
[(3, 5), (1, 2, 6), (0, 4)],
[(3, 5), (1, 4, 6), (0, 2)],
[(3, 5), (2, 4, 6), (0, 1)],
[(3, 6), (0, 1, 2), (4, 5)],
[(3, 6), (0, 1, 4), (2, 5)],
[(3, 6), (0, 1, 5), (2, 4)],
[(3, 6), (0, 2, 4), (1, 5)],
[(3, 6), (0, 2, 5), (1, 4)],
[(3, 6), (0, 4, 5), (1, 2)],
[(3, 6), (1, 2, 4), (0, 5)],
[(3, 6), (1, 2, 5), (0, 4)],
[(3, 6), (1, 4, 5), (0, 2)],
[(3, 6), (2, 4, 5), (0, 1)],
[(4, 5), (0, 1, 2), (3, 6)],
[(4, 5), (0, 1, 3), (2, 6)],
[(4, 5), (0, 1, 6), (2, 3)],
[(4, 5), (0, 2, 3), (1, 6)],
[(4, 5), (0, 2, 6), (1, 3)],
[(4, 5), (0, 3, 6), (1, 2)],
[(4, 5), (1, 2, 3), (0, 6)],
[(4, 5), (1, 2, 6), (0, 3)],
[(4, 5), (1, 3, 6), (0, 2)],
[(4, 5), (2, 3, 6), (0, 1)],
[(4, 6), (0, 1, 2), (3, 5)],
[(4, 6), (0, 1, 3), (2, 5)],
[(4, 6), (0, 1, 5), (2, 3)],
[(4, 6), (0, 2, 3), (1, 5)],
[(4, 6), (0, 2, 5), (1, 3)],
[(4, 6), (0, 3, 5), (1, 2)],
[(4, 6), (1, 2, 3), (0, 5)],
[(4, 6), (1, 2, 5), (0, 3)],
[(4, 6), (1, 3, 5), (0, 2)],
[(4, 6), (2, 3, 5), (0, 1)],
[(5, 6), (0, 1, 2), (3, 4)],
[(5, 6), (0, 1, 3), (2, 4)],
[(5, 6), (0, 1, 4), (2, 3)],
[(5, 6), (0, 2, 3), (1, 4)],
[(5, 6), (0, 2, 4), (1, 3)],
[(5, 6), (0, 3, 4), (1, 2)],
[(5, 6), (1, 2, 3), (0, 4)],
[(5, 6), (1, 2, 4), (0, 3)],
[(5, 6), (1, 3, 4), (0, 2)],
[(5, 6), (2, 3, 4), (0, 1)]]


Related Topics



Leave a reply



Submit