PHP无法为任意长度的二维数组编写重新排序函数

Question

Broadly speaking, I have a 2-dimensional array of the following format:

$elements = array(  0 => array('typeA', 'desc'),
                    1 => array('typeB', 'desc'),
                    2 => array('typeA', 'desc'),
                    n => array('typeC', 'desc'));

Where typeX can be 1 of 5 possibilities, and desc can be anything. The end goal is $elements sorted such that no two elements who share a typeX are ever adjacent. Here's my function:

function fixDbls($elems) {
    $final   = array();
    $singles = array();
    $doubles = array();
    $lastelem = null;
    foreach($elems as $elem) {
        if(!$lastelem) { // set this the first time through
            $lastelem = $elem[0];
            $singles[] = $elem;
        } else { //otherwise, sort!
            if($lastelem == $elem[0]) {
                $doubles[] = $elem;
            } else {
                $singles[] = $elem;
            }
        }
    }

    if ($doubles) {
            // I suspect this is where it all goes wrong, I am awful at recursion!
        $final = fixDbls(array_merge($singles, $doubles));
    } else {
        $final = $singles;
    }

    return $final;
}

If anyone can help me understand why this doesn't work (not just the code, but, where I've made a false assumption or where my thinking about this problem betrayed me—helps makes this more generally useful to the public!) I'd be ever, ever so appreciative.

Answer 1

I've been thinking your problem over and I think I came up with a solution. Here's the

code:

<?php

function print_array( $s, $a )
{
    echo $s.': { ';
    foreach ( $a as $k => $aa ) {
        echo $k.' => ';
        if ( is_array($aa) ) {
            echo '{ '.implode( ', ', $aa ).' }, ';
        } else {
            echo $aa.', ';
        }
    }
    echo '}'.PHP_EOL;
}

function search_array( array $a, $k )
{
    $found = false;
    foreach ( $a as $kk => $aa ) {
        if ( $aa[0] == $k ) {
            $found = $kk;
            break;
        }
    }

    return $found;
}

$input = array(  
        array('typeA', 'desc'),
            array('typeB', 'desc'),
                array('typeA', 'desc'),
                array('typeC', 'desc')
);

print_array( 'Initial input', $input );
$frequencies = array();

foreach ( $input as $e ) {
    $frequencies[ $e[0] ] = array_key_exists( $e[0], $frequencies ) ? $frequencies[ $e[0] ] + 1 : 1;
}

arsort($frequencies);

print_array( 'Frequencies', $frequencies );
$tail = array_slice( $frequencies, 1 );
$maxFreq = current( $frequencies ); 
$orderedElems = array_keys( $frequencies );
$mostFreq = current( $orderedElems );

echo 'The most frecuent element is "'.$mostFreq.'"'.PHP_EOL;

if ( array_sum( $tail ) < $maxFreq - 1 ) {
    die ('There\'s No possible solution'.PHP_EOL);
}

$ouput = array();

for ( $i = 0; $i < $maxFreq; $i++ ) {
    $k = search_array( $input, $mostFreq);
    $output[] = $input[ $k ];
    unset( $input[ $k ] );
}

print_array( 'Input after removing "'.$mostFreq.'"', $input );

echo '-----'.PHP_EOL;
print_array( 'Before process, output', $output );

foreach ( $tail as $e => $f ) {
    $i = 1;
    echo 'Elem to place: "'.$e.'" ('.$f.' times)'.PHP_EOL;
    while ( ( $k = search_array( $input, $e ) ) !== false ) {
        echo '$i: '.$i.PHP_EOL;
        $begin = array_slice( $output, 0, $i );
        print_array( 'Begin', $begin );
        $end = array_slice( $output, $i );
        print_array( 'End', $end );
        $output = array_merge( $begin, array( $input[$k] ), $end );
        print_array( 'Output', $output );
        $i+=2;
        unset( $input[$k] );
        echo PHP_EOL;
    }
}

print_array( 'Final output', $output );

This time I just tried the example you put in the question. The end result was:

Final output: { 0 => { typeA, desc }, 1 => { typeB, desc }, 2 => { typeC, desc }, 3 => { typeA, desc }, }

I hope this version suits your needs.