Geek Answers Handbook

Get the diagonal values ​​of the spiral matrix

I have a n * n spiral matrix.

if N = 4

then the matrix:

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

if N = 3

  7 8 9 6 1 2 5 4 3

I want to get the diagonal values ​​of this spiral matrix.

In the case n=4 diagonal values ​​will be 7,1,3,13,10,2,4,16

I can do this by storing this matrix in an array and going through each diagonal value. Is there a better way to get these values.

+6
source share
3 answers

To get the numbers on the main diagonal, we can notice that the values

 1 = 1 1 + 2 = 3 1 + 2 + 4 = 7 1 + 2 + 4 + 6 = 13

Thus, the general formula is 1 + (the sum i = 0 to k from 2 * i) for k = 0, 1, 2, ... Simplifying this, we get k ^ 2 + k + 1 for k = 0, 1, 2, ...

In PHP, we can generate them through something like this:

 function mainDiagonal($n) { $values = array(); for ($k = 0; $k < $n; $k++) { $values[] = $k*$k + $k + 1; } return $values; }

To get the numbers on the anti-diagonal for even N, we get:

 2 = 2 2 + 2 = 4 2 + 2 + 6 = 10 2 + 2 + 6 + 6 = 16

If we continue this pattern for large matrices, we will see that the general formula

amount i = 0 to k floor (i / 2) * 4 + 2 for k = 0, 1, 2, ...

Similarly, for odd N we find the formula:

1 + (sum i = 0 to k ceil (i / 2) * 4) for k = 0, 1, 2, ...

In PHP, we can generate them through something like this:

 function antiDiagonal($n) { $values = array(); if ($n % 2 == 0) { for ($k = 0; $k < $n; $k++) { $accum = 0; for ($j = 0; $j <= $k; $j++) { $accum += floor($j/2)*4 + 2; } $values[] = $accum; } } else { for ($k = 0; $k < $n; $k++) { $accum = 1; for ($j = 0; $j <= $k; $j++) { $accum += ceil($j/2)*4; } $values[] = $accum; } } return $values; }

Note that the maximum value of k is less than the dimension of the matrix.

Combining these functions, we get:

 array_unique(array_merge(mainDiagonal($n), antiDiagonal($n)))
+2
source

The task can be divided into 4 parts: find the numbers diagonally in each quadrant. There are four quadrants, so we have four knitting needles:

  • Northwest (NW) spoke
  • Northeast (NE) spoke
  • Southwest (SW) spoke
  • Southeast (SE) spoke

For example, in your illustration of the Ulam spiral, when N is equal.

  • NW has 1, 7, ...
  • NE said 2, 10, ...
  • SW said 4, 16, ...
  • SE has 3, 13, ...

The problem is further divided into two cases:

  • N is even.
  • N is odd.

Case 1: N equals

Here are the formulas for each knitting needle:

 NW spoke: f(n) = 4*n*n + 2*n + 1 NE spoke: g(n) = 4*n*n + 4n + 2 SW spoke: h(n) = 4*n*n + 8*n + 4 SE spoke: i(n) = 4*n*n + 6*n + 3

where n = 0, 1, 2, ...

For a 4x4 matrix, calculate the following set:

 {f(0), f(1), g(0), g(1), h(0), h(1), i(0), i(1)}

It gives the diagonal values:

 {1, 7, 2, 10, 4, 16, 3, 13}

In the general case, for the matrix NxN, when N is even, calculate the following set to obtain diagonal values:

 { f(0), ..., f(N/2 - 1), g(0), ..., g(N/2 - 1), h(0), ..., h(N/2 - 1), i(0), ..., i(N/2 - 1) }

Case 2: N is odd

In your illustration of the Ulam spiral, when N is odd, the formulas for each spoke are:

 NW spoke: f(n) = 4*n*n + 2*n + 1 NE spoke: g(n) = 4*n*n + 4*n + 1 SW spoke: h(n) = 4*n*n + 1 SE spoke: i(n) = 4*n*n - 2*n + 1

where n = 0, 1, 2, ...

Note that f (0) = g (0) = h (0) = i (0) = 1.

For 3x3, calculate the following set:

 {f(0), f(1), g(1), h(1), i(1)}

It gives the following diagonal values:

 {1, 7, 9, 5, 3}.

In the general case, for the matrix NxN, when N is odd, calculate the following set to obtain diagonal values:

 { f(0), ..., f((N - 1)/2, g(0), ..., g((N - 1)/2), h(0), ..., h((N - 1)/2), i(0), ..., i((N - 1)/2) }

PHP code

Finally, here is a PHP program that demonstrates what I discussed above.

 <?php function ulam_diag($N) { $result = array(); if ($N % 2 == 0) { for ($n = 0; $n < $N / 2; $n++) { $result[] = 4*$n*$n + 2*$n + 1; $result[] = 4*$n*$n + 4*$n + 2; $result[] = 4*$n*$n + 8*$n + 4; $result[] = 4*$n*$n + 6*$n + 3; } } else { $result[] = 1; for ($n = 1; $n <= ($N - 1) / 2; $n++) { $result[] = 4*$n*$n + 2*$n + 1; $result[] = 4*$n*$n + 4*$n + 1; $result[] = 4*$n*$n + 1; $result[] = 4*$n*$n - 2*$n + 1; } } sort($result); return $result; } print_r(ulam_diag(4)); print_r(ulam_diag(3)); ?>

Output:

 Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 7 [5] => 10 [6] => 13 [7] => 16 ) Array ( [0] => 1 [1] => 3 [2] => 5 [3] => 7 [4] => 9 )

Here is the code one Ideal: http://ideone.com/F9jaC0

If you are interested in how I came to the formulas, there are good results for the four spokes of the Ulam spiral. Here are the links:

The ulama spirals in your illustrations are oriented differently from the popular representation of the Ulam spiral, so I took these well-known results and adjusted the offset n for each formula to work with your Ulam spiral. These adjustments remain in the form of exercises for the reader .; -)

+1
source

Well, for each row in the matrix, we have two diagonal values. To get these two values, I used two positions (x1, y1) and (x2, y2) for the main and anti-diagonals.

Well, I wrote this code:

 <?php function getSpiralDiagonal($spiralArr,$N){ $diagonalValueCount = $N*2; $xIndexMainDiagonal = 0; $yIndexMainDiagonal = 0; $xIndexAntiDiagonal = 0; $yIndexAntiDiagonal = $N-1; while($diagonalValueCount > 0){ //checking for same position if($yIndexMainDiagonal == $yIndexAntiDiagonal){ echo $spiralArr[$xIndexMainDiagonal][$yIndexMainDiagonal].'<br>'; }else{ echo $spiralArr[$xIndexMainDiagonal][$yIndexMainDiagonal].'<br>'; echo $spiralArr[$xIndexAntiDiagonal][$yIndexAntiDiagonal].'<br>'; } $xIndexMainDiagonal++; $yIndexMainDiagonal++; $xIndexAntiDiagonal++; $yIndexAntiDiagonal--; $diagonalValueCount -= 2; } } $spiralArr = array(array('7','8','9'),array('6','1','2'),array('5','4','3')); getSpiralDiagonal($spiralArr,3); ?>
0
source

More articles:


All Articles