CODEWITHSUNDEEP
algorithmrecursioncombinations
Erik Petersen
Erik Petersen

Reputation: 2357

Find all possibilities of bin and objects

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]

Upvotes: 2

Views: 100

Answers (2)

Dialecticus
Dialecticus

Reputation: 16769

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 0B to AA...AAB, 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 On is located.

Upvotes: 1

SSC
SSC

Reputation: 3008

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

Upvotes: 0

Related Questions