Faire correspondre un ensemble de personnes pour donner des cadeaux, comment gérer ce cas de bordure

Question

Je fais correspondre un tableau de personnes les uns aux autres. Ils ne peuvent pas être assortis à eux-mêmes et chaque personne ne peut être jumelée avec un autre. J'ai travaillé cela mais je suis tombé dans une affaire de bord. Si la personne jumelée est elle-même la seule personne à ne pas avoir été appariée, nous sommes bloqués.

Exemple:

$names = array('Dad','Mom','Harrald','Yu','Sandra','Dave', 'Andy & Kim'); 
$drawn = array(); 
$tn = count($names)-1; 
$i = mt_rand(0, $tn); 

foreach ($names as $name) {   
    while($name == $names[$i] || in_array($names[$i], $drawn)) { 
      $i = mt_rand(0, $tn); 
    } 
    echo $name. ' has ' . $names[$i].'<br />'; 
    array_push($drawn, $names[$i]); 
} 

Cela pourrait produire:
Papa a Sandra
Maman a Yu
Harrald a Dave
... etc, etc.

Le problème est quand il arrive au dernier élément du tableau, 'Andy & Kim', si 'Andy & Kim' est le seul élément qui n'a pas encore été ajouté au $drawn tableau alors nous avons un cas de carre parce que vous ne pouvez pas correspondre 'Andy & Kim' à eux-mêmes. Dans mon exemple, cela peut se traduire par être coincé dans cette boucle tout en finissant par expirer ... voyez ce que je veux dire? Comment pourriez-vous gérer cela (c'est uniquement pour mon propre amusement que je suis allé à assommer un cadeau rapide donnant un script de match-up pour ma mère à utiliser et réalisé que c'était un problème potentiel).

Oh, de meilleures façons d'implémenter un tel modèle seraient les plus intéressantes à voir. THX!

Answer 1

Sans correspondre à quelqu'un qui a déjà une correspondance, vous ne pouvez pas. Voilà comment fonctionnent les nombres impairs. :/

Donc soit correspondre avec quelqu'un qui a déjà une correspondance, ou demander à votre professeur de ne pas vous donner de mauvaises entrées. ;)

Answer 2

Sûrement, plutôt que d'utiliser l'itération, il est plus facile de simplement mélanger la matrice; et ensuite correspondre 1er au 2ème, 2ème au 3ème, etc, avec le dernier étant apparié au 1er à nouveau pour compléter le cercle

Answer 3

Vous devez revenir en arrière à ce point. Il existe de nombreux algorithmes qui nécessitent un retour en arrière, car (comme vous l'avez constaté) il s'avère que le choix que vous avez fait à un stade antérieur était en réalité impossible. Vous devrez stocker les points de choix précédents d'une manière ou d'une autre, de sorte que lorsque vous frappez l'impossibilité (ou que vous réussissiez, si votre tâche consiste à obtenir toutes les solutions), vous pouvez revenir au dernier choix non entièrement exploré. un choix différent.