how to find multidimensional array permutation in php

TL;DR: This code compactly solves the case where all rows contain all values in any order. For a solution to the general case - every row has a sub-set of all possible values - see my other answer.

“If I had only one hour to solve a problem, I would spend up to two-thirds of that hour in attempting to define what the problem is.” -- Albert Einstein

Seems like you want a ragged array squared up with no columns sharing the same ordering. Let's define functions for that:

function array_make_square(array &$array, $fill = ' ') {
    $pad = count(array_keys($array));
    foreach ($array as &$row) {
        $row = array_pad($row, $pad, $fill);
    }
}

function array_organize(array &$outer) {
    $offset = 0;
    foreach ($outer as &$inner) {
        sort($inner);
        array_rotate($inner, $offset++);
    }
}

function array_rotate(array &$array, $offset) {
    foreach (array_slice($array, 0, $offset, true) as $key => $val) {
        unset($array[$key]);
        $array[$key] = $val;
    }
}

Now let's put some wrappers around those to test the behavior:

function solve($test) {
    array_make_square($test);
    array_organize($test);
    return $test;
}

function display($outer) {
    echo "[\n";
    foreach ($outer as $row => $inner) {
        echo "  $row => ['" . implode("', '", $inner) . "']\n";
    }
    echo "]\n";
}

