मैट्रिक्स और एल्गोरिदम "सर्पिल"

Question

मैं पूछना चाहता था कि क्या कुछ एल्गोरिदम तैयार है, जिसने मुझे ऐसा करने की अनुमति दी: मेरे पास एम एक्स एन तत्वों के साथ एक मैट्रिक्स एम (कोल) एक्स एन (पंक्ति) है। मैं इस तत्व को स्थिति देना चाहते केंद्र से शुरू करने और एक सर्पिल के रूप में घूर्णन, उदाहरण के लिए, एक मैट्रिक्स 3x3 के लिए मैं 9 तत्वों तो परिभाषित किया गया है:

5 6 7 
4 9 8 
3 2 1 

या ऊना मैट्रिक्स 4 x 3 मैं 12 तत्व के लिए, करना परिभाषित:

3 4 
    7 8 
    10 9 
    6 5 
    2 1 

आदि मैं मूल रूप से MXN elemen के पूर्णांक के एक सरणी को परिभाषित समाधान कर लिया है:

8 9 10 1 
    7 12 11 2 
    6 5 4 3 

या फिर, एक मैट्रिक्स 5x2 मैं 10 तत्वों तो परिभाषित किया गया है टीएस और मैन्युअल रूप से मूल्य लोड कर रहा है, लेकिन मेरे लिए जीनरल में स्वचालित रूप से एल्गोरिदम से बनाए गए मैट्रिक्स की तरह। धन्यवाद कि मुझे कुछ खोजने में कौन मदद कर सकता है, बहुत बहुत धन्यवाद।

अद्यतन

इस कोड, के बारे में मैं चाहता हूँ है, लेकिन डेल्फी में नहीं है exactely करते हैं; केवल मुझे केवल 1 से शुरू करना चाहिए और 0 से नहीं चाहिए। मेरे लिए महत्वपूर्ण यह है कि यह किसी भी मैट्रिक्स एम एक्स एन के लिए मान्य है। डेल्फी में अनुवाद करने में मेरी मदद कौन करता है?

(defun spiral (rows columns) 
    (do ((N (* rows columns))  
    (spiral (make-array (list rows columns) :initial-element nil))  
    (dx 1) (dy 0) (x 0) (y 0)  
    (i 0 (1+ i)))  
((= i N) spiral) 
(setf (aref spiral y x) i) 
    (let ((nx (+ x dx)) (ny (+ y dy))) 
    (cond  
     ((and (< -1 nx columns)  
     (< -1 ny rows)   
     (null (aref spiral ny nx)))  
    (setf x nx 
      y ny)) 
    (t (psetf dx (- dy)     
     dy dx)  
    (setf x (+ x dx)    
    y (+ y dy))))))) 


> (pprint (spiral 6 6)) 

#2A ((0 1 2 3 4 5) 
    (19 20 21 22 23 6) 
    (18 31 32 33 24 7) 
    (17 30 35 34 25 8) 
    (16 29 28 27 26 9) 
    (15 14 13 12 11 10)) 


> (pprint (spiral 5 3)) 

#2A ((0 1 2) 
    (11 12 3) 
    (10 13 4) 
     (9 14 5) 
     (8 7 6)) 

फिर से बहुत धन्यवाद।

Answer 1

क्लासिक spiral algorithm के आधार पर। समर्थन गैर वर्ग मैट्रिक्स:

program SpiralMatrix; 
{$APPTYPE CONSOLE} 
uses 
    SysUtils; 

type 
    TMatrix = array of array of Integer; 

procedure PrintMatrix(const a: TMatrix); 
var 
    i, j: Integer; 
begin 
    for i := 0 to Length(a) - 1 do 
    begin 
    for j := 0 to Length(a[0]) - 1 do 
     Write(Format('%3d', [a[i, j]])); 
    Writeln; 
    end; 
end; 

var 
    spiral: TMatrix; 
    i, m, n: Integer; 
    row, col, dx, dy, 
    dirChanges, visits, temp: Integer; 
