Find all possibilities of bin and objects

Question

Given a finite set of bins and objects, where the bins are of infite size (there is no limit to the number of objects they can hold. What is an efficient algorithm to compute all the possibilities of objects in bins.

For example:

Lets say we have bins: B1, B2 and objects O1,O2 the solution would be:

B1 => [O1, O2] 
B2 => []

B1 => []
B2 => [O1, O2]

B1 => [O2]
B2 => [O1]

B1 => [O1]
B2 => [O2]

Algorithm that produces all possibilities is different from algorithm that computes them. — Dialecticus, Mar 06 '15 at 23:12
The words find, produce and compute all mean the same thing in this context — Erik Petersen, Mar 06 '15 at 23:15
The total combinations are the number of bins to the power of the number of objects, otherwise B^O. It's a simple, closed-form solution. — Vedaad Shakib, Mar 07 '15 at 00:16
I'm not looking for a number that is super easy as you stated, looking for the actual combinations — Erik Petersen, Mar 07 '15 at 00:23

Dialecticus · Accepted Answer · 2015-03-07T09:10:57.810

1

Let's say B is number of bins and O is number of objects. The algorithm should just count in base-B (as opposed to base-10 or base-2), counting from 0_B to AA...AA_B, where A = B - 1, and number of digits equals O.

The easiest way to count in base-B is to have an array of length O. In each step convert ...XAA..AA to ...Y00..00, where X < A and Y = X + 1, and part AA..AA could even have the length zero. Repeat as long as possible. Easiest way to convert the sub-array is to run inner a loop that runs from one end of array, incrementing items in modulo-B, and stopping after the first item that is not zero after the increment, or at the other end of the array.

Interpretation of the array contents in each step is that each of O digits tells us in which bin object O_n is located.

edited Mar 07 '15 at 09:10

answered Mar 06 '15 at 23:27

Dialecticus

16,400
7
43
103

I think you might have something but could you be more formal in your variable usage? I am having a hard time understanding. For example, you say "number of digits equals O" is O in this case the number of objects? – Erik Petersen Mar 07 '15 at 05:04
@ErikPetersen correct. I expanded the answer a bit. – Dialecticus Mar 07 '15 at 09:11

score 0 · Answer 2 · edited May 23 '17 at 12:28

As per my understanding a simple solution can be like:

Let's suppose, we have two bins (as per your mentioned solution):

B1 => [O1, O2] 
B2 => []

This means, B1 has 2 objects and B2 is empty so 1 because 2^0 = 1

Total = 3 and total number of possibilities = 2^3 = 8

Combine all bins, if you use add all (Not sure what's it's complexity but you can take a look at Collections.addAll [specifically java, there will be other algorithms with better complexity to merge two or multiple arrays]) and then you can find all combinations of N elements in O(n!) with the algorithm mentioned in here.

Best way to find all combinations

Computing the number of possibilities isn't the problem, I want the actual possiblities — Erik Petersen, Mar 06 '15 at 23:08

Find all possibilities of bin and objects

2 Answers2