php array generation challange

Question

Necesito generar aleatoriamente una matriz bidimensional n por n. En este ejemplo, n = 10. La matriz debe tener esta estructura. Un ejemplo:

$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.................... 

donde

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

como lo ve como una matriz de números de cada fila y columna también constan de números 0-9, y nunca hay un número dos veces en cada fila o en cada columna. cómo generar dicha matriz, y cada vez al azar.

Answer 1

bien, así que aquí está mi versión:

$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; 

Esto debería ser un algoritmo muy rápido, ya que sólo implica la generación de dos matrices aleatorias y no implica ningún intercambio en absoluto. Debería ser aleatorio, también, pero no puedo probarlo. (Por lo menos yo no sé cómo probar algo como esto.)

Ésta es una versión optimizada de un algoritmo muy simple:

En primer lugar una matriz no aleatoria se crea de esta manera (imagina que sólo queremos 5 * 5, no 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 

En esta matriz que ahora cambiamos azar columnas. Como no cambiamos las columnas, sus reglas todavía se obedecen. Luego cambiamos aleatoriamente las filas.

Ahora, como puede ver, el algoritmo anterior no intercambia nada y tampoco genera la matriz anterior. Esto se debe a que genera las columnas y filas para intercambiar por adelantado ($v1 y $v2) y luego escribe directamente en la posición correcta en la matriz resultante.

Edit: Acabo de hacer algunos benchmarking: Para $n = 500 se necesitan 0,3 segundos.

Edit2: Después de reemplazar los bucles for con bucles foreach solo toma 0.2 segundos.

Answer 2

Esto es lo que hice. Hizo una matriz válida (2d array) que no es aleatoria. Entonces, comenzando, la fila 0 es 0-9, la fila 1 es 1-0 (es decir: 1,2,3 ... 8,9,0), la fila 2 es 2-1 (2,3 ... 9, 0,1) ... la fila 8 es 8-7 ... etc. Luego baraja esa matriz para aleatorizar las filas y realiza un simple intercambio de columnas para aleatorizar las columnas. Debe volver exactamente lo que quiere. Prueba esto:

<?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); 
?> 

En mi solución, al no generar una matriz aleatoria y comprobar si ya existe, se debe ejecutar mucho más rápido (sobre todo si el conjunto siempre fue por encima 0-9). Cuando llega a la última fila, solo hay una combinación posible de números. Generará matrices aleatorias tratando de encontrar esa respuesta. Sería más o menos lo mismo que elegir un número del 1 al 10 y generar un número aleatorio hasta que llegue al que elegiste. Podría ser en el primer intento, pero de nuevo podrías elegir 1000 números aleatorios y nunca obtener el que querías.

Answer 3

Hmm .. Veo que tienes algunas buenas respuestas ya, pero aquí está mi versión:

$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"; 
} 

muestra de salida:

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 

Se crea una matriz aleatoria al azar como punto partida Entonces recorre el conjunto de semillas tomando cada elemento como punto de partida para crear una nueva base.