php中的矩阵排列问题

Question

我想知道解决此类问题的一些方法。

它被赋予一个数字，比如说 16，你必须以这种方式排列一个矩阵

1  2  3  4
12 13 14 5
11 16 15 6
10 9  8  7

，语言无关紧要（最好是 PHP）；

Answer 1

[编辑：更新] 如果语言不重要：

转到：http://rosettacode.org/ wiki/Spiral_matrix

---

在 PHP 中：

在这里：

<?php
function getSpiralArray($n)
{
    $pos = 0;
    $count = $n;
    $value = -$n;
    $sum = -1;

    do
    {
        $value = -1 * $value / $n;
        for ($i = 0; $i < $count; $i++)
        {
            $sum += $value;
            $result[$sum / $n][$sum % $n] = $pos++;
        }
        $value *= $n;
        $count--;
        for ($i = 0; $i < $count; $i++)
        {
            $sum += $value;
            $result[$sum / $n][$sum % $n] = $pos++;
        }
    } while ($count > 0);

    return $result;
}

function PrintArray($array)
{
    for ($i = 0; $i < count($array); $i++) {
        for ($j = 0; $j < count($array); $j++) {
            echo str_pad($array[$i][$j],3,' ');
        }
        echo '<br/>';
    }
}

$arr = getSpiralArray(4);
echo '<pre>';
PrintArray($arr);
echo '</pre>';
?>

Answer 2

在Python中：

from numpy import *

def spiral(N):
    A = zeros((N,N), dtype='int')
    vx, vy = 0, 1 # current direction
    x, y = 0, -1 # current position
    c = 1
    Z = [N] # Z will contain the number of steps forward before changing direction
    for i in range(N-1, 0, -1):
        Z += [i, i]
    for i in range(len(Z)):
        for j in range(Z[i]):
            x += vx
            y += vy
            A[x, y] = c
            c += 1
        vx, vy = vy, -vx
    return A

print spiral(4)  

Answer 3

看来贪吃蛇游戏可能会成功。跟踪方向矢量，每次碰到边或有人居住的方块时，右转 90 度。尾巴一直无限延伸:)

编辑：C# 中的 Snakey v0.1。也适用于非方形网格；）

using System;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        public enum Direction
        {
            Up,
            Down,
            Left,
            Right
        }

        static void Main(string[] args)
        {
            int[,] maze;

            Direction currentDirection = Direction.Right;

            bool totallyStuck = false;
            bool complete = false;
            int currentX = 0;
            int currentY = 0;
            int boundX = 4;
            int boundY = 5;
            int currentNumber = 1;
            int stuckCounter = 0;
            bool placeNumber = true;

            maze = new int[boundY, boundX];

            while ((!totallyStuck) && (!complete))
            {
                if (placeNumber)
                {
                    maze[currentY, currentX] = currentNumber;
                    currentNumber++;
                    stuckCounter = 0;
                }

                switch (currentDirection)
                {
                    case Direction.Right:
                        // Noted short Circuit Bool Evan
                        if ((currentX + 1 < boundX) && (maze[currentY, currentX + 1] == 0))
                        {
                            placeNumber = true;
                            currentX++;
                            stuckCounter = 0;
                        }
                        else
                        {
                            placeNumber = false;
                            stuckCounter++;
                        }

                        break;
                    case Direction.Left:
                        if ((currentX - 1 >= 0) && (maze[currentY, currentX - 1] == 0))
                        {
                            placeNumber = true;
                            currentX--;
                            stuckCounter = 0;
                        }
                        else
                        {
                            placeNumber = false;
                            stuckCounter++;
                        }
                        break;
                    case Direction.Down:
                        if ((currentY + 1 < boundY) && (maze[currentY + 1, currentX] == 0))
                        {
                            placeNumber = true;
                            currentY++;
                            stuckCounter = 0;
                        }
                        else
                        {
                            placeNumber = false;
                            stuckCounter++;
                        }
                        break;
                    case Direction.Up:
                        if ((currentY - 1 >= 0) && (maze[currentY - 1, currentX] == 0))
                        {
                            placeNumber = true;
                            currentY--;
                            stuckCounter = 0;
                        }
                        else
                        {
                            placeNumber = false;
                            stuckCounter++;
                        }
                        break;
                }

                // Is Snake stuck? If so, rotate 90 degs right
                if (stuckCounter == 1)
                {
                    switch (currentDirection)
                    {
                        case Direction.Right:
                            currentDirection = Direction.Down;
                            break;
                        case Direction.Down:
                            currentDirection = Direction.Left;
                            break;
                        case Direction.Left:
                            currentDirection = Direction.Up;
                            break;
                        case Direction.Up:
                            currentDirection = Direction.Right;
                            break;
                    }
                }
                else if (stuckCounter > 1)
                {
                    totallyStuck = true;
                }
            }

            // Draw final maze
            for (int y = 0; y < boundY; y++)
            {
                for (int x = 0; x < boundX; x++)
                {
                    Console.Write(string.Format("{0:00} ",maze[y, x]));
                }
                Console.Write("\r\n");
            }
        }
    }
}

