Algorithm - evenly distribute items across multiple arrays (if n items < n arrays)

Question

I am in need of an algorithm that distributes items across multiple arrays. I am coding in PHP if that helps anyone. The criteria is that I want to evenly skip arrays if the number of items is less than the number of arrays. To help you better understand what I am looking for, please review my example problem:

Example:

Consider having 50 lists. I have 20 items I want to distribute to these 50 lists. Some lists will miss out as there are only 20 items. What type of algorithm or what could I do to evenly distribute the items and avoid things like giving the first 20 lists the items and the last 30 lists get nothing?

Edit:

Okay, the objective is that some lists DO NOT receive items. So, only 20 lists would receive items.

Example: There are 8 lists but only 2 items. I want lists 3 and 6 to receive 1 item and then the process would be complete.

Thank you in advance.

Describe what you think should be "evenly distributed". If you have 50 lists and only 20 items, and each item cannot be divided, the result MUST be 30 empty lists, and 20 lists having 1 item each. — Sven
– Sven, Commented Jul 27, 2013 at 22:45
Having problems with your homework? This just requires some basic grade-school math to figure out how the items should be distributed, and a simple loop to put the items in the right arrays. What exactly do you not understand? — Sverri M. Olsen
– Sverri M. Olsen, Commented Jul 27, 2013 at 22:46
What Sven said. What does it mean that the "first" 20 lists get the items? If you want the result to "look random", put the 20 items in the first 20 lists and then shuffle the lists. Problem solved. — Jon
– Jon, Commented Jul 27, 2013 at 22:52

Paul · Accepted Answer · 2013-07-28 04:13:22Z

1

Put floor(#items/#lists) items in each list.

Then for the remaining items, put one in every floor(#lists/(#items % #lists)).

answered Jul 28, 2013 at 4:13

Paul

142k28 gold badges285 silver badges272 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

score 0 · Accepted Answer · 2013-07-28 15:38:11Z

0

Start with some random index in array, and then increment it by length of array + 1 modulo length of array:

function distribute_evenly(lists, items)
  last_index = random(length(lists))

  while length(items) > 0 do
    last_index <- mod(last_index + length(lists) + 1, length(lists))
    push(nth(lists, last_index), pop(items))

There could be other techniques of course, to ensure that the function returns the same result, rather than random one. For example, you could use, as the starting value, either the prime closest to the length of the lists, or the closest power of two or something like that.

edited Jul 28, 2013 at 15:38

answered Jul 28, 2013 at 13:38

user797257

Collectives™ on Stack Overflow

Algorithm - evenly distribute items across multiple arrays (if n items < n arrays)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related