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

    

CodePudding user response：

We can design an algorithm but your exercise is to write it in PHP. grid(y,x) takes columns y and rows x that holds y in place and "rotates" x one-by-one -

Immutable rotate(a,i) of some array a and index i takes elements up to the index and puts them on the end of the array.

We'll show the implementation in JS because it's easy to demonstrate in the browser and verify the result -

const grid = (y, x) =>
  y.length > x.length // Note below
    ? grid(x, y)
    : x.map((_, i) => Object.fromEntries(zip(y, rotate(x, i))))

const zip = (a, b) =>
  a.length && b.length
    ? [[a[0], b[0]], ...zip(a.slice(1), b.slice(1))]
    : []

const rotate = (a, i) =>
  a.length < 2
    ? a
    : [ ...a.slice(i), ...a.slice(0, i) ]

const colors = [ 'gold', 'silver', 'bronze', 'wood' ]
const emotions = [ 'smile', 'sad', 'wow', 'angry' ]
    
console.log(JSON.stringify(grid(colors, emotions)))
console.table(grid(colors,emotions))

Object.fromEntries is the JS equivalent of (object) [ "key" => "value", ... ] in PHP.

Open your console to view the console.table output -

Note, for non-square grids, x must be the longer array, otherwise grid(y,x) will calculate grid(x,y). Can you reason why this is the case?

CodePudding user response：

• 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