Answer 4

好吧，我只是为了好玩而发布这个答案。

其他解决方案使用变量来迭代地积累信息。我想尝试一种功能解决方案，其中可以知道任何表格单元格的编号（或者任何数字的表格单元格），而无需迭代任何其他单元格。

这是 JavaScript 中的。我知道，这不是纯粹的函数式编程，也不是非常优雅，但是每个表格单元格的数字的计算是在不参考先前迭代的情况下完成的。所以它是多核友好的。

现在我们只需要有人用 haskell 来做这件事。 ;-)

顺便说一句，这是在评论之前写的，即 1 应该最终位于不一定是西北角的某个位置（目前尚未指定）。

由于有人提到了乌拉姆螺旋，只是为了好玩，我添加了代码，在素数周围放置了红色边框（即使螺旋是由内向外的）。有趣的是，似乎确实存在质数的对角条纹，尽管我不知道它是否与随机奇数得到的条纹有显着不同。

代码：

// http://stackoverflow.com/questions/3584557/logical-problem

/* Return a square array initialized to the numbers 1...n2, arranged in a spiral */
function spiralArray(n2) {
   var n = Math.round(Math.sqrt(n2));
   if (n * n != n2) {
      alert('' + n2 + ' is not a square.');
      return 0;
   }
   var h = n / 2;
   var arr = new Array(n);
   var i, j;

   for (i = 0; i < n; i++) {
      arr[i] = new Array(n);
      for (j = 0; j < n; j++) {
         // upper rows and lower rows of spiral already completed
         var ur = Math.min(i, n - i, j + 1, n - j, h),
            lr = Math.min(i, n - i - 1, j + 1, n - j - 1, h);
         // count of cells in completed rows
         // n + n-2 + n-4 ... n - 2*(ur-1) = ur*n - (ur*2*(ur - 1)/2) = ur * (n - ur + 1)
         // n-1 + n-3 + ... n-1 - 2*(lr-1) = lr*(n-1) - (lr*2*(lr - 1)/2) = lr * (n - 1 - lr + 1)
         var compr = ur * (n - ur + 1) + lr * (n - lr);
         // e.g. ur = 2, cr = 2*(5 - 2 + 1) = 2*4 = 8
         // left columns and right columns of spiral already completed
         var rc = Math.min(n - j - 1, i, n - i, j + 1, h),
            lc = Math.min(n - j - 1, i, n - i - 1, j, h);
         // count of cells in completed columns
         var compc = rc * (n - rc) + lc * (n - lc - 1);
         // offset along current row/column
         var offset;
         // Which direction are we going?
         if (ur > rc) {
            // going south
            offset = i - (n - j) + 1;
         } else if (rc > lr) {
            // going west
            offset = i - j;
         } else if (lr > lc) {
            // going north
            offset = n - i - 1 - j;
         } else {
            // going east
            offset = j - i + 1;
         }

         arr[i][j] = compr + compc + offset;
      }
   }
   return arr;
}