begin 
    m := 3; // columns 
    n := 3; // rows 
    SetLength(spiral, n, m); 
    row := 0; 
    col := 0; 
    dx := 1; 
    dy := 0; 
    dirChanges := 0; 
    visits := m; 
    for i := 0 to n * m - 1 do 
    begin 
    spiral[row, col] := i + 1; 
    Dec(visits); 
    if visits = 0 then 
    begin 
     visits := m * (dirChanges mod 2) + n * ((dirChanges + 1) mod 2) - (dirChanges div 2) - 1; 
     temp := dx; 
     dx := -dy; 
     dy := temp; 
     Inc(dirChanges); 
    end; 
    Inc(col, dx); 
    Inc(row, dy); 
    end; 
    PrintMatrix(spiral); 
    Readln; 
end. 

3 एक्स 3:

1 2 3 
8 9 4 
7 6 5 

4 एक्स 3:

1 2 3 4 
10 11 12 5 
9 8 7 6 

2 x 5:

1 2 
10 3 
9 4 
8 5 
7 6 

Answer 2

यहां आप जो कुछ भी करने की कोशिश कर रहे हैं उसके लिए जावास्क्रिप्ट कार्यान्वयन टिप्पणी की गई है।

// return an array representing a matrix of size MxN COLxROW 
function spiralMatrix(M, N) { 
var result = new Array(M * N); 
var counter = M * N; 
// start position 
var curCol = Math.floor((M - 1)/2); 
var curRow = Math.floor(N/2); 
// set the center 
result[(curRow * M) + curCol] = counter--; 
// your possible moves RIGHT, UP, LEFT, DOWN * y axis is flipped 
var allMoves = [[1,0], [0,-1], [-1,0], [0,1]]; 
var curMove = 0; 
var moves = 1; // how many times to make current Move, 1,1,2,2,3,3,4,4 etc 
// spiral 
while(true) { 
for(var i = 0; i < moves; i++) { 
    // move in a spiral outward counter clock-wise direction 
    curCol += allMoves[curMove][0]; 
    curRow += allMoves[curMove][1]; 
    // naively skips locations that are outside of the matrix bounds 
    if(curCol >= 0 && curCol < M && curRow >= 0 && curRow < N) { 
    // set the value and decrement the counter 
    result[(curRow * M) + curCol] = counter--; 
    // if we reached the end return the result 
    if(counter == 0) return result; 
    } 
} 
// increment the number of times to move if necessary UP->LEFT and DOWN->RIGHT 
if(curMove == 1 || curMove == 3) moves++; 
// go to the next move in a circular array fashion 
curMove = (curMove + 1) % allMoves.length; 
} 
} 

कोड सबसे कारगर नहीं है क्योंकि यह पहले पता चल सके कि स्थान उस पर चलते मान्य है बिना भोलेपन से सर्पिल चलता है। यह केवल उस पर मूल्य निर्धारित करने से पहले वर्तमान स्थान की वैधता की जांच करता है।

Answer 3

वहां आप जाते हैं !!! 30some वाक्यविन्यास त्रुटियों के बाद ...

ideone.com पर, मैंने इसे कुछ परीक्षणों के साथ भाग लिया और ऐसा लगता है कि यह ठीक काम करता है। मुझे लगता है कि आप अभी भी आउटपुट देख सकते हैं और इसे स्वयं चला सकते हैं ...

मैंने कोड में कुछ टिप्पणियां डालीं। इसके अधिकांश को समझने के लिए पर्याप्त है। मुख्य नेविगेशन सिस्टम व्याख्या करने के लिए थोड़ा कठिन है। संक्षेप में, सर्पिल करना पहली दिशा में 1 बार, दूसरा 1 बार, तीसरा 2 गुना, चौथा 2 गुना, पांचवां 3 गुना, 3, 4, 4, 5, 5, और इसी तरह से चल रहा है। मैं इस व्यवहार को प्राप्त करने के लिए seed और step नामक उपयोग करता हूं।

program test; 

