[PHP] Non-square Matrix Transposition

[TheNephilim]

Na wat klooien kwam Miyamoto in "De Devschuur Coffee Corner - Iteratie 2" met de term Transpose. Dat bleek al heel handig, maar tot zover krijg ik het nog niet voor elkaar. Misschien is mijn situatie anders dan wat je met transpose kan doen, dus vandaar een topic.

Situatie

Voor een website heb ik een menu waarin onder enkele categorieën een submenu zit. Normaal geen probleem, maar nu moeten de sub-items weergegeven worden in drie kolommen. Dat kan prima met float: left;, maar niet als de sortering van boven naar beneden loopt in plaats van links naar rechts.

Normaal:
1 2 3
4 5 6
7 8 9

De bedoeling:
1 4 7
2 5 8
3 6 9

Menu items

Ik werk hier aan een thema voor Wordpress en daar vang ik de menu items af in een array. De volgorde moet overigens juist blijven, anders kan Wordpress er niks mee.

code:

Array (
    0 => Array(Parent),
    1 => Array(Child),
    2 => Array(Child)
)

Ze zitten dus in dezelfde array en worden aan de hand van properties in de array gekoppeld door parent_menu_item.

Mijn insteek

De items met een bepaalde parent uit de array halen en opslaan wat de eerste key is. Dan ga ik de items anders sorteren (transposeren) en dan weer terug in de array waar het allemaal mee begonnen is. Zo verander ik niks fundamenteels, maar van slechts op wat ik moet doen, aanpassen en weer terug.

Eerste poging

Hieronder een poging van mijzelf en een opmerking van EddoH in "De Devschuur Coffee Corner - Iteratie 2" kwam er onderstaande code uit. Deze werkte prima maar ging de mist in met ongelijke rijen. Dus 3x3=9 werkt prima, maar als er op de eerste rij 4 staan en de andere 2 rijen 3 (in het geval van 10 ipv 9 items), dan gaat hij de mist in.

PHP:

    $i=$first;
    $rows = round(count($newItems)/3);
    
    foreach ($newItems AS $key => $newItem) {
        
        echo $i;
        
        $newArray[$i] = $newItem;
        
        if (round($i/$rows) == 3) {
            $i = $first + (($i%$rows)+1);
        } else {
            $i = $i + $rows;
        }

    }
    
    ksort($newArray);

Transpose

Wikipedia: Transpose
http://stackoverflow.com/...ys-in-php/3423692#3423692

Transpose bracht ander licht op de zaak en zo heet blijkbaar het probleem waar ik tegenaan loop. Zeker toen ik het plaatje op Wiki bekeek, wist ik dat dit de oplossing moest zijn. Echter heb ik het idee dat ik het niet begrepen heb, want de output is niet zoals hij hoort te zijn.

Voor zover ik begrepen heb, moet ik de bestaande array opdelen in 3 kolommen zoals te vinden is bij Normaal bovenaan in dit topic. Dan de transpose functie zoals in Stackoverflow. Alleen krijg ik dan weer een driedimensionale Array terug en alles moet in één array, onder elkaar.

Hieronder de code die ik gefabriceerd heb, misschien is er iemand die mij een hint kan geven waar ik heen moet na het transposen?

PHP:

    // Transpose functie
    function transpose($array) {
        array_unshift($array, null);
        return call_user_func_array('array_map', $array);
    }
    
    // Driedimensionale array maken
    foreach ($newItems AS $key => $item) {
        
        $array[$c][$key] = $item;
        
        if ($c == 3) $c=0; else $c++;
        
    }
    
    // Transpose
    $newArray = transpose($array);

    // Items weer in één array onder elkaar.    
    foreach ($newArray AS $column) {

        foreach ($column AS $row) {
            
            $final[] = $row;

        }
    }
    
    foreach ($final AS $key => $value) {
        echo $value->title."<br />";
    }

Helaas krijg ik nu weer 1 t/m 9 terug in plaats van 1 4 7 2 5 8 3 6 9

[P.O. Box]

volgens mij denk je een beetje moeilijk...

je wilt gewoon de rows en de columns omwisselen... dat is dan dus ook wat je moet doen:

code:

$a = array(
array(1,2,3),
array(4,5,6),
array(7,8,9)
);

$result = array();
foreach ($a as $rownr => $row) {
foreach ($row as $colnr => $element) {
$result[$colnr][$rownr] = $element;
}
}

[TheNephilim]

Misschien wel, maar het mooie is, bij 9 items werkt het prima, maar zodra ik er één toevoeg, met dus totaal 10 items, gaat het mis.

Maar bedankt, ik ga eens even kijken of ik in ieder geval een dergelijke uitput krijg zoals je array.

[alex3305]

Dan moet je in de code hierboven ergens een item toevoegen natuurlijk.

[PrisonerOfPain]

PHP:

$array = array();
for($y = 0; $y < 100; $y++)
 for($x = 0; $x < 100; $x++) 
   $array[$x][$y] = $x + $y * 100;
   
// In 2D array is dat het verschil tussen
for($y = 0; $y < 100; $y++)
{
 for($x = 0; $x < 100; $x++) 
   echo $array[$x][$y], ", ";
 echo "<br>";
}
echo "---------------";
// en
for($y = 0; $y < 100; $y++)
{
 for($x = 0; $x < 100; $x++) 
   echo $array[$y][$x], ", ";
 echo "<br>";
}

$w = 100;
$h = 100;
$array = range(0, 100 * 100);
echo "-------------";
// Voor een 1D lineare array is het het verschil tussen
for($y = 0; $y < 100; $y++)
{
 for($x = 0; $x < $w; $x++) 
   echo $array[$x + $y * $w], ", ";
 echo "<br>";
}
echo "-------------";
// en
for($y = 0; $y < $h; $y++){
 for($x = 0; $x < $w; $x++) 
   echo $array[$y + $x * $h], ", ";
 echo "<br>";
}

[TheNephilim]

Klopt, echter was de uitvoer van mijn array anders dan de array waar P.O. Box mee begint.

Maar, met dank aan het schrijven van dit topic (soort van rubber duck debugging) en onder andere P.O. Box is het me dan uiteindelijk toch gelukt.

PHP:

    $selectedItems = array();
    
    // Van alle menu items, alleen de children van een bepaalde parent ophalen
    foreach ($sorted_menu_items AS $key => $item) {
        if ($item->menu_item_parent == 23) {
            $selectedItems[$key] = $item;      
        }
    }

    $r=0;
    $i=0;
    $rowsArray = array();

    // 3 items per array
    foreach ($selectedItems AS $key => $item) {
        
        $rowsArray[$r][] = $item;

        if ($i==2) { $i=0; $r++;} else{ $i++;}
    }
    
    $transposeArray = array();

    // Rows en cols omwisselen (nog steeds Transpose methode toch?)
    foreach ($rowsArray as $rownr => $row) {
        foreach ($row as $colnr => $element) {
            $transposeArray[$colnr][$rownr] = $element;
        }
    }
    
    // De transposed items weer achter elkaar zetten in de juist volgorde.
    foreach ($transposeArray AS $column) {
            $orderedArray[] = $column[0];
    }
    foreach ($transposeArray AS $column) {
            $orderedArray[] = $column[1];
    }
    foreach ($transposeArray AS $column) {
            $orderedArray[] = $column[2];
    }
    
    $i=0;

    // De oude keys weer terug zetten, zodat ze weer op de juiste plek staan
    foreach ($selectedItems AS $key => $value) {
        $finalArray[$key] = $orderedArray[$i];
        $i++;
    }
    
    // De oude items met de nieuwe overschrijven
    $sorted_menu_items = array_merge_overwrite($sorted_menu_items, $finalArray);

Mijn eigen eerste functie voor het maken van die eerste cruciale array deed:

1 4 7
2 5 8
3 6 9

Maar dat doen we later met het transpose gebeuren.

Code heb ik nog niet echt opgeruimd hoor, dingen kunnen vast efficiënter en dergelijke, werkend krijgen is in ieder geval gelukt! ^^

Dank allemaal!

Edit: Nevermind, het is nog steeds niet goed... ik zit weer niet goed te kijken

