在PHP中生成唯一的排列对

Question

I have an associative array:

$arr = [];
$arr['One'] = 1;
$arr['Two'] = 2;
$arr['Three'] = 3;
$arr['Four'] = 4;
$arr['Five'] = 5;
$arr['Six'] = 6;

From which i'd like to generate permutation pairs with it's keys:

$keys = array_keys($arr);
$result = generatePermutations($keys);

Where $result would be an array of arrays of unique pairs:

//as per example, $result =
$result = [[['One','Two'],['Three','Four'],['Five','Six']],
           [['One','Three'],['Two','Four'],['Five','Six']],
           [['One','Four'],['Two','Three'],['Five','Six']],
           [['One','Five'],['Two','Three'],['Four','Six']],
           [['One','Two'],['Three','Five'],['Four','Six']],
           [['One','Three'],['Two','Five'],['Four','Six']],
           [['One','Six'],['Two','Three'],['Four','Five']],
           [['One','Two'],['Three','Six'],['Four','Five']],
           etc..
          ];

I found multiple ways to generate permutations, yet most of them didn't focus specifically on pairs and a lot of them put all the permutations in a single array.

Answer 1

I am going to call this a "working solution" at best. It is certainly possible that I have redundant filters or wasted iterations, but I've been developing and debugging this for too many hours now and I'm no longer sharp. If/When I discover ways to refined this code block (or someone offers a suggestion) I will update my answer.

Code: (Demo)

function pairedPerms($arr){
    $val1=$arr[0];
    $pairs_per_set=sizeof($arr)/2;
    foreach($arr as $v1){  // $arr is preserved/static
        $arr=array_slice($arr,1);  // modify/reduce second foreach's $arr
        foreach($arr as $v2){
            if($val1==$v1){
                $first[]=[$v1,$v2];  // unique pairs as 2-d array containing first element
            }else{
                $other[]=[$v1,$v2]; // unique pairs as 2-d array not containing first element
            }            
        }
    }

    for($i=0; $i<$pairs_per_set; ++$i){  // add one new set of pairs per iteration
        if($i==0){
            foreach($first as $pair){
                $perms[]=[$pair]; // establish an array of sets containing just one pair
            }
        }else{
            $expanded_perms=[];
            foreach($perms as $set){
                $values_in_set=[];  // clear previous data from exclusion array
                array_walk_recursive($set,function($v)use(&$values_in_set){$values_in_set[]=$v;}); // exclude pairs containing these values
                $candidates=array_filter($other,function($a)use($values_in_set){
                    return !in_array($a[0],$values_in_set) && !in_array($a[1],$values_in_set);
                });
                if($i<$pairs_per_set-1){
                    $candidates=array_slice($candidates,0,sizeof($candidates)/2);  // omit duplicate causing candidates
                }
                foreach($candidates as $cand){
                    $expanded_perms[]=array_merge($set,[$cand]); // add one set for every new qualifying pair
                }
            }
            $perms=$expanded_perms;  // overwrite earlier $perms data with new forked data
        }
    }
    return $perms;
}
//$arr=['One'=>1,'Two'=>2];
//$arr=['One'=>1,'Two'=>2,'Three'=>3,'Four'=>4];
$arr=['One'=>1,'Two'=>2,'Three'=>3,'Four'=>4,'Five'=>5,'Six'=>6];
//$arr=['One'=>1,'Two'=>2,'Three'=>3,'Four'=>4,'Five'=>5,'Six'=>6,'Seven'=>7,'Eight'=>8];
$result=pairedPerms(array_keys($arr));
//var_export($result);

echo "[
";
foreach($result as $sets){
    echo "\t[ ";
    foreach($sets as $pairs){
        echo "[",implode(',',$pairs),"]";
    }
    echo " ]
";
}
echo "]";

Output:

[
    [ [One,Two][Three,Four][Five,Six] ]
    [ [One,Two][Three,Five][Four,Six] ]
    [ [One,Two][Three,Six][Four,Five] ]
    [ [One,Three][Two,Four][Five,Six] ]
    [ [One,Three][Two,Five][Four,Six] ]
    [ [One,Three][Two,Six][Four,Five] ]
    [ [One,Four][Two,Three][Five,Six] ]
    [ [One,Four][Two,Five][Three,Six] ]
    [ [One,Four][Two,Six][Three,Five] ]
    [ [One,Five][Two,Three][Four,Six] ]
    [ [One,Five][Two,Four][Three,Six] ]
    [ [One,Five][Two,Six][Three,Four] ]
    [ [One,Six][Two,Three][Four,Five] ]
    [ [One,Six][Two,Four][Three,Five] ]
    [ [One,Six][Two,Five][Three,Four] ]
]