在 PHP 中有效地创建满足特定条件的随机数组项对


Efficiently creating pairs of random array items in PHP that meet certain criteria

我有三个数组:

$a有五个元素,$b&c有四个元素。

$a的每个成员都必须与来自$b$c的成员随机配对三次。但是,$b$c 中的每个元素必须与其他两个数组中的五个元素随机配对。

这些配对中的每一个都必须是唯一的,并且元素不能与自身配对。

例如:

$a = array('a1', 'a2', 'a3', 'a4', 'a5');
$b = array('b1', 'b2', 'b3', 'b4');
$c = array('c1', 'c2', 'c3', 'c4');

a1的配对可能如下所示:

'a1', 'b3'
'a1', 'b4'
'a1', 'c2'

c3的配对可能看起来像

'c3', 'a2'
'c3', 'b3'
'c3', 'a4'

所以再一次,我试图进行随机配对:

  1. 元素必须与其他数组中的元素匹配(因此它们无法匹配自身(。它们可以是任何一个中的任何一个。
  2. 每个匹配项必须是唯一的
  3. $a中的元素必须匹配 3 次,$b$c中的元素必须精确匹配 5 次,除了(编辑!($c中的一个元素只能匹配四次。

我找到了一个解决方案,它的工作原理是基本上打乱数组并检查它们是否排列,但显然这非常慢 - 大约需要 100-5000 次尝试才能获得一个有效的数组。由于这是针对将发生数千/数百万次的模拟,因此这不会削减它。我希望有一种方法可以在第一次尝试时生成这些配对。

因此,根据戴夫的一些建议,我想通了。我确信有一种更简单的方法可以做到这一点,但这是我所做的要点:

准备工作 -- 创建一个数组,其中$b可以与$c匹配

  1. 创建一个数组,其中包含 $b 的每个成员五次。

  2. 洗牌该数组,并在第 8 个成员之后剪切它。第一部分进入一个数组,我们称之为 $a_choices .对于第二部分,我们将称之为 $b_choices ,调用array_count_values()并确定每个元素出现的次数。

  3. 创建一个包含 $c 的每个成员五次的数组(除了一个会出现 4 倍的成员(,我们称之为 $c_list 。然后使用上面的直方图,根据成员出现的次数从$c元素创建一个数组。例如,如果来自$b的成员出现 3x、3x、4x 和 2x,那么我需要来自$c的四个元素:两个显示为 4x,一个为 3x,一个为 1x。这些被放入一个数组中,$c_choices .元素是从$c_list中随机挑选的,然后从该数组中移出并放入$c_choices中。

  4. 调用array_merge($a_choices, $c_list)以合并剩余的内容。现在有 15 个元素可供$a抓取,$c$b都有 12 个剩余元素。

首先选择$a匹配项

  1. 遍历$a中的每个元素,并从$a_choices中随机选择三个。但是,如果任何元素出现得太频繁,这次需要抓住它。例如,如果我匹配$a中的倒数第二个元素,那么我需要从$a_choices中抓取出现两次的任何元素。如果我选择倒数第三,那么我会抓取出现 3 倍的任何元素。 等等。这可确保$a中的最后一个元素可以进行 3 个唯一匹配。

匹配$b

  1. 现在使用 $b 中的元素,将它们与$c_choices中的元素匹配,就像我们对$a中的元素所做的那样 - 再次确保始终选择任何出现频率太高的元素。准备部分的重点是确保$b和剩余元素的$c完全正确组合,使其每次都匹配。