php array generation challange

Question

Ho bisogno di generare in modo casuale un array bidimensionale n per n. In questo esempio, n = 10. L'array dovrebbe avere questa struttura. Un esempio:

$igra[]=array(0,1,2,3,4,5,6,7,8,9); 
$igra[]=array(6,9,1,5,0,2,7,3,4,8); 
$igra[]=array(2,5.................... 
$igra[]=array(1,7..................... 
$igra[]=array(5,4................... 
$igra[]=array(4,2................... 
$igra[]=array(9,0..................... 
$igra[]=array(8,3..................... 
$igra[]=array(7,6.................... 
$igra[]=array(3,8.................... 

dove

`$igra[x][z]!=$igra[y][z]` (x={0,9},y={0,9}); 

come si vede come una matrice di numeri ciascuna fila di esso e colonna consiste anche dai numeri 0-9, e non c'è mai un numero due volte in ogni riga o in ogni colonna. come generare una tale matrice, e ogni volta in modo casuale.

Answer 1

Va bene, ecco la mia versione:

$n = 10; 

$v1 = range(0, $n-1); 
$v2 = range(0, $n-1); 
shuffle($v1); 
shuffle($v2); 

foreach ($v1 as $x => $value) 
    foreach ($v2 as $y) 
     $array[$y][$x] = $value++ % $n; 

Questo dovrebbe essere un algoritmo molto veloce, perché si tratta di generare solo due matrici casuali e non comporta alcun scambio a tutti. Dovrebbe essere anche casuale, ma non posso provarlo. (Almeno io non so come dimostrare qualcosa di simile.)

Questa è una versione ottimizzata di un algoritmo molto semplice:

Prima una matrice non casuale è creato in questo modo (immaginate vogliamo solo 5 * 5, non 10 * 10):

0 1 2 3 4 
1 2 3 4 0 
2 3 4 0 1 
3 4 0 1 2 
4 0 1 2 3 

In questa matrice ora scambiamo le colonne casualmente. Poiché non cambiamo le colonne, le tue regole vengono ancora rispettate. Quindi scambiamo a caso le righe.

Ora, come si può vedere l'algoritmo di cui sopra non scambia nulla e non genera neanche la matrice sopra. Questo perché genera cols e righe da scambiare in anticipo ($v1 e $v2) e quindi scrive direttamente nella posizione corretta nell'array risultante.

Modifica: Ho appena fatto un benchmarking: per $n = 500 ci vogliono 0,3 secondi.

Edit2: Dopo aver sostituito i cicli for con cicli foreach ci vogliono solo 0,2 secondi.

Answer 2

Questo è quello che ho fatto. Crea una matrice valida (array 2d) che non è casuale. Quindi partendo, la riga 0 è 0-9, la riga 1 è 1-0 (cioè: 1,2,3 ... 8,9,0), la riga 2 è 2-1 (2,3 ... 9, 0,1) ... la riga 8 è 8-7 ... ecc. Quindi mescola quell'array per randomizzare le righe ed eseguire un semplice scambio di colonne per rendere casuali le colonne. Dovrebbe tornare esattamente quello che vuoi. Prova questo:

<?php 
//simple function to show the matrix in a table. 
function show($matrix){ 
    echo '<table border=1 cellspacing=0 cellpadding=5 style="float: left; margin-right:20px;">'; 
    foreach($matrix as $m){ 
     echo '<tr>'; 
     foreach($m as $n){ 
      echo '<td>'.$n.'</td>'; 
     } 
     echo '</tr>'; 
    } 
    echo '</table>'; 
} 

//empty array to store the matrix 
$matrix = array(); 

//this is what keeps the current number to put into matrix 
$cnt = 0; 

//create the simple matrix 
for($i=0;$i<=9;$i++){ 
    for($j=0;$j<=9;$j++){ 
     $matrix[$i][$j] = $cnt % 10; 
     $cnt++; 
    } 
    $cnt++; 
} 

//display valid simple matrix 
show($matrix); 

//shuffle the rows in matrix to make it random 
shuffle($matrix); 

//display matrix with shuffled rows. 
show($matrix); 

//swap the columns in matrix to make it more random. 
for($i=0;$i<=9;$i++){ 
    //pick a random column 
    $r = mt_rand(0, 9); 
    //now loop through each row and swap the columns $i with $r 
    for($j=0;$j<=9;$j++){ 
     //store the old column value in another var 
     $old = $matrix[$j][$i]; 
     //swap the column on this row with the random one 
     $matrix[$j][$i] = $matrix[$j][$r]; 
     $matrix[$j][$r] = $old; 
    } 
} 

//display final matrix with random rows and cols 
show($matrix); 
?> 

Nella mia soluzione, non genera una matrice casuale e controllare se esiste già, dovrebbe funzionare molto più veloce (soprattutto se la matrice mai andato sopra 0-9). Quando arrivi all'ultima riga, c'è solo una possibile combinazione di numeri. Genererai array casuali cercando di trovare quella risposta. Sarebbe più o meno lo stesso di scegliere un numero da 1 a 10 e generare un numero casuale fino a quando non colpisce quello che hai scelto. Potrebbe essere al primo tentativo, ma poi potresti scegliere 1000 numeri casuali e non ottenere mai quello che volevi.

Answer 3

Hmm .. vedo che hai già alcune buone risposte, ma ecco la mia versione:

$n = 10; 

$seed_row = range(0, $n - 1); 
shuffle($seed_row); 

$result = array(); 
for($x = 0; $x < $n; $x++) 
{ 
    $tmp_ar = array(); 
    $rnd_start = $seed_row[$x]; 
    for($y = $rnd_start; $y < ($n + $rnd_start); $y++) 
    { 
     if($y >= $n) $idx = $y - $n; 
     else $idx = $y; 
     $tmp_ar[] = $seed_row[$idx]; 
    } 
    $result[] = $tmp_ar; 
} 

for($x = 0; $x < $n; $x++) 
{ 
    echo implode(', ', $result[$x]) . "<br/>\n"; 
} 

campione di uscita:

4, 3, 0, 2, 6, 5, 7, 1, 8, 9 
0, 2, 6, 5, 7, 1, 8, 9, 4, 3 
7, 1, 8, 9, 4, 3, 0, 2, 6, 5 
2, 6, 5, 7, 1, 8, 9, 4, 3, 0 
6, 5, 7, 1, 8, 9, 4, 3, 0, 2 
9, 4, 3, 0, 2, 6, 5, 7, 1, 8 
8, 9, 4, 3, 0, 2, 6, 5, 7, 1 
5, 7, 1, 8, 9, 4, 3, 0, 2, 6 
1, 8, 9, 4, 3, 0, 2, 6, 5, 7 
3, 0, 2, 6, 5, 7, 1, 8, 9, 4 

Si crea una matrice random random come punto di partenza Poi attraversa l'array seme prendendo ogni elemento come punto di partenza per se stesso per creare una nuova base.