6

所以，

问题

众所周知，伪随机数。“伪”实际上意味着，尽管它们通常是随机的（即不可预测的），但它们的顺序仍然是相同的，其中使用了相同的生成器初始化值。例如，在 PHP 中有mt_srand()函数可以做到这一点。例子：

mt_srand(1);
var_dump(mt_rand(), mt_rand(), mt_rand());

- 不管多少次我们将启动我们的脚本：生成的三个数字的顺序总是相同的。

现在，我的问题是如何做同样的事情 - 但对于洗牌数组。即我想创建一个函数，它将接受输入数组来 shuffle 和seed。在相同的种子值内，洗牌必须有连续的相同顺序。即让我们调用该函数shuffleWithSeed()- 然后以下应该适用于每个脚本启动：

$input = ['foo', 'bar', 'baz'];
$test  = shuffleWithSeed($input, 1000);//1000 is just some constant value
var_dump($test); //let it be ['bar', 'foo', 'baz']
$test  = shuffleWithSeed($test, 1000); 
var_dump($test); //let it be ['baz', 'foo', 'bar']
$test  = shuffleWithSeed($test, 1000); 
var_dump($test); //let it be ['baz', 'bar', 'foo']
//...

- 即无论我们为数组洗牌多少次 - 我希望下一个脚本启动的排序顺序在一个seed值内总是相同的。

我的方法

我想到了这个算法：

  1. 通过传递初始化随机数生成器seed
  2. 生成N随机数，其中成员N数$input
  3. 对第 2 步中的数字进行排序
  4. 使相应的数字依赖于$input键。

我已经实现了这个：

function shuffleWithSeed(array $input, $seed=null)
{
   if(!isset($seed))
   {
      shuffle($input);
      return $input;
   }
   if(!is_int($seed))
   {
      throw new InvalidArgumentException('Invalid seed value');
   }
   mt_srand($seed);
   $random = [];
   foreach($input as $key=>$value)
   {
      $random[$key] = mt_rand();
   }
   asort($random);
   $random = array_combine(array_keys($random), array_values($input));
   ksort($random);
   return $random;
}

- 现在，还发现了Fisher-Yates算法 - 但不确定它是否可以使用伪随机数（即使用种子）

问题

正如你所看到的，我在我的函数中做了两种排序——首先是值，其次是键。

  • 这可以用一种来完成吗？还是根本没有排序？输入数组可能很大，所以我想避免这种情况。
  • 但是，可能是我的算法不好？如果是，还有哪些其他选项可以建议？
4

1 回答 1

11

这是我不久前为此目的实现的功能的复制和粘贴：

/**
 * Shuffles an array in a repeatable manner, if the same $seed is provided.
 * 
 * @param array &$items The array to be shuffled.
 * @param integer $seed The result of the shuffle will be the same for the same input ($items and $seed). If not given, uses the current time as seed.
 * @return void
 */
protected function seeded_shuffle(array &$items, $seed = false) {
    $items = array_values($items);
    mt_srand($seed ? $seed : time());
    for ($i = count($items) - 1; $i > 0; $i--) {
        $j = mt_rand(0, $i);
        list($items[$i], $items[$j]) = array($items[$j], $items[$i]);
    }
}

它使用种子随机数生成器实现了一个简单的Fisher-Yates 洗牌。

于 2013-10-29T12:34:13.683 回答