Random But Unique Pairings, with Conditions

I need some help/direction in setting up a PHP script to randomly pair up items in an array.

• The items should be randomly paired up each time.

• The items should not match themselves ( item1-1 should not pair up with item1-1 )

• Most of the items have a mate (ie. item1-1 and item1-2). The items should not be paired with their mate.

I've been playing around with the second script in this post but, I haven't been able to make any progress. Any help is appreciated.

Very simple approach, but hopefully helpful to you:

(mates, if grouped in an array (e.g. array('a1', 'a2')), will not be paired.)

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'),
);

Update:

foreach(matchUp($array) as $pair) {
  list($a, $b) = $pair + array(null, null);
  echo '<div style="border: solid 1px #000000;">' . $a . ' + ' . $b . '</div>';
}

With the randomness, there is no guarantee that a full correct solution will be reached.

Certain problem sets are more likely to be solved than others. Some will be impossible.

You can configure how many times it will try to achieve a good solution. After the specified number of tries it will return the best solution it could find.

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

Case 1: if all elements had a mate

If all elements had a mate, the following solution would work, although I don't know if it would be perfectly random (as in, all possible outputs having the same probability):

1. Shuffle the list of elements, keeping mates together

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

2. Shift the second mate to the right. The matches have been formed.

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

(Edit1: if applied exactly as described, there is no way a1 ends up matched with b1. So, before shifting, you may want to throw a coin for each pair of mates to decide whether they should change their order or not.)

Case 2: if only some elements have a mate

Since in your question only some elements will have a mate, I guess one could come up with the following:

1. Arbitrarily pair up those elements who don't have a mate. There should be an even number of such elements. Otherwise, the total number of elements would be odd, so no matching could be done in the first place.

   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. Shuffle and shift as in case 1 to form the matches.

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

Again, I don't know if this is perfectly random, but I think it should work.

(Edit2: simplified the solution)

(Edit3: if the total number of elements is odd, someone will be left without a match, so pick an element randomly at the beginning to leave it out and then apply the algorithm above).