-2

我有三个数组：

$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. 元素 in$a必须精确匹配 3 次，元素 in $bor$c必须精确匹配五次，除了（编辑！）其中一个元素$c只能匹配四次。

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

4

1 回答 1

0

所以使用戴夫的一些建议，我想通了。我确信有一种更简单的方法可以做到这一点，但这是我所做的要点：

$b准备工作——创建一个可以匹配的数组$c

  1. 制作一个包含每个成员$b五次的数组。

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

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

  4. 调用array_merge($a_choices, $c_list)合并剩余的东西。现在有 15 个元素可供$a抓取，还有 12 个剩余元素用于$c和$b。

首先选择匹配$a项

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

匹配$b

  1. 现在使用 中的元素$b，将它们与来自的元素进行匹配$c_choices，就像我们对来自的元素所做的那样$a——再次确保始终选择任何出现得太频繁的元素。准备工作部分的重点是确保元素$b和$c剩余元素的正确组合，以使其每次都匹配。
于 2013-08-13T14:29:12.740 回答