$tests = [
    [ ['X'], ['X'], ['X'] ],
    [ ['X', 'Y'], ['X', 'Y'], ['X', 'Y'] ],
    [ ['X', 'Y', 'Z'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'] ],
];
array_map('display', array_map('solve', $tests));

Which produces:

[
  0 => [' ', ' ', 'X']
  1 => [' ', 'X', ' ']
  2 => ['X', ' ', ' ']
]
[
  0 => [' ', 'X', 'Y']
  1 => ['X', 'Y', ' ']
  2 => ['Y', ' ', 'X']
]
[
  0 => ['X', 'Y', 'Z']
  1 => ['Y', 'Z', 'X']
  2 => ['Z', 'X', 'Y']
]

See it live on 3v4l.org.

I am collecting all the info first i.e. key names like A B C etc., all values like X Y Z etc.. and number of elements per each sub array. Then I create new arrays for each position in the sub array namely pos0, pos1 and pos2 in this case. Then I populate the new sub arrays using the values from valArray ( randomly picking), keeping the constraint that the value must not be repeated in this array or in any other array for the same position.

Hope this helps..

    <?php

    $input = [
        'A' => ['X', 'Y', 'Z','P'],
        'B' => ['X', 'Y', 'Z','Q'],
        'C' => ['X', 'Y', 'Z','R'],
        'D' => ['X','Y','K']
    ];

    // declare two arrays - keyArray will hold all key names like A, B, C
    // valArray will hold all the distinct values like X, Y, Z
    // valLength is number of elements in each sub array

    $keyArray = [];
    $valArray = [];
    $valLength =0; // no of elements in sub array       

    echo "<table width='100%'> <tr> <td width='20%'>&nbsp; </td> <td width='30%'>";
    // this loop will gather all the relevenat info for $keyArray, $valAray and $valLength
    echo "INPUT <br><br>";
    foreach($input as $key => $val) {
        if(is_array($val)) {
            echo "$key <br/>";
            $keyArray[] = $key;
            if(count($val) > $valLength) {
                $valLength = count($val);    
            }

            foreach($val as $key1 => $val1) {
                echo "$key1 => $val1<br>";
                if (! in_array($val1, $valArray)) {
                    //echo "no ...";
                    $valArray[] = $val1;
                }
            }
            echo "<br>----<br>"; 
        }
        else {
           // echo "$key => $val<br>";    
        }            
    }
    echo "</td><td width='30%'>";

    $output =[];

    //create arrays for each position

    for($i=0; $i<$valLength; $i++) {
            $posArr = "pos" . $i;
            $$posArr = [];            
    }

    foreach($keyArray as $key) {
        //echo "$key <br/>";
        $thisArr = [];
        for($i=0; $i<$valLength; $i++) {
            //echo "$i <br>";
            $posArr = "pos" . $i;

            $whileIterations = 0; // no of random iterations to perform before using wildcard 

            $randomKey=array_rand($valArray);
            $new = $valArray[$randomKey];                
            do {
                $randomKey=array_rand($valArray);
                $new = $valArray[$randomKey];  
                $whileIterations++;
                if($whileIterations > 10) { // no of iterations ls limited to 10
                    $new = '';
                    break;
                }
            }while(in_array($new,$thisArr) || in_array($new, $$posArr));

            $thisArr[] = $new; 
            //$$posArr[] = $new;
            if($new != '') {
                array_push($$posArr,$new); 
                // keep this in position array so that same value is not repeated in  the same position  
            }                
        }
        // now one subarray is ready to be assigned
        $keyName = $key;
        $$keyName = [];
        $$keyName = $thisArr;    
    }

    // push sub arrays into output array
    foreach($keyArray as $key) {
        $keyName = $key;  
        //echo "$keyName <br>";
        foreach ($$keyName as $key2) {
           // echo "$key2 <br/>";
        }
        //echo "<br>----<br>";            
        //array_push($output, $$keyName);
        $output[$keyName] = $$keyName;
    }

    echo "OUTPUT <br/><br/>";
    foreach($output as $key => $val) {
        if(is_array($val)) {
            echo "$key <br/>";
            $keyArray[] = $key;               
            foreach($val as $key1 => $val1) {
                echo "$key1 => $val1<br>";
            }
        }
        echo "<br>----<br>"; 

    }

    echo "</td><td width='20%'>&nbsp; </td></tr></table>";

    ?>

You can use array_shift to make a array with all the elements. Then set the lost element to ''. Below code is well commented. https://eval.in/895863

<?php
$ks = ['A', 'B', 'C', 'D'];
$vs = ['X', 'Y', 'Z', 'A'];

$input = [
    'A' => ['X', 'Z'],
    'B' => ['X', 'Z'],
    'C' => ['X', 'Z'],
];

// element not in $inpupt
$diff = array_diff($vs, $input[$ks[0]]);

// array with all the values
$arr = [];
foreach($ks as $k)
{
    $arr[$k] = $vs;
    array_push($vs, array_shift($vs));
}

// set value in the $diff array to ''
$result = array_map(function($value) use ($diff) {
    return array_map( function($v) use ($diff) {
        return in_array($v, $diff) ? '' : $v;
    }, $value);
}, $arr);


print_r($result);

Edit for OP's comment

For the $input with different element, the $diff array should calculated seperately. https://eval.in/896322

<?php
$ks = ['A', 'B', 'C', 'D', 'E'];
$vs = ['X', 'Y', 'Z', 'A'];

$input = [
    'A' => ['X', 'Z'],
    'B' => ['X', 'Z'],
    'C' => ['X', 'A'],
];

// array with all the values
$arr = [];
foreach($ks as $k)
{
    $arr[$k] = $vs;
    array_push($vs, array_shift($vs));
}

// set value in the $diff array to ''
$result = array_map(function($value, $k) use ($input, $vs) {

    // element not in $inpupt[$k]
    $diff = array_diff($vs, isset($input[$k]) ? $input[$k] : []);
    return array_map( function($v) use ($diff) {
        return in_array($v, $diff) ? '' : $v;
    }, $value);
}, $arr, $ks);

// when use multi array for `array_map` the index lost, so combine index with the result here.
$result = array_combine($ks, $result);

print_r($result);

ok i think we are close now i have this idea, there is one thing left to do, described it on the end

1. increase size of input array to number of element of highest occurrences or highest length of child depends what is bugger
2. try to find all placaes for X, then trying to all places for Y and so on.
3. every time when its find add it to array that keeps used elements to prevents duplicates.

helpers:

function getHeight($array) {
    $max2 = $max1 = 0;
    $max = [];
    foreach ($array as $k => $v) {
        if ($max2 < count($v)) {
            $max2 = count($v);
        }
        foreach($v as $elem) {
            if(isset($max[$elem])) {
                $max[$elem]++;
        } else {
            $max[$elem] = 1;
        }
    }

    }
    foreach($max as $m) {
        if ($max1 < $m) {
            $max1 = $m;
        }
    }
    return max($max2, $max1);
}

function getRow($array, $j)
{
    $res = [];
    foreach ($array as $k => $v) {
        $res[] = $v[$j] ?? '';
    }
    return $res;
}

code

function solve_this_array_please() {
    $input = [
        'A' => ['X', 'Y', 'Z', 'I'],
        'B' => ['X', 'Y', 'Z', 'I'],
        'C' => ['X', 'Y', 'Z', 'I'],
        'D' => ['X', 'Y', 'Z', 'I'],
    ];

    usort($input,  function($i, $j) {
        return count($i) <=> count($j);
    });

    $output = [];

    $h = getHeight($input);

    // filling te missing wildcards;
    foreach($input as $k => $v) {
        for($i=0;$i<$h;$i++) {
            if (!isset($input[$k][$i]))
                $input[$k][$i] = '';
        }
        $output[$k] = [];
        $used[$k] = [];
    }

    $j = 0;
    foreach($input as $key2 => $col2) {
        foreach($col2 as $k => $elem) {

            foreach($input as $key => $col) {
                for($i=0;$i<$h;$i++) {
                    dump("TRYING: $key $i = $elem");
                    if (!in_array($elem, getRow($output, $i)) && !in_array($elem, $used[$key]) && (!isset($output[$key][$i]) || $output[$key][$i] == '')) {

                        if (in_array($elem, $col)) {
                            dump("ok");
                            $output[$key][$i] = $elem;
                            $used[$key][] = $elem;
                            $i = 0;
                            break;
                        }
                    }
                }

            }
        }
    }



    foreach($output as $k => $o) {
        ksort($output[$k]);
    }


    dump($output);
}

one thing I still need help with is to make that script to start searching next array on key when he find last one instead of 0