随机但唯一配对，条件

Question

我需要一些帮助/方向来设置一个PHP脚本来随机配对数组中的项目。

• 这些项目应该随机配对每次。

• 的项目不应该与自身匹配（item1-1不应item1-1配对）

• 的项目大多数有一个伴侣（即 item1-1和item1-2 ）。这些物品不应与配偶配对。

我一直在玩the second script in this post但是，我还没有能够取得任何进展。任何帮助表示赞赏。

Answer 1

非常简单的方法，但希望对您有所帮助：

（队友，如果分组在阵列（例如阵列（ '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>'; 
} 

Answer 2

随机性不能保证能够达到完全正确的解决方案。

某些问题集比其他问题集更可能被解决。有些是不可能的。

您可以配置它尝试实现一个好的解决方案的次数。经过指定次数的尝试后，它会返回找到的最佳解决方案。

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) { 
    } 
} 
*/ 

Answer 3

案例1：如果所有元素有一个伴侣

如果所有元素有一个伴侣，下面的解决办法的工作，虽然我不知道这是否会是完全随机的（如中，具有相同的概率的所有可能的输出）：

1. 洗牌元素的列表，保持配合在一起

   original list = (a1,a2),(b1,b2),(c1,c2),(d1,d2) 
   shuffled  = (c1,c2),(d1,d2),(a1,a2),(b1,b2) 
   

2. 将第二个队友转移到右侧。比赛已经形成。

   shifted  = (c1,b2),(d1,c2),(a1,d2),(b1,a2) 
   

（EDIT1：如果应用精确描述，也没有办法a1结束了b1匹配所以，转移之前，你可能想扔一粒纽扣每对伴侣的决定是否。他们应该改变它们的顺序或不）

案例2：如果只有一些元素有其队友

由于您的问题只是一些元素将有一个伴侣，我想一个能拿出以下内容：

1. 任意配对那些没有配偶的元素。应该有偶数的这种元素。否则，元素的总数将是奇数，因此不能首先完成匹配。

   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 
   

2. 按照情况1进行随机和移位以形成匹配。

   shuffled = (e1,f1),(a1,a2),(c1,d1),(b1,b2) 
   shifted = (e1,b2),(a1,f1),(c1,a2),(b1,d1) 
   

再说一遍，我不知道这是否是完全随机的，但我认为它应该工作。

（EDIT2：简化了溶液）

（EDIT3：如果元素的总个数是奇数，有人会留下不匹配，所以随机选择的元件在开始时离开它，然后应用上面的算法）。