如何从数组中获取n个随机值并防止连续重复值

Question

我想填充一个结果数组，其中包含从输入数组中随机抽取的值，但结果数组不能有两个相同的连续值。

附加规则：

1. 输入值数组将仅包含唯一值，并且至少有两个值以确保可以填充所需的结果数组。
2. 随机值的数量可能大于或小于输入数组的大小。
3. 如果随机值的数量大于输入数组的大小，则结果数组不得要求使用输入中的所有值。 换句话说，随机选择的值不得有偏差，均匀分布。

输入示例：

$array = ['one', 'two', 'three', 'four'];
$n = 10;

可能有效结果的非详尽列表：

• ["three","one","three","one","two","one","four","one","three","four"]

• ["four","three","two","one","two","four","one","three","two","one"]

• ["two","four","three","one","two","one","four","two","three","one"]

我该怎么做？

---

_{这个问题的灵感来自于这个已删除的问题，它很难以明确的规则和期望提出问题。}

Answer 1

为了保证两个连续值不相同，请跟踪前一个值（或其键）并将其作为当前迭代的可能随机值删除。 将随机值推入结果数组，然后更新“前一个”变量。

array_diff_key()

可用于在调用

array_rand()

返回随机密钥之前排除特定密钥。

代码：（演示）（简化替代方案）（丑陋版本）

$lastIndex = -1;
$result = [];
for ($x = 0; $x < $n; ++$x) {
    $key = array_rand(array_diff_key($array, [$lastIndex => null]));
    $result[] = $array[$key];
    $lastIndex = $key;
}
echo json_encode($result);

---

或者，您可以使用

unset()

排除之前的随机值，但重要的是不要修改原始数组，否则可能没有足够的值来填充结果数组。 修改输入数组的副本即可。

代码：（演示）

$lastIndex = -1;
$result = [];
for ($x = 0; $x < $n; ++$x) {
    $copy = $array;
    unset($copy[$lastIndex]);
    $key = array_rand($copy);
    $result[] = $copy[$key];
    $lastIndex = $key;
}
echo json_encode($result);

---

暴力脚本可以猜测、检查和覆盖推送的连续重复值——这不会有有限数量的循环。使用较小的输入数组，连续重复的可能性会越来越大。

在循环中，无条件地将随机获取的值推入结果数组中，然后仅当结果数组有一个值或最后两个值不同时才有条件地增加计数器变量。 (演示)

$result = [];
for ($x = 0; $x < $n; $x += (int) (!$x || $result[$x] !== $result[$x - 1])) {
    $result[$x] = $array[array_rand($array)];
}
echo json_encode($result);

Answer 2

暴力方法

可以使用

while

循环来将输入

$array

的当前随机选择的元素与

$result

数组的最后一个元素进行比较（使用 PHP

end()

函数）。

此方法将导致对

array_rand()

的调用多于要返回的所需元素的数量，但是没有必要创建原始数组的副本。

但是，额外循环的数量将与

$array

的长度相关，因此当

$array

有：

• 4 个元素，我们预计大约有 33% 的额外循环
• 5 个元素，我们可以预期大约 25% 的额外循环
• 6 个元素，我们预计大约有 20% 的额外循环

当我们将

$n

的起始值增加到大约 1000 时，这一点清晰可见。

随着

$array

长度的增加，额外循环的预期百分比将趋于 0，尽管显然永远不会达到 0。

代码：演示

    $array = ['one', 'two', 'three', 'four', 'five'];
    // $array = ['one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten'];

    $n = 1000;
    $result = [];
    $loop_counter = 0;

    while($n > 0) {
        $key = array_rand($array);
        if(end($result) != $array[$key]) {
            $result[] = $array[$key];
            $n--;
        }
        $loop_counter++;
    }

    echo PHP_EOL . json_encode($result);
    echo PHP_EOL . $loop_counter;

有限循环数方法

有多种方法可以确保存在有限数量的循环，如此问题的另一个答案中给出的那样，但它们涉及为每个循环创建

$array

的副本，这可能是问题，也可能不是问题。

以下方法还创建

$array

的副本，但不是在每个循环上创建

$array

的新副本，此方法创建数组映射并查找数组是否已创建。

代码：演示

    $array = ['zero', 'one', 'two', 'three', 'four'];
    $n = 10;
    $result = [];
    $map_of_arrays = [];

    // We only select a random element once from the original array
    $key = array_rand($array);
    $result[] = $array[$key];
    $n--;

    while($n > 0) {
        if(!array_key_exists($key, $map_of_arrays)) {
            $map_of_arrays[$key] = $array;
            unset($map_of_arrays[$key][$key]);
        }
        $new_key = array_rand($map_of_arrays[$key]);
        $result[] = $map_of_arrays[$key][$new_key];
        $key = $new_key;
        $n--;
    }

    echo PHP_EOL . json_encode($result);

    // Check that the map of arrays has been created correctly
    // by comparing the index with the string representation
    echo PHP_EOL . PHP_EOL;
    var_dump($map_of_arrays);