1

说我有：

$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);

我想要实现的是在其中均匀地重新排序元素。

PHP 的函数 shuffle() 不适合这里，因为我想要相同数字之间的距离。所以 1 必须在数组的开头、中间和结尾。

我在谷歌上搜索了Fisher-Yates_shuffle算法，但它的工作原理似乎与 shuffle() 完全一样。

提前致谢！

4

1 回答 1

2

我认为这接近您所要求的：数组中项目的恒定、合理均匀分布。

// 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);

对于数组：

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

它返回：

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

对于数组：

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

它返回：

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

我认为这是一个整洁的分布。感谢 datdo 对中间数组进行排序的想法。

于 2012-11-21T17:45:54.677 回答