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.
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] ]
]
In python it's as easy as
result = itertools.permutations(keys, 2)
If you want to do it from scratch algorithmic-ally, you could implement a recursive function like this. I've written something pretty naive in python, sorry it's not PHP.
// permutation function
def permutations(my_list, target_len, curr_perm):
// base case
if len(curr_perm) = target_len:
print(curr_perm)
return
for item in my_list:
// don't add duplicates
if item in curr_perm:
continue
next_perm = curr_perm.copy()
next_perm.append(item)
// recursive call
permutations(my_list, target_len, next_perm)
// generate permutations of length 2
permutations(['one', 'two', 'three'], 2, [])
<?php
$arr = [];
$arr['One'] = 1;
$arr['Two'] = 2;
$arr['Three'] = 3;
$arr['Four'] = 4;
foreach($arr as $key1=>$val1) {
foreach($arr as $key2=>$val2) {
if($val1>$val2) continue;
if($key1 !== $key2) {
echo "[$key1, $key2], ";
}
}
}
Iterate through them twice to generate the unique combinations, then iterate through the combinations to form the unique pairs:
<?php
$arr = [];
$arr['One'] = 1;
$arr['Two'] = 2;
$arr['Three'] = 3;
$arr['Four'] = 4;
function generatePermutations($array) {
$permutations = [];
$pairs = [];
$i = 0;
foreach ($array as $key => $value) {
foreach ($array as $key2 => $value2) {
if ($key === $key2) continue;
$permutations[] = [$key, $key2];
}
array_shift($array);
}
foreach ($permutations as $key => $value) {
foreach ($permutations as $key2=>$value2) {
if (!in_array($value2[0], $value) && !in_array($value2[1], $value)) {
$pairs[] = [$value, $value2];
}
}
array_shift($permutations);
}
return $pairs;
}
print_r(generatePermutations($arr));
To simplify the problem, you can divide it into two parts.
Firstly, generate all combinations. You can use the following function for that (the idea came from Tom Butler's post):
function getCombinations(array $array)
{
$num = count($array);
$total = pow(2, $num);
for ($i = 1; $i < $total; $i++) {
$combination = [];
for ($j = 0; $j < $num; $j++) {
if (pow(2, $j) & $i) {
$combination[$j] = $array[$j];
}
}
yield $combination;
}
}
Then you can filter all combinations and keep only those with two elements in them:
$keys = array_keys($arr);
$result = array_filter(
iterator_to_array(getCombinations($keys)),
function ($combination) {
return count($combination) === 2;
}
);
Here is working demo.