0

I have a number of items N and I want to uniformly distribute them among a number of C bins. My first though was to generate a random double number between 0 and 1 and then multiply it with the number N but it's not working as i expected. We are currently working on a Java project but a general algorithm would be fine.

Bins have no specific capacity and numbers don't have weights

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
Fotis
  • 97
  • 2
  • 13
  • Do all items have the same size/weight, i.e., there are no capacity restrictions on the bins? – Michiel uit het Broek May 25 '17 at 11:18
  • no there are no capacities on the bins and there are no weights i should have mentioned that will edit now! Thanks – Fotis May 25 '17 at 11:48
  • Are bins ordered (meaning putting only items 1,2,3 into bin 1 would be different from putting them in bin 5)? Can items divide unequally into bins, e.g. bins = 2, items = 1,2,3? Some example input and output always helps clarify the question. – Bernhard Barker May 25 '17 at 12:34
  • You should multiply the random number by C, not by N. Perhaps that was just a typo; in any case, you should clarify how your expectations were not met. (That will make it clearer what your expectations are.) – rici May 25 '17 at 14:46
  • Does this answer your question? [Uniformly selecting a distribution of items into bins](https://stackoverflow.com/questions/43566121/uniformly-selecting-a-distribution-of-items-into-bins) – Stef Jan 16 '23 at 16:41

2 Answers2

0

Given that all items and bins are identical we can use the following simple approach, which is definitely not the most efficient way to go but it is easy and works.

Create a vector containing the sequence 1 to N and use a function to randomly shuffle the values (e.g., Collections.shuffle(values)). Then the first N/C items are placed in the first bin, the following N/C items in the second one, etc..

Example, we have N=10 items and C=2 bins. We create the vector val = {1,2,3,4,5,6,7,8,9,10} and using a random shuffle function gives val = {4,8,2,1,9,10,5,3,6,7}. Then use this to get the following two bins bin1: {4,8,2,1,9} and bin2: {10,5,3,6,7}

Michiel uit het Broek
  • 983
  • 2
  • 7
  • 29
0

You have not specified what you mean by "uniformly distribute ".

There are M=CN variants of distribution of N items into C bins. So you can random integer in range 0..M-1 and represent it in C-ary numeral system to get random combination.

MBo
  • 77,366
  • 5
  • 53
  • 86
  • "Uniformly distribute" probably means having an equal number of items per bin (or with an item-count-in-bin difference of 1, if items % bins != 0). – Bernhard Barker May 25 '17 at 12:24
  • @Dukeling We could come up with many meanings of that term :) Hope that author will clarify his needs. – MBo May 25 '17 at 12:35
  • @Dukeling this is what i need to have a number lets say 100 and 10 bins and one bin could have 12 items, another 10 and so on... – Fotis May 25 '17 at 14:06
  • @Fotis Would 9 bins having 1 items each and one bin having 91 items be a valid possibility? Or 9 bins having 0 items with 1 bin having 100? – Bernhard Barker May 25 '17 at 14:07
  • @Dukeling i believe that in this case the items are not uniformly distributed. – Fotis May 25 '17 at 14:08
  • @Fotis If you randomly put any given item into any given bin with each bin being equally likely, it's possible (albeit very unlikely with many items and few bins) that some bins could end up with no items. If you don't want that, you'll need to be more specific about how you want the items to be distributed (12 is fine, but 100 is not, where's the cutoff?). If you say each bin must have the same number of items (+1 or -1, as required), this problem ends up being less of a problem (but you may still need to clarify where the +1's and -1's need to happen). – Bernhard Barker May 25 '17 at 14:14