生成組合並根據三個參數選擇最佳

Question

我試圖生成對，然後想根據設置的參數選擇最佳對。生成配對並不困難，但棘手的是要從中選擇最好的配對。

我覺得這是最好的，如果我會用例子繼續，讓我們我們目前有4個元素，並將其命名element1，element2，element3，element4。每個元素具有生成對時是重要的性能：

while ($element = mysqli_fetch_assoc($queryToGetElements)){ 
    $elementId = $element['eid']; 
    $elementOpponents = getElementOpponents($elementId); //Returns opponents Id's as an array. These are the possible elements which can be paired. 
    $elementPairs = generatePairsWithElement($elementId,$elementOpponents); //Pair generating function, this uses the possible pairs which is defined below. Pretty much checks who hasn't paired before and puts them together in the pair. 
    $bestPair = chooseBest($elementPairs,$allOtherPairs) // This should select the best pair out of the elementPairs considering uniqueness with other pairs. 

} 

//So let's define our four elements: 
$element1Place = 1; 
$element2Place = 2; 
$element3Place = 3; 
$element4Place = 4; 
//execute while loop with $element1: 
$element1Opponents = [$element2,$element3,$element4]; 
$elementPairs = [[$element1,$element3],[$element1,$element3],[$element1,$element4]]; 
$element2Opponents = [$element3] 
$elementPairs = [[$element2,$element3],[$element2,$element1]]; 
$elemenet3Opponents = [$element2] 
$elementPairs = [[$element2,$element3],[$element1,$element3]]; 
$element4Opponents = [$element1] 
$elementPairs = [[$element1,$element4]; 
//Pairs returned should be: [$element1,$element4] & [$element2,$element3]. 

• Possible pairs - 這是可以與當前元素配對的其它元件的陣列。在當前的例子中，我確實有4個元素，但其中一些元素不能配對在一起，因爲他們以前可能已經配對在一起（並且不允許兩人配對）。該限制適用於功能generatePairsWithElements。
• Place - 這是一個唯一的整數值，對於兩個元素不能相同。當選擇配對元素時，將選擇低於Place的元素。該限制適用於函數chooseBest。
• 組合必須是唯一的 - 例如，如果element1可與element2和element3和element4配對只能與element2然後element1配對只能與element3即使element1較早迭代和element2具有較低的地方配對。所以組合將是[element1,element3] and [element2,element4]。該限制適用於函數chooseBest。

如果不存在第三方面的話，這個任務就不會那麼困難，會產生獨特的組合。迭代可能的對手並選擇最好的對手是相當容易的，但是生成獨特的組合對於我的項目至關重要。

Answer 1

所以，我想我想通了，這要歸功於威廉和感謝從另一個線程ishegg。

因此，作爲一個先決條件，我有一個數組$unmatchedPlayers這是一個關聯數組，其中元素名稱是一個鍵和元素位置（Place）是一個值。

首先使用該信息，即時生成唯一置換對

function generatePermutations($array) { 
    $permutations = []; 
    $pairs = []; 
    $i = 0; 
    foreach ($array as $key => $value) { 
     foreach ($array as $key2 => $value2) { 
      if ($key === $key2) continue; 
      $permutations[] = [$key, $key2]; 
     } 
     array_shift($array); 
    } 
    foreach ($permutations as $key => $value) { 
     foreach ($permutations as $key2=>$value2) { 
      if (!in_array($value2[0], $value) && !in_array($value2[1], $value)) { 
       $pairs[] = [$value, $value2]; 
      } 
     } 
     array_shift($permutations); 
    } 
    return $pairs; 
} 

這將返回我的陣列稱爲$pairs其具有不同的可能對陣列內側的方式：$pairs= [[['One','Two'],['Three','Four']],[['One','Three'],['Two','Four']],[['One','Four'],['Two','Three']]];

現在我將遍歷數組$pairs並選擇最佳，給每個排列組合一個'分數'：

function chooseBest($permutations,$unmatchedPlayers){ 
    $currentBest = 0; 
    $best = []; 
    foreach ($permutations as &$oneCombo){ //Iterate over all permutations [[1,2],[3,4]],[..] 
     $score = 0; 
     foreach ($oneCombo as &$pair){ 
      $firstElement = $pair[0]; 
      $secondElement = $pair[1]; 
      //Check if these two has played against each other? If has then stop! 
      if(hasPlayedTP($firstElement,$secondElement)){ 
       $score = 0; 
       break; 
      } 
      $score += $unmatchedPlayers[$firstElement]; 
      $score += $unmatchedPlayers[$secondElement]; 
     } 
     if($score > $currentBest){ 
      $currentBest = $score; 
      $best = $oneCombo; 
     } 
    } 
    return $best; 
} 

計算最佳分數並返回排列對。

Answer 2

所以我想用一個免責聲明來說這個答案：我不是數學家;我對線性代數，矩陣代數和統計的理解是足夠的，但決不是廣泛的。可能有辦法以更少的代碼行或更有效率的方式來實現相同的結果。但是，我相信這個答案的詳細程度會讓更多的人瞭解它，並且一步一步地遵循邏輯。現在已經不存在了，讓我們來看看它。

計算的每對

與當前方法的問題是，找到最佳匹配的邏輯正在發生的事情，你遍歷查詢結果的權重。這意味着當你到達最後一次迭代時，你可能會留下無法匹配的元素。爲了解決這個問題，我們需要分解一下這個過程。第一步是獲取給定數組元素的所有可能對。

$elements = [ 
    1,2,3,4,5,6  
]; 

$possiblePairs = []; 
for($i = 1; $i <= $elementCount; $i++) { 
    for($j = $i + 1; $j <= $elementCount; $j++) { 
     $possiblePairs[] = [ 
      'values' => [$elements[$i - 1], $elements[$j - 1]], 
      'score' => rand(1, 100) 
     ]; 
    } 
} 

正如你所看到的，對於每個可能的對，我也附加score元素，在這種情況下，一個隨機整數。這個分數表示這對配對的強度。這個score的值實際上並不重要：它可以是特定範圍內的值（例如：0-100）或者是由您自己的某些函數定義的每個值。這裏最重要的是配對潛力最高的配對應該有更高的分數，而配對中幾乎沒有潛力的配對應該得分較低。如果有些配對絕對不能在一起，只需將score設置爲零即可。

接下來要使用的值比score值對數組進行排序，以便更強匹配的對位於頂部，而底部的弱對（或不可能）對。我使用PHP 7.0的spaceship operator來完成工作，但是您可以通過其他方式來實現這種排序here。

usort($possiblePairs, function($a, $b) { 
    return $b['score'] <=> $a['score']; 
}); 

現在我們終於裝備完成了我們的最終輸出。這一步實際上相當簡單：循環遍歷可能的對，檢查值是否已被使用，然後將它們推送到輸出數組。

$used = []; // I used a temporary array to store the processed items for simplicity 
foreach($possiblePairs as $key => $pair) { 
    if($pair['score'] !== 0 && // additional safety if two elements cannot go together 
     !in_array($pair['values'][0], $used) && 
     !in_array($pair['values'][1], $used)) 
    { 
     $output[] = $pair['values']; // push the values to the return of the function 
     array_push($used, $pair['values'][0], $pair['values'][1]); // add the element to $used so they get ignored on the next iteration 
    } 
} 

var_dump($output); 

// output 
array(3) { 
    [0]=> array(2) { 
     [0]=> int(2) 
     [1]=> int(4) 
    } 
    [1]=> array(2) { 
     [0]=> int(1) 
     [1]=> int(3) 
    } 
    [2]=> array(2) { 
     [0]=> int(5) 
     [1]=> int(6) 
    } 
} 

它就在那裏！首先選擇最強的一對，然後優先選擇。玩弄權重算法，看看什麼適合您的特定需求。最後一句話：如果我是在業務應用程序的上下文中編寫此代碼，那麼如果碰巧有不匹配的對（畢竟，這在統計上是可行的），我可能會添加一些錯誤報告，以便更容易地發現問題的原因，並決定權重是否需要調整。

---

你可以嘗試的例子here

---

編輯補充：

爲了防止其中一個元素被存儲在一對時，另一件只能與配對的情況那第一個元素（這會導致一對永遠不會被創建），你可以嘗試這個小補丁。我開始在getScore()函數中重新創建您的需求。

function getScore($elem1, $elem2) { 
    $score; 

    if($elem1 > $elem2) { 
     $tmp = $elem1; 
     $elem1 = $elem2; 
     $elem2 = $tmp; 
    } 

    if($elem1 === 1 && $elem2 === 2) { 
     $score = 100; 
    } 
    elseif(($elem1 === 3 && $elem2 !== 2) || ($elem1 !== 2 && $elem2 === 3)) { 
     $score = 0; 
    } 
    else { 
     $score = rand(0, 100); 
    } 

    return $score; 
} 

然後，我修改了$possiblePairs數組的創建做了兩件事。

1. 如果比分是0，不追加到數組和多少場比賽被發現的每個元素

2. 跟蹤。通過這樣做，任何只有一個可能匹配的元素將在$nbMatches的1中具有關聯的值。

   $nbMatches = [ 
       1 => 0, 
       2 => 0, 
       3 => 0, 
       4 => 0 
   ] 
   
   $possiblePairs = []; 
   for($i = 1; $i <= $elementCount; $i++) { 
       for($j = $i + 1; $j <= $elementCount; $j++) { 
        $score = getScore($elements[$i - 1], $elements[$j - 1]); 
        if($score > 0) { 
         $possiblePairs[] = [ 
          'values' => [$elements[$i - 1], $elements[$j - 1]], 
          'score' => $score 
         ]; 
         $nbMatches[$elements[$i - 1]]++; 
         $nbMatches[$elements[$j - 1]]++; 
        } 
       } 
   } 
   

然後，我添加另一個循環，使得它們最終在列表的頂部的其餘部分之前被處理，將撞了的那些元素。

foreach($nbMatches as $elem => $intMatches) { 
    if($intMatches === 1) { 
     foreach($possiblePairs as $key => $pair) { 
      if(in_array($elem, $pair['values'])) { 
       $possiblePairs[$key]['score'] = 101; 
      } 
     } 
    } 
} 

usort($possiblePairs, function($a, $b) { 
    return $b['score'] <=> $a['score']; 
}); 

的輸出是：

array(2) { 
    [0]=> array(2) { 
     [0]=> int(2) 
     [1]=> int(3) 
    } 
    [1]=> array(2) { 
     [0]=> int(1) 
     [1]=> int(4) 
    } 
} 

我只是想強調：這只是一個臨時補丁。它不會保護你的情況下，例如，element 1只能匹配element 2和element 3可以也只匹配element 2。但是，我們正在處理的樣本量非常小，並且您擁有的元素越多，這些邊緣案例可能會發生的可能性就越小。 在我看來，這個修復是沒有必要的，除非你只使用4個元素。使用6個元素產生15種可能的組合，10種元素產生45種可能的組合。這些情況已經不太可能發生。另外，如果發現那些邊緣案例仍然發生，最好返回並調整匹配算法使其更加靈活，或者考慮更多參數。

---

您可以嘗試更新的版本here