php 数组生成挑战

Question

我需要随机生成一个二维 n × n 数组。在此示例中，n = 10。数组应具有此结构。举个例子：

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

正如

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

你所看到的，它就像一个数字矩阵，每一行和每一列也由数字 0-9 组成，并且每行或每列中永远不会有一个数字出现两次。 如何生成这样的数组，并且每次都是随机的。

Answer 1

好的，这是我的版本：

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

这应该是一个非常快的算法，因为它只涉及生成两个随机数组，并且根本不涉及任何交换。它也应该是随机的，但我无法证明这一点。 （至少我不知道如何证明这样的事情。）

这是一个非常简单算法的优化版本：

首先以这种方式创建一个非随机矩阵（想象一下我们只需要 5*5，而不是 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

在这个矩阵中，我们现在随机交换列。由于我们不更改列本身，因此您的规则仍然得到遵守。然后我们随机交换行。

现在，如您所见，上述算法不会交换任何内容，也不会生成上述矩阵。这是因为它预先生成要交换的列和行（$v1 和 $v2），然后直接写入结果数组中的正确位置。

编辑：刚刚做了一些基准测试：对于 $n = 500 需要 0.3 秒。

Edit2：用 foreach 循环替换 for 循环后，只需要 0.2 秒。

Answer 2

这就是我所做的。制作了一个非随机的有效矩阵（二维数组）。所以开始时，第 0 行是 0-9，第 1 行是 1-0（即：1,2,3...8,9,0），第 2 行是 2-1（2,3...9， 0,1)...第 8 行是 8-7...等。然后打乱该数组以随机化行，并执行简单的列交换以随机化列。应该准确地返回你想要的内容。试试这个：

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

在我的解决方案中，通过不生成随机数组并检查它是否已经存在，它应该运行得更快（特别是如果数组超过 0-9）。当你走到最后一行时，只有一种可能的数字组合。您将生成随机数组并尝试找到该答案。这与从 1 到 10 中选择一个数字并生成一个随机数直到它达到您选择的数字几乎相同。第一次尝试可能会出现这种情况，但您也可能会随机选择 1000 个数字，但永远不会得到您想要的数字。

Answer 3

嗯..我看到你已经得到了一些很好的答案，但这是我的版本：

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

示例输出：

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

它创建一个随机随机数组作为起点
然后它遍历种子数组，以每个元素作为自身的起点来创建新的基础。