function isPrime(n) {
    // no fancy sieve... we're not going to be testing large primes.
    var lim = Math.floor(Math.sqrt(n));
    var i;
    if (n == 2) return true;
    else if (n == 1 || n % 2 == 0) return false;
    for (i = 3; i <= lim; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

// display the given array as a table, with fancy background shading
function writeArray(arr, tableId, m, n) {
   var tableElt = document.getElementById(tableId);
   var s = '<table align="right">';
   var scale = 1 / (m * n);
   var i, j;
   for (i = 0; i < m; i++) {
      s += '<tr>';
      for (j = 0; j < n; j++) {
         var border = isPrime(arr[i][j]) ? "border: solid red 1px;" : "";
         s += '<td style="' + border + '" >' + arr[i][j] + '</td>';
      }
      s += '</tr>';
   }
   s += '</table>';

   tableElt.innerHTML = s;
}

function tryIt(tableId) {
   var sizeElt = document.getElementById('size');
   var size = parseInt(sizeElt.value);
   writeArray(spiralArray(size * size), 'spiral', size, size);
}

练习它的 HTML 页面：

<html>
    <head>
        <style type="text/css">
        td {
            text-align: right;
            font-weight: bold;
        }
        </style>
        <script type="text/javascript" src="so3584557.js" ></script>
    </head>
    <body>
        <form action="javascript:tryIt('spiral')">
            Size of spiral: <input type='text' id='size' />
        </form>
        <table id="spiral">
        </table>
    </body>
</html>

Answer 5

在java中

   public static void main(final String args[]) {
      int numbercnt = 16;
      int dim = (int) Math.sqrt(numbercnt);
      int[][] numbers = new int[dim][dim];
      ArrayList < Integer > ref = new ArrayList < Integer >();
      for (int i = 0; i < numbercnt; i++) {
         ref.add(i);
      }
      for (int i = 0; i < numbers.length; i++) {
         for (int j = 0; j < numbers[i].length; j++) {
            int pos = (int) (Math.random() * ref.size());
            numbers[j][i] = ref.get(pos);
            ref.remove(pos);
         }
      }
      for (int i = 0; i < numbers.length; i++) {
         for (int j = 0; j < numbers[i].length; j++) {
            System.out.print(numbers[j][i] + " ");
         }
         System.out.println();
      }
   }

Answer 6

在 PHP 中，但带有递归。您可以通过指定边长来设置要填充的方框的大小。

其工作方式是函数最初填充指定数组位置的值。然后它尝试继续朝原来的方向移动。如果不能，则顺时针旋转 90 度。如果没有剩余的动作，它就会停止。这是通过 direction 变量和递归的 switch() 语句来处理的。

这可以很容易地适应矩形网格（只需为边长指定 2 个常数而不是 1）。

8x8 的实时示例 和您的4x4

代码：

<?php

  // Size of edge of matrix
define("SIZE", 4);

  // Create empty array
$array = array();

  // Fill array with a spiral.
fillerUp($array);

// Start at 0 / 0  and recurse
function fillerUp(& $array, $x = 0, $y = 0, $count = 1, $direction = "right")
{
      // Insert value
    $array[$x][$y] = $count;

      // Try to insert next value. Stop if matrix is full.
    switch ($direction)
    {

    case "right":        
        if (! $array[($x + 1) % SIZE][$y])
            fillerUp($array, $x + 1, $y, ++$count, "right");
        elseif (! $array[$x][($y + 1) % SIZE])
            fillerUp($array, $x, $y + 1, ++$count, "down");        
        break;

    case "down":  
        if (! $array[$x][($y + 1) % SIZE])
            fillerUp($array, $x, $y + 1, ++$count, "down");
        elseif (! $array[($x - 1) % SIZE][$y])
            fillerUp($array, $x - 1, $y, ++$count, "left");        
        break; 

    case "left":   
        if (! $array[abs(($x - 1) % SIZE)][$y])
            fillerUp($array, $x - 1, $y, ++$count, "left");
        elseif (! $array[$x][abs(($y - 1) % SIZE)])
            fillerUp($array, $x, $y - 1, ++$count, "up");        
        break;

    case "up":                   
        if (! $array[$x][abs(($y - 1) % SIZE)])
            fillerUp($array, $x, $y - 1, ++$count, "up");        
        elseif (! $array[($x + 1) % SIZE][$y])
            fillerUp($array, $x + 1, $y, ++$count, "right");            
        break; 

    }
}

// Show answer.
echo "<pre>";
for ($y = 0; $y < SIZE; ++$y)
{
    for ($x = 0; $x < SIZE; ++$x)    
    {
        echo str_pad($array[$x][$y], 4, " ", STR_PAD_BOTH);
    }
    echo "\n";
}
echo "</pre>";
?>