Find all the possible combinations of array elements with two attributes where neither repeats

Question

I have two arrays:

$colors = [ 'gold', 'silver', 'bronze', 'wood' ];
$emotion = [ 'happy', 'sad', 'wow', 'angry' ];

Out of those, I can make up 16 elements, so that colors and emotion don't repeat. I can easily generate all the unique elements by nesting 2 foreach loops.

$items = array();

foreach ( $colors as $c ) {
    foreach( $emotion as $e ) {
        $items[] = array( $c => $e );
    }
}

The problem is that I need to create a 4x4 grid out of those 16 elements so that every column and every row contains only 1 element with particular color AND emotion.

To further explain, one row, of 4 elements( from the $items array ), can only contain one element of each emotion and color. It can not have colors nor emotions repeat in a row. The same goes for column.

What would be the proper way to do it? I'm pretty sure I need some condition checks and recursion, but not sure how to do it.

EDIT: Add example output

As for the output, it should be an array of four arrays, 4 elements in each, like so:

array(4) {
  [0]=>
  array(4) {
    ["bronze"]=>
    string(5) "angry"
    ["gold"]=>
    string(3) "happy"
    ["silver"]=>
    string(3) "sad"
    ["wood"]=>
    string(5) "wow"
  }
  [1]=>
  array(4) {
    ["gold"]=>
    string(5) "happy"
    ["bronze"]=>
    string(3) "wow"
    ["wood"]=>
    string(5) "angry"
    ["silver"]=>
    string(3) "sad"
  }
  [2]=>
  array(4) {
    ["silver"]=>
    string(5) "happy"
    ["wood"]=>
    string(3) "sad"
    ["bronze"]=>
    string(5) "angry"
    ["gold"]=>
    string(3) "wow"
  }
  [3]=>
  array(4) {
    ["wood"]=>
    string(5) "happy"
    ["silver"]=>
    string(3) "wow"
    ["gold"]=>
    string(5) "angry"
    ["bronze"]=>
    string(3) "sad"
  }
}

Here's a( one of ) solution:

bronze->angry   |  gold->happy      |  silver->sad      |  wood->wow        
gold->sad       |  bronze->wow      |  wood->angry      |  silver->happy
silver->wow     |  wood->sad        |  bronze->happy    |  gold->angry  
wood->happy     |  silver->angry    |  gold->wow        |  bronze->sad

    

Answer 1

• Ok, so you need to first collect all possible pairs as you did.
• Now, we will try to place a pair at a location if no collision in the grid and check with other pairs.
• If the current placement fails, we try another location and so on and so forth.

(Scroll to the end to check with a working demo if you would like to see this in action first)

generateGrid:

<?php

function generateGrid($colors, $emotions, &$grid){
    $combs = [];
    foreach($colors as $color){
        foreach($emotions as $emotion){
            $combs[] = [$color, $emotion];
        }
    }

    /* initialize grid */
    for($i = 0; $i < count($colors); ++$i){
        for($j = 0; $j < count($emotions); ++$j){
            $grid[ $i ][ $j ] = [];
        }
    }
    /* initializing grid ends */

    if(makeGrid($combs, $grid, 0, count($colors) * count($emotions))){
        return true;
    }

    $grid = [];// restore the grid to original state
    return false;
}

makeGrid:

<?php

function makeGrid($combs, &$grid, $idx, $total){
    if($idx == $total) return true;

    for($i = 0; $i < count($grid); ++$i){
        for($j = 0; $j < count($grid[ $i ]); ++$j){
            if(count($grid[ $i ][ $j ]) == 0){
                if(noCollision($combs[ $idx ], $i, $j, $grid)){
                    $grid[ $i ][ $j ] = $combs[ $idx ];
                    if(makeGrid($combs, $grid, $idx + 1, $total)){
                        return true;
                    }
                    $grid[ $i ][ $j ] = [];
                }               
            }
        }
    }

    return false;
}

noCollision check method:

<?php

function noCollision($element, $row, $col, $grid){
    $rowSet = [];
    for($i = 0; $i < count($grid[ $row ]); ++$i){
        if(count( $grid[ $row ][ $i ]) > 0){
            $rowSet[$grid[ $row ][ $i ][ 0 ]] = true;
            $rowSet[$grid[ $row ][ $i ][ 1 ]] = true;
        }
    }

    if(isset($rowSet[ $element[0] ]) || isset($rowSet[ $element[1] ])){
        return false;
    }

    $colSet = [];
    for($i = 0; $i < count($grid); ++$i){
        if(count( $grid[ $i ][ $col ]) > 0){
            $colSet[$grid[ $i ][ $col ][ 0 ]] = true;
            $colSet[$grid[ $i ][ $col ][ 1 ]] = true;
        }
    }

    return !(isset($colSet[ $element[0] ]) || isset($colSet[ $element[1] ]));
}

Driver code:

<?php

$grid = [];

if(generateGrid([ 'gold', 'silver', 'bronze', 'wood' ], [ 'happy', 'sad', 'wow', 'angry'], $grid)){
    printGrid($grid);
}else{
    throw new \Exception("No solution found!!");// or whatever you would like to have here
}

Online Demo

Code Demo to print all combinations