[Chip.]

Ik zou eens kijken naar, Wikipedia: In-place matrix transposition

[TheNephilim]

Wouser schreef op woensdag 24 oktober 2012 @ 15:38:
Ik zou eens kijken naar, Wikipedia: In-place matrix transposition

Thanks!

Reeds voorgestelde functies (ook die bij Stackoverflow) zijn allen voor Square matrices in plaats van non-Square matrices. Tenminste dat idee heb ik nu.

Bij 9 items gaat het namelijk goed terwijl hij bij 11 compleet in de soep loopt en de laatste 2 items ergens middenin plaatst. Even zien of ik het voorbeeld van wiki (pseudocode) kan gebruiken om wat te maken.

Overigens was mijn loop die ze achter elkaar zet de boosdoener wat betreft de volgorde verkeerd. Het volgende werkt wel:

PHP:

    foreach ($transposeArray AS $rows) {
        foreach ($rows AS $row) {
            $orderedArray[] = $row;
        }
    }

[ Voor 17% gewijzigd door TheNephilim op 24-10-2012 15:57 ]

[P.O. Box]

geef eens een voorbeeld van een input en gewenste output bij een 11 item voorbeeld

[TheNephilim]

Wat betreft pseudo code (van http://stackoverflow.com/...-non-square-matrix-in-c):

PHP:

$array = Array
(
    [0] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 3
        )

    [1] => Array
        (
            [0] => 4
            [1] => 5
            [2] => 6
        )

    [2] => Array
        (
            [0] => 7
            [1] => 8
            [2] => 9
        )

    [3] => Array
        (
            [0] => 10
            [1] => 11
            [2] => 12
        )

);

function transpose($array) {
    
    define('COLS', 3);
    define('ROWS', 4);

    $newArray = array();

    $i = 0;
    $j = 0;

    for ($i=0; $i < COLS; $i++) {
        for ($j = 0; $j < ROWS; $j++) {
            $newArray[$j][$i] = $array[$i][$j];
        }
    }
    
    return $newArray;
}

Hierbij moet ik wel weten hoeveel cols/rows er zijn, maar dat is uit te rekenen. Volgens mij doet hij het, even verder spieken

P.O. Box schreef op woensdag 24 oktober 2012 @ 16:08:
geef eens een voorbeeld van een input en gewenste output bij een 11 item voorbeeld

Ehm, das een lastige... dat komt sowieso raar uit, maar voorlopig:

1 4 7
2 5 8
3 6 9
10 11

Eigenlijk moet links van die 10 een wit ruimte, maar dat is dan weer punt 2

Edit, uitvoer pseudo code

Helaas is de uitvoer van de pseudo code niet zoals hij zijn moet:

1 4 7
2 5 8
3 6 9
10 11 12

Terwijl dat moet zijn:

1 5 9
2 6 10
3 7 11
4 8 12

Edit, oplossing!

PHP:

    $rowsArray = array();
    $r=0;
    $i=0;
    $j=1;
    foreach ($selectedItems AS $key => $item) {
        
        $rowsArray[$r][] = $item;

        if ($i==2) { $i=0; $r++;} else{ $i++;}
        
        $j++;
    }

Moet eigenlijk zijn:

PHP:

    $rowsArray = array();
    $r=0;
    $i=0;
    $j=1;
    foreach ($selectedItems AS $key => $item) {
        
        $rowsArray[$r][] = $item;

        if ($i==ceil(count($selectedItems)/3)-1) { $i=0; $r++;} else{ $i++;}
        
        $j++;
    }

Nu krijg ik netjes de gewenste uitvoer bij 12 items. Zou het dan eindelijk gelukt zijn? Ik ga eerst nog eens even klooien, want ik verwacht weer gekke dingen bij 11 items

Edit 3: Ook bij 11 items de gewenste uitvoer! Er mist er dan 1 op de laatste rij in de laatste kolom! ^^

@PrisonerOfPain: Sorry, hier kan ik niet heel wijs uit worden Maar als ik het goed begrijp schets je hier de verschillen tussen 2d en 1d met betrekking tot transposition? Je code lijkt in ieder geval op de C code van Stackoverflow