var 
    w, h, m, n, v, d : integer; // Matrix size, then position, then value and direction. 
    spiral : array of array of integer; // Matrix/spiral itself. 
    seed, step : integer; // Used to travel the spiral. 

begin 
    readln(h); 
    readln(w); 
    setlength(spiral, h, w); 
    v := w * h; // Value to put in spiral. 
    m := trunc((h - 1)/2); // Finding center. 
    n := trunc((w - 1)/2); 
    d := 0; // First direction is right. 

    seed := 2; 
    step := 1; 

    // Travel the spiral. 
    repeat 
     // If in the sub-spiral, store value. 
     if ((m >= 0) and (n >= 0) and (m < h) and (n < w)) then 
     begin 
      spiral[m, n] := v; 
      v := v - 1; 
     end; 

     // Move! 
     case d of 
      0: n := n + 1; 
      1: m := m - 1; 
      2: n := n - 1; 
      3: m := m + 1; 
     end; 

     // Plan trajectory. 
     step := step - 1; 
     if step = 0 then 
     begin 
      d := (d + 1) mod 4; 
      seed := seed + 1; 
      step := trunc(seed/2); 
     end; 
    until v = 0; 

    // Print the spiral. 
    for m := 0 to (h - 1) do 
    begin 
     for n := 0 to (w - 1) do 
     begin 
      write(spiral[m, n], ' '); 
     end; 
     writeln(); 
    end; 

end. 

यदि आपको वास्तव में टेक्स्ट सर्पिल प्रिंट करने की आवश्यकता है तो मैं आपको संख्याओं को संरेखित करने दूंगा। बस उन्हें रिक्त स्थान के साथ पैड।

संपादित करें:

भूल थी ... ताकि इसे ideone पर काम करने के लिए, मैं इनपुट के रूप में 2 तर्ज पर मापदंडों डाल दिया। एम, फिर एन।

उदाहरण के लिए:

5 
2 

पैदावार

3 4 
7 8 
10 9 
6 5 
2 1 

Answer 4

हालांकि प्रश्न पहले से ही उत्तर दिया गया है, यह एक वैकल्पिक समाधान है (तर्कसंगत रूप से सरल)। समाधान पायथन में है (बोली-विभागीय सरणी के लिए numpy का उपयोग कर), लेकिन आसानी से पोर्ट किया जा सकता है।

import numpy as np 

def spiral(m, n): 
    """Return a spiral numpy array of int with shape (m, n).""" 
    a = np.empty((m, n), int) 
    i, i0, i1 = 0, 0, m - 1 
    j, j0, j1 = 0, 0, n - 1 
    for k in range(m * n): 
     a[i, j] = k 
     if i == i0 and  j0 <= j < j1: j += 1 
     elif j == j1 and  i0 <= i < i1: i += 1 
     elif i == i1 and  j0 < j <= j1: j -= 1 
     elif j == j0 and 1 + i0 < i <= i1: i -= 1 
     else: 
      i0 += 1 
      i1 -= 1 
      j0 += 1 
      j1 -= 1 
      i, j = i0, j0 
    return a 

:

मूल विचार तथ्य यह है कि चरणों की संख्या अंत हालत, के रूप में जाना जाता है (एम * एन) और ठीक से प्रत्येक यात्रा पर लूप के अगले तत्व गणना करने के लिए उपयोग करने के लिए है और यहां कुछ आउटपुट:

>>> spiral(3,3) 
array([[0, 1, 2], 
     [7, 8, 3], 
     [6, 5, 4]]) 
>>> spiral(4,4) 
array([[ 0, 1, 2, 3], 
     [11, 12, 13, 4], 
     [10, 15, 14, 5], 
     [ 9, 8, 7, 6]]) 
>>> spiral(5,4) 
array([[ 0, 1, 2, 3], 
     [13, 14, 15, 4], 
     [12, 19, 16, 5], 
     [11, 18, 17, 6], 
     [10, 9, 8, 7]]) 
>>> spiral(2,5) 
array([[0, 1, 2, 3, 4], 
     [9, 8, 7, 6, 5]])