我需要一些帮助/方向在设置一个PHP脚本随机配对数组中的项目。
-
每次随机配对。
-
物品本身不应该匹配(item1-1不应该与item1-1配对)
-
大多数项有一个配偶(ie)。 item1-1和item1-2)。物品不应与其同伴配对。
我在这篇文章中一直在玩第二个脚本,但是,我没有取得任何进展。
非常简单的方法,但希望对您有所帮助:
配偶(,如果数组中分组(例如数组(a1, a2) ),不会配对。)
function matchUp($array) {
$result = array();
while($el = array_pop($array)) {
shuffle($array);
if (sizeof($array) > 0) {
$candidate = array_pop($array);
$result[] = array(
array_pop($el),
array_pop($candidate)
);
if (sizeof($el) > 0) {
$array[] = $el;
}
if (sizeof($candidate) > 0) {
$array[] = $candidate;
}
}
else {
$result[] = array(array_pop($el));
}
}
return $result;
}
$array = array(
array('a1', 'a2'),
array('b1', 'b2'),
array('c1'),
array('d1'),
array('e1', 'e2'),
array('f1'),
array('g1', 'g2'),
);
:
foreach(matchUp($array) as $pair) {
list($a, $b) = $pair + array(null, null);
echo '<div style="border: solid 1px #000000;">' . $a . ' + ' . $b . '</div>';
}
由于具有随机性,因此无法保证得到完全正确的解决方案。
某些问题集比其他问题集更容易被解决。有些是不可能的。
您可以配置它将尝试多少次来实现一个好的解决方案。在指定次数的尝试后,它将返回它能找到的最佳解决方案。
function pairUp (array $subjectArray) {
// Config options
$tries = 50;
// Variables
$bestPaired = array();
$bestUnpaired = array();
for($try = 1; $try <= 50; $try++) {
$paired = array();
$unpaired = array();
$toBePaired = $subjectArray;
foreach($subjectArray as $subjectIndex => $subjectValue) {
// Create array without $thisValue anywhere, from the unpaired items
$cleanArray = array();
foreach($toBePaired as $index => $value) {
if($value != $subjectValue) {
array_push($cleanArray, array(
'index' => $index,
'value' => $value
));
}
}
sort($cleanArray); // reset indexes in array
// See if we have any different values left to match
if(count($cleanArray) == 0) {
array_push($unpaired, $subjectValue);
continue;
}
// Get a random item from the clean array
$randomIndex = rand(0,count($cleanArray)-1);
// Store this pair
$paired[$subjectIndex] = $subjectValue . '-' . $cleanArray[$randomIndex]['value'];
// This item has been paired, remove it from unpairedItems
unset($toBePaired[$cleanArray[$randomIndex]['index']]);
sort($toBePaired);
}
// Decide if this is our best try
if(count($paired) > count($bestPaired)) {
$bestPaired = $paired;
$bestUnpaired = $unpaired;
}
// If we had no failures, this was a perfect try - finish
if(count($unpaired) == 0) { $break; }
}
// We're done, send our array of pairs back.
return array(
'paired' => $bestPaired,
'unpaired' => $bestUnpaired
);
}
var_dump(pairUp(array('a','b','c','d','e','a','b','c','d','e')));
/*
Example output:
array(2) {
["paired"]=>
array(10) {
[0]=>
string(3) "a-b"
[1]=>
string(3) "b-c"
[2]=>
string(3) "c-d"
[3]=>
string(3) "d-e"
[4]=>
string(3) "e-a"
[5]=>
string(3) "a-b"
[6]=>
string(3) "b-e"
[7]=>
string(3) "c-d"
[8]=>
string(3) "d-c"
[9]=>
string(3) "e-a"
}
["unpaired"]=>
array(0) {
}
}
*/
情形1:如果所有元素都有配偶
如果所有元素都有配偶,那么下面的解决方案将有效,尽管我不知道它是否完全随机(即所有可能的输出具有相同的概率):
-
打乱元素列表,保持伙伴在一起
original list = (a1,a2),(b1,b2),(c1,c2),(d1,d2) shuffled = (c1,c2),(d1,d2),(a1,a2),(b1,b2)
-
右移第二副。匹配已经形成。
shifted = (c1,b2),(d1,c2),(a1,d2),(b1,a2)
(Edit1:如果完全按照描述应用,a1
最终不可能与b1
匹配。因此,在移动之前,你可能想要向每对伙伴投掷一枚硬币,以决定他们是否应该改变顺序。
情况2:如果只有部分元素有配偶
既然在你的问题中只有一些元素会有配偶,我想可以得出以下结论:
-
任意配对那些没有配偶的元素。应该有偶数个这样的元素。否则,元素的总数将是奇数,因此从一开始就不能进行匹配。
original list = (a1,a2),(b1,b2),c1,d1,e1,f1 // c1,d1,e1 and f1 don't have mates list2 = (a1,a2),(b1,b2),(c1,d1),(e1,f1) // pair them up
-
与情况1一样进行Shuffle和shift以形成匹配。
shuffled = (e1,f1),(a1,a2),(c1,d1),(b1,b2) shifted = (e1,b2),(a1,f1),(c1,a2),(b1,d1)
再次强调,我不知道这是不是完全随机的,但我认为它应该可以工作。
(Edit2:简化解决方案)