Reorder elements in array evenly

Question

Say i have:

$array = (1,1,1,1,2,2,2,2,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);

What I'm trying to achive is to reorder elements evenly in it.

PHP's function shuffle() don't fits here, because i want some distance between same digits. So 1's has to be somewhere in the beginning of array, in the middle and in the end too.

I google about Fisher-Yates_shuffle algorithm, but it seems to work exactly like shuffle().

Thanks in advance!

Either you *randomize* the array or you don't. There's no such thing as an "even shuffle". It's either random or it is subject to some algorithm, not both. Maybe you want to distribute the numbers evenly first, then break the array apart into sub arrays and shuffle those? — deceze, Nov 21 '12 at 16:07
do you want it shuffled at all, or do you want it methodically ordered with even distribution? — Billy Moon, Nov 21 '12 at 16:08
The concept of shuffling is to randomize the order of items. If you shuffle a deck of cards it may happen that two consequitive cards are actually still next to each other in the shuffled deck. It may even happen (once in a gazillion times) that after shuffling, all cards are exactly in order. So if you explicitly want to prevent that, you're not looking for a shuffle function but for some kind of balancing function. — GolezTrol, Nov 21 '12 at 16:08
It might help to clarify what you are after if you write two potential outputs you would be happy with. — Billy Moon, Nov 21 '12 at 16:10
`So 1's has to be somewhere in the beginning of array, in the middle and in the end too.` this is not shuffle in my opinion. — itachi, Nov 21 '12 at 16:11
Okay, this is that i want $array = (0,1,3,0,0,0,0,2,0,0,0,2,0,0,0,2,3,0,1,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,1,0,0,0,0,0,3,0,0,0,2,0,0,3,0,1); I agree it is not a result of shuffle, but i cant figure out how to achive this. — Stanislav, Nov 21 '12 at 16:13
And *why* do you want this? What is the logic behind this distribution? Or what is the *purpose* of distributing it like this? — deceze, Nov 21 '12 at 16:19
It is a schedule for displaying banners "by views percent". So 1,2,3- ids of banners (say, 5% views), 0 is no banner found (other 85%). My current algorithm is based on mt_rand [....] and works fine, but for all views per month. When some user reloads page 20 times, there is no guarantee he will see his banner (with 5% views). — Stanislav, Nov 21 '12 at 16:34
Then I would recommend [Weighted random numbers](http://stackoverflow.com/questions/1761626/weighted-random-numbers) — deceze, Nov 21 '12 at 17:00
@deceze That is a better implementation than using an array, but still has the same problem of having the chance that 5 'ones' are returned in a row. — GolezTrol, Nov 21 '12 at 17:14
@Golez That chance is always there, if you want it to be *random* at all. Randomness only ever pays off over a large enough sample. If the user only generates 4 page hits and there are 4 possible ads *with weighted distribution*, it simply does not work. The user either doesn't see all ads or he doesn't see them according to weight or they're not random. The distribution will only ever work across *all page views within a certain timeframe* with enough hits to even out the random distribution. Not for individual users. Can't have your cake and eat it too. — deceze, Nov 21 '12 at 17:22
Sure, but apart from eliminating (or shrinking) the array, nothing changes. The outcome will be the same (that is, just as random) as when you shuffle this array of numbers the OP has. So it just doesn't solve anything much. Actually, it's worse, because with the array, you know that '1' will show up exactly 4 times (because 1 is there 4 times) when you have the same number of views as elements in the array. With weighted random numbers, you may (theoretically) have a million views without hitting the '1' a single time. — GolezTrol, Nov 21 '12 at 17:50
@Golez Sure, but I believe that's a misconception on the OP's part. You cannot have it weighted, "evenly random" and non-repetitive on a tiny sample like a single session of a single user, all at the same time. Simply because you do not know how many pages the user will visit, so you cannot precalculate the order so he sees all banners according to their weight. Still, upvoted your answer, since it answers the question, even if maybe a little too literally. — deceze, Nov 21 '12 at 18:02

GolezTrol · Accepted Answer · 2012-11-21T19:07:27.810

I think this is close to what you ask: A constant, reasonably even distribution of the items in an array.

// The input array. 0s are regarded as blanks.
$array = array(1,1,1,1,2,2,2,2,3,3,3,3,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);

// Count the times each item occurs. PHP will probably have a function for that, but I don't know.
$counter = array();
foreach ($array as $item)
{
  // Zeros are infill. Don't process them now, only process the other numbers and
  // the zeros will occupy the remaining space.
  if ($item === 0)
    continue;

  if (!array_key_exists($item, $counter))
    $counter[$item] = 0;
  $counter[$item]++;
}

// Reverse sort by quantity. This results in the best distribution.
arsort($counter);

// Pre-fill a new array with zeros.
$resultCount = count($array);
$result = array_fill(0, $resultCount, 0);

// Distribute the items in the array, depending on the number of times they occur.
foreach ($counter as $item => $count)
{
  // Determine the division for this item, based on its count.
  $step = $resultCount / $count;

  // Add the item the right number of times.
  for ($i = 0; $i < $count; $i++)
  {
    // Start with the index closest to the preferred one (based on the calculated step).
    $index = 0;
    $startIndex = (int)($step * $i);
    // Count up until a right index is found.
    for ($index = $startIndex; $index < $resultCount; $index++)
    {
      if ($result[$index] === 0)
      {
        $result[$index] = $item;
        break;
      }
    }
    // If no proper index was found, count fown from the starting index.
    if ($index === $resultCount)
    {
      for ($index = $startIndex; $index >= 0; $index--)
      {
        if ($result[$index] === 0)
        {
          $result[$index] = $item;
          break;
        }
      }
    }

    // Still no proper index found, that shouldn't be possible. There's always room.
    if ($index === -1)
    {
      throw new Exception('This cannot not happen');
    }
  }
}

var_dump($result);

For array:

1,1,1,1,2,2,2,2,3,3,3,3,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

It returns:

3,2,1,0,3,0,0,0,3,0,2,1,3,0,0,0,3,0,0,0,0,3,2,1,0,3,0,0,0,3,0,2,1,3,0,0,0,3,0,0,0,0

For array:

1,1,1,1,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,0,0

It returns:

4,4,3,4,3,4,2,4,3,4,2,4,3,4,1,4,3,4,1,4,0,4,4,3,4,3,4,2,4,3,4,2,4,3,4,1,4,3,4,1,4,0

Which I think is a neat distribution. Thanks to datdo for the idea of sorting the intermediate array.

I'm pretty sure this is the easiest way to somewhat evenly distribute the elements. You might want to start with the least frequent elements and work your way up though. — datdo, Nov 21 '12 at 18:29
Good plan, only it turns out that starting with the most frequent elements works better. I've changed the code and added new example results. I've added `arsort` to the code to reverse sort the array of counters. I also changed `(int)$step * $i` to `(int)($step * $i)`, because the multiplication needs to be done on the multiplication result instead of step alone. — GolezTrol, Nov 21 '12 at 19:07
Great! I added mt_rand to get some randomness: $startIndex = (int)($step * $i) + mt_rand(0, 1); @GolezTrol Thanks for time u spent! — Stanislav, Nov 22 '12 at 07:31

Reorder elements in array evenly

1 Answers1