[ Voor 54% gewijzigd door TheNephilim op 24-10-2012 16:52 ]

[GateKeaper]

In javascript kom ik op zoiets:

JavaScript:

var l = [1,2,3,4,5,6,7,8,9,10,11];
var count = l.length;
var cols = 3;
var rows = Math.ceil(count/cols);

var k = new Array();

for(var i = 0; i < l.length; i++) {
  var col = Math.floor(i/rows);
  if(typeof k[col] == 'undefined')
     k[col] = new Array();

  k[col][$i-(col*rows)] = l[i];
}
console.log(k);

*edit, maar ik zie net dat je er al uit bent, met een vergelijkbare oplossing.

vertaald naar php zou dat zoiets worden (ook wat logischere namen gekozen ).
(DISCLAIMER, php is alweer een tijdje geleden, en dit is even snel in notepad++, dus niet getest!)

PHP:

function Transpose($array, $columnCount) {

    $rowCount = ceil(count($array)/$columnCount);

    $T = array();

    for($i = 0; $i < count($array); $i++) {
      $columnNr = floor($i/$rowCount);
      if(!is_array($T[$columnNr]))
         $T[$columnNr] = array();

      $T[$columnNr][$i-($columnNr*$rowCount)] = $array[$i];
    }
    
    return $T;
}

$array = array('1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11');
$T = Transpose($array, 3);

[ Voor 52% gewijzigd door GateKeaper op 24-10-2012 17:39 . Reden: bugfix, php kent geen var :X ]

[TheNephilim]

GateKeaper schreef op woensdag 24 oktober 2012 @ 16:52:
In javascript kom ik op zoiets:
...

code:

Array[3]
0: Array[4]
0: 1
1: 2
2: 3
3: 4
1: Array[4]
0: 5
1: 6
2: 7
3: 8
2: Array[3]
0: 9
1: 10
2: 11

Nice, doet het inderdaad ook op de juiste manier! ^^ Ik had uiteraard ook aan de buitenkant de li's met JavaScript kunnen orderen, maar wil het toch liever aan de server kant doen.

[ Voor 58% gewijzigd door TheNephilim op 24-10-2012 16:59 ]

[GateKeaper]

TheNephilim schreef op woensdag 24 oktober 2012 @ 16:57:
[...]

Nice, doet het inderdaad ook op de juiste manier! ^^ Ik had uiteraard ook aan de buitenkant de li's met JavaScript kunnen orderen, maar wil het toch liever aan de server kant doen.

Snap ik, maar javascript kan ik hier in firebug nog controleren, php niet Ik acht je zelf wel in staat om het naar php te vertalen.

[TheNephilim]

GateKeaper schreef op woensdag 24 oktober 2012 @ 17:00:
[...]


Snap ik, maar javascript kan ik hier in firebug nog controleren, php niet Ik acht je zelf wel in staat om het naar php te vertalen.

Ah oké, thanks! ^^

Had het al voor elkaar met het voorbeeld uit C. Hieronder nog even de relevante code stukken voor mensen die dit topic later tegenkomen:

PHP:

// Array met gesorteerde datum bijv. A, B, C of zoals hieronder
$selectedItems = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11);

$r=0;
$i=0;
$rowsArray = array();

// Items opdelen in rijen terwijl we uitgaan van 3 kolommen
foreach ($selectedItems AS $key => $item) {

    $rowsArray[$r][] = $item;

    if ($i==ceil(count($selectedItems)/3)-1) { $i=0; $r++;} else{ $i++;}
}

// Rijen omwisselen met kolommen (functie in codeblok hieronder)
$transposedArray = transpose($rowsArray, array('cols' => 3, 'rows' => ceil(count($selectedItems)/3)));

PHP:

function transpose($array, $args = array()) {

    $i = 0;
    $j = 0;
    $newArray = array();

    for ($i=0; $i < $args['cols']; $i++) {
        for ($j = 0; $j < $args['rows']; $j++) {
            $newArray[$j][$i] = $array[$i][$j];
        }
    }
    
    return $newArray;
}

[ Voor 3% gewijzigd door TheNephilim op 24-10-2012 17:16 ]

