Using PHP, randomly pair up group of items, not pairing any with itself, no direct pairings

Question

Assume you have a set of items in an array.

A, B, C, D, E, F, G, H

Using PHP, how would you randomly pair the letters together without pairing them with a duplicate of themselves?

Such as this:

 A->pairedLetter = G
 B->pairedLetter = C
 C->pairedLetter = E
 D->pairedLetter = A
 E->pairedLetter = B
 F->pairedLetter = D
 G->pairedLetter = F

and so on...

EDIT: Oh, and also, If A is paired with F, F can NOT be paired with A. So there will have to be as many relationships as there are items.

Answer 1

I've tried using a copy of the original array and using array_rand() but if it finds the same item as I'm iterating over, I have to run array_rand() again, which can fall into a endless loop.

I'm stumped, there has to be an elegant way to do this.

Answer 2

Duplicate the array. Call shuffle on one array. Then:

1. Check that the first elements are different (if they are switch the first two elements of one array).
2. array_pop off an item from each array to form a pair.
3. If the items are the same, pop two off one array and pair up, then two off the other.

edit

With your extra condition, you'll need to check that every pair doesn't already exist. If it does (at the third stage) you can try taking different combinations (pop off first and third {pop off first, second, third and push second back on}) but you may still end up with an invalid pair at the end so would need to start again.

Answer 3

$arrayValues = range('A','H');
shuffle($arrayValues);
while (count($arrayValues) > 0) {
   echo array_pop($arrayValues),' is matched with ',array_pop($arrayValues),'<br />';
}

EDIT

following changes to the question

$arrayValues = range('A','H');
$tmpArrayValues = $arrayValues;
$pairs = array();
shuffle($tmpArrayValues);
foreach($arrayValues as $arrayValue) {
    $tmpValue = array_pop($tmpArrayValues);
    while (($arrayValue == $tmpValue) || ((isset($pairs[$tmpValue])) && ($pairs[$tmpValue] == $arrayValue))) {
        array_unshift($tmpArrayValues,$tmpValue);
        $tmpValue = array_pop($tmpArrayValues);
    }
    $pairs[$arrayValue] = $tmpValue;
}

foreach($pairs as $key => $value) {
   echo $key,' is matched with ',$value,'<br />';
}

Answer 4

$array = array(
    'A','B','C',
    'D','E','F',
    'G','H','I','J'
);
$new = array();

if(count($array) % 2 != 0)
{
    array_pop($array); // Got to remove 1 element to make them even.
}

foreach($array as $item)
{
    $_t = array_pop($array);
    //Key
    if(!isset($new[$item]))
    {
        $new[$item] = $_t;
        $new[$_t] = $item;
    }
}


var_dump($new);

This would print:

array(10){
    ["A"]=> string(1) "J"
    ["J"]=> string(1) "A"
    ["B"]=> string(1) "I"
    ["I"]=> string(1) "B"
    ["C"]=> string(1) "H"
    ["H"]=> string(1) "C"
    ["D"]=> string(1) "G"
    ["G"]=> string(1) "D"
    ["E"]=> string(1) "F"
    ["F"]=> string(1) "E"
}

the way this works is it loops the values and deletes a value at the same time, so you always have 2 values at once but at the same time shrinking the array by 1.

then when we set the new keys were setting both of them to the new array, so the next time the loop iterates if the same value comes back around it just gets discarded :)

Answer 5

What about this ?

// input array
$arr = array('A','B','C','D','E','F');
// result array
$res = array();
// get first element and save it
$first = $ele1 = array_shift($arr);
while(count($arr)) {
    // get random element
    $ele2 = array_rand($arr);
    // associate elements
    $res[$ele1] = $arr[$ele2];
    // random element becomes next element
    $ele1 = $arr[$ele2];
    // delete the random element
    array_splice($arr, $ele2, 1);
}
// associate last element woth the first one
$res[$ele1] = $first;

print_r($res);

Output:

Array
(
    [A] => B
    [B] => F
    [F] => E
    [E] => D
    [D] => C
    [C] => A
)

Works with even number of elements arrays as well as odd.

Update, using Chris' algorithm:

$arr = array('A','B','C','D','E','F');
shuffle($arr);
$res=array();
for($i=0;$i<count($arr);$i++) {
  $res[$arr[$i]] = $arr[$i+1];
}
$res[$arr[count($arr)-1]] = $arr[0];

Answer 6

Does it have to be perfectly random given your constraints? If you were willing to add in another constraint then you could make the problem very simple. If you were willing to make it so that the mappings all formed a single loop then you could just shuffle your array and then make element one pont at two, two point at three and the last element points at the first. You will guarantee that no element can poitn at itself (unless the array only has one element), no element will point at the element pointing at it (unless the array only has two elements) and that no element will be pointed at by more than one item.

You are restricting your results set slightly so losing a certain amount of the random element but if you are happy with this its extremely simpel to do.

Answer 7

Using the shuffle function on the array and checking that the mappings are valid (A doesn't map to A and that if A maps to B then B doesn't map to A). The following should do what you want:

$values = array('A','B','C','D','E','F','G');
$new_values = array('A','B','C','D','E','F','G');

$random = shuffle($new_values);
//randomly shuffle the order of the second array
$mappings = array();

$validMappings = false;
//continue to retry alternative mappings until a valid result is found
while(!$validMappings) {
   //set the mappings from $values to $new_values
   for($i = 0; $i < count($values); $i++) {
        $mappings[$values[$i]] = $new_values[$i];
    }

    $validMappings = true;
    //check validity of the current mapping
    foreach ($mappings as $key=>$value) {
        if($mappings[$key] == $mappings[$value]) {
            $validMappings = false;
            break;
        }
    }
    //if false shuffle the new values and test again
    if(!$validMappings) {
        $random = shuffle($new_values);
    }
}
print_r($mappings);