CODEWITHSUNDEEP
phparraysalgorithmfunctionmath
cheersjosh
cheersjosh

Reputation: 1209

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

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.

Upvotes: 0

Views: 2004

Answers (2)

user797257
user797257

Reputation:

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.

Upvotes: 0

Paul
Paul

Reputation: 141827

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

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

Upvotes: 1

Related Questions