[GateKeaper]

offtopic:
Kan je het aantal rijen niet beter binnen je functie bepalen?

[ Voor 9% gewijzigd door GateKeaper op 24-10-2012 17:17 ]

[TheNephilim]

GateKeaper schreef op woensdag 24 oktober 2012 @ 17:15:
Kan je het aantal rijen niet beter binnen je functie bepalen?

Nou dit hele gebeuren is een filter callback functie voor wp_nav_menu_objects binnen Wordpress. Dus er zit nog links en rechts omheen. Behalve is de callback voor dat filter gewoon een functie en geen classes of iets dergelijks. Wat wel beter is, om het die in plaats van 2 counts gewoon even een variabele aan te maken met daarin het totaal aantal rijen. Ga ik eens even regelen, thanks!

[GateKeaper]

Maar zie ik het nu goed dat je één lange array (lijst) eerst opdeelt in (3) rijen, en dan die rijen omzet naar kolommen?

Dat lijkt me nogal een omweg? Mijn functie doet dat in 1x , zodat je maar 1 for loopt hebt, ipv 3. Je zou mijn functie dus ipv "Transpose" ook "Divide" kunnen noemen .

Tenzij je natuurlijk van WordPress al die rijen krijgt aangeleverd.

*edit, sterker nog... mijn functie is al geen Transpose meer.

[ Voor 18% gewijzigd door GateKeaper op 24-10-2012 17:28 ]

[TheNephilim]

GateKeaper schreef op woensdag 24 oktober 2012 @ 17:25:
Maar zie ik het nu goed dat je één lange array (lijst) eerst opdeelt in (3) rijen, en dan die rijen omzet naar kolommen?

Dat lijkt me nogal een omweg? Mijn functie doet dat in 1x , zodat je maar 1 for loopt hebt, ipv 3. Je zou mijn functie dus ipv "Transpose" ook "Divide" kunnen noemen .

Tenzij je natuurlijk van WordPress al die rijen krijgt aangeleverd.

Nee, van lijst naar 3 kolommen -> transposeren -> terug naar lijst.

Maar nice, daar heb ik niet aan gedacht Het kan dus nog efficiënter! Even kijken of het nog lukt om die aanpassing te maken, moet even zien wat ik nog moet doen voor ik naar huus ga

[GateKeaper]

Hah... codepad vergeten ,

1 lange lijst -> X kolommen

http://codepad.org/4C7vCRF6

PHP:

function Divide($array, $columnCount) {

    $rowCount = ceil(count($array)/$columnCount);

    $T = array();

    for($i = 0; $i < count($array); $i++) {
      $columnNr = floor($i/$rowCount);
      if(!is_array($T[$columnNr]))
         $T[$columnNr] = array();

      $T[$columnNr][$i-($columnNr*$rowCount)] = $array[$i];
    }
    
    return $T;
}

[ Voor 3% gewijzigd door GateKeaper op 24-10-2012 17:38 ]

[TheNephilim]

Maar ik moest 1 5 9 2 6 10 3 7 11 4 8 hebben en niet 1 2 3 4 5 6 7 8 9 10 11

[GateKeaper]

Aaah joh... Details.

In 1x dan, lijst => lijst.

http://codepad.org/PzBYIynA

PHP:

<?php
function ToColumns($array, $columnCount) {

    $rowCount = ceil(count($array)/$columnCount);

    $T = array();

    for($i = 0; $i < count($array); $i++) {
      $columnNr = $i % $columnCount;
      $index = floor($i/$columnCount)+$columnNr+($columnNr*$columnCount);

      $T[$index+1] = $array[$i];
    }

    return $T;
}

Test

PHP:

$array = array('1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11');
$T = ToColumns($array, 3);

foreach($T as $key => $val) {
   echo $key . ' ';
}

Output

code:

1 5 9 2 6 10 3 7 11 4 8

[ Voor 23% gewijzigd door GateKeaper op 24-10-2012 18:39 ]

[TheNephilim]

Haha nice! ^^ Zodra ik weer verder ga met het menu'tje zal ik dit eens even gaan aanpassen! Thnx!