php - 当要投票的项目集增加时，公平、随机的投票匹配算法

Question

我正在创建一个程序，用户可以在从一组项目中选择的两个项目之间进行一系列投票。每次投票后，会显示集合中的两个新项目并对其进行投票，直到看到集合中的所有成员。

这是我的限制条件:

1. 每个用户应该以不同的随机顺序看到他们的项目
2. 如有必要，可以多次显示相同的项目，但我会喜欢将其保持在绝对最低限度
3. 用户可以在多个“ session ”中投票，即我需要保存他们的位置并允许他们重新开始投票
4. 在用户的投票 session 之间可能已将更多项目添加到集合中

选择的语言是 PHP，但我对以任何语言给出的算法感到满意，甚至只是伪代码。

显然，如果只有约束 1-3 到位，这将非常简单。我现在已经有了工作代码。我想不通的是如何处理约束 4 并仍然保持 1 和 2。我创建投票匹配数组的代码如下所示:

function matchedArray($count /* # items in set*/, $seed /* rand seed for this user*/)
{
    // Make array of 1 to $count
    $input = range(1, $count);

    // Randomize the array in a repeatable way,
    // so we can save their place and come back to it later
    srand($seed);
    shuffle($input);

    // Split the array into 2 equal-size arrays
    $firsthalf = array_slice($input, 0, ceil($count / 2));
    $secondhalf = array_slice($input, ceil($count / 2));

    // If array size was odd, repeat a value in the second array
    // so that we end up with equal-sized arrays
    if ($count & 1)
    $secondhalf[] = $secondhalf[rand(0, sizeof($secondhalf) - 1)];

    // Build a two-column array using the 2 split arrays
    for($i = 0; $i < sizeof($firsthalf); ++$i)
    {
        $output[] = array($firsthalf[$i], $secondhalf[$i]);
    }

    return $output;
}

如果集合有九个项目，例如，投票数组将如下所示:

Array
(
    [0] => Array
        (
            [0] => 5
            [1] => 7
        )

    [1] => Array
        (
            [0] => 2
            [1] => 3
        )

    [2] => Array
        (
            [0] => 8
            [1] => 4
        )

    [3] => Array
        (
            [0] => 6
            [1] => 1
        )

    [4] => Array
        (
            [0] => 9
            [1] => 3
        )

)

因此，该用户的第一次投票将在项目 5 和 7 之间，第二次投票在项目 2 和 3 之间，依此类推。简单易行，直到您尝试在投票开始后将更多项目添加到组合中。

有没有什么方法可以在不失去他们的位置的情况下并且让他们对他们已经看过的一堆东西进行投票并且同时保持随机性？ p>

Answer 1

我认为您的需求存在矛盾，永远不会允许每个人都同意令人满意的解决方案。但是，无论如何，让我提出一个解决方案。

每次 session 需要三条信息:

• session 开始时的项目数
• 用于洗牌的随机种子
• 在 session 期间呈现给用户的选择数量

下次 session 开始时，您需要

• 重新创建 firsthalf 和 secondhalf 数组(基于 session 开始时存在的项目数和随机种子)
• 从两个数组中删除项目(基于所做选择的数量)
• 将两个数组合二为一
• 将新项添加到数组
• 您现在拥有一组特定于该用户的项目，可以将其混洗、拆分和呈现

请注意，如果用户中断 session 10 次，则您需要保留 10 个 {count,seed,choices} 元组实例。要开始，您需要 recreate,remove,combine,add 10 次以获得当前 session 的数组。