Reduce an associative array to randomised pairs of unique values

Question

I am trying to reduce an associative array to pairs of unique values, whereby the keys are letters to be paired and the values are their count()s.

Each pair cannot contain the same letter twice such as AA or BB.

It is permissible for more than one occurrence of the same pair.
e.g. AC, DC, AC, DC are all valid in the resultant array

Every time a letter is picked, its associated number decreases by one until none remain, or

any odd/leftover letters should be flagged and not ignored, e.g. Array([paired]=>Array(...) [unpaired]=>Array(...))

Sample input:

Array(
    [A] => 8
    [B] => 16
    [C] => 15
    [D] => 4
    [E] => 1
)

Possible output:

[
    'paired' => [
        'BD', 'AE', 'BC', 'AC', 'BC', ...
    ],
    'unpaired' => [
        'C' => 4
    ]
]

I would prefer two unique letters to be chosen at random, but if that is too hard then the resultant array should be easily shuffle()-able

I have tried various combinations of array_reduce(), array_map(), array_walk(), array_unique() etc., even Pear's Math_Combinatorics, but all to no avail.

Answer 1

Here is a function that will generate the results you want. It iterates over the letters array, filtering out letters which have been completely used, until there is only one letter which is unused. The list of pairs and the unused letter are then returned in an array:

function random_pairs($letters) {
    $pairs = array();
    $letters = array_filter($letters);
    while (count($letters) > 1) {
        $keys = array_keys($letters);
        shuffle($keys);
        list($letter1, $letter2) = array_slice($keys, 0, 2);
        $pairs[] = "$letter1$letter2";
        $letters[$letter1]--;
        $letters[$letter2]--;
        $letters = array_filter($letters);
    }
    return array('pairs' => $pairs, 'unpaired' => $letters);
}

Sample usage:

$letters = array('A' => 8, 'B' => 16, 'C' => 15, 'D' => 4, 'E' => 1);
print_r(random_pairs($letters));

Sample output:

Array
(
    [pairs] => Array
        (
            [0] => CB
            [1] => CE
            [2] => CD
            [3] => BD
            [4] => CB
            [5] => DC
            [6] => AB
            [7] => CA
            [8] => DA
            [9] => BC
            [10] => BA
            [11] => BA
            [12] => AB
            [13] => BA
            [14] => BC
            [15] => AB
            [16] => BC
            [17] => CB
            [18] => CB
            [19] => CB
            [20] => CB
        )
    [unpaired] => Array
        (
            [C] => 2
        )
)

Demo on 3v4l.org