Wikipedia:Reference desk/Archives/Computing/2015 October 20

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 20

iterating over a square matrix, one square frame at a time

Hello,

I have a square matrix of size N (N is odd). I want to iterate over the matrix, one "square frame", or ring, at a time, from the outmost ring, to the innermost ring ( which contains only one element). How can I do it efficiently?

for example in the following matrix:

${\begin{bmatrix}1&2&3&4&5\\6&7&8&9&10\\11&12&13&14&15\\16&17&18&19&20\\21&22&23&24&25\end{bmatrix}}.$

the innermost ring is 13, the next ring is 7, 8, 9, 12, 14, 17, 18, 19, etc.

I need to to do it as a part of a homework question: I was given a matrix in which all the numbers in a given ring are bigger than all the numbers in the more inner rings. I should write a function that given a number n says if n is in the matrix (1) or not (0). The answer I thought of is the following: iterate over all rings, from the outmost to the innermost; if n is in the current ring, stop and return 1. For each ring also check if n is smaller than all numbers in this ring; if n is not found in the current ring and n is not smaller than all numbers in the ring, return 0; else, continue to the more inner ring. If after iterating all rings the numbers wasn't found, return 0. Does it make sense?

Thanks. 31.154.144.146 (talk) 06:29, 20 October 2015 (UTC)

The algorithm you describe is much more complicated than simple scanning the whole array row by row and checking each element against the given number. And it is not a bit faster, on average. --CiaPan (talk) 11:02, 20 October 2015 (UTC)

Hint: you usually don't need to check all numbers in all rings. Suppose N>6, and your number is 500; and you find that $a_{3,3}$ is 800, then 500 certainly is not in rings containig $a_{1,1}$ or $a_{2,2}$ (because numbers in that two rings are bigger than 800). --CiaPan (talk) 10:06, 20 October 2015 (UTC)

The JPEG algorithm's entropy coding stage iterates over a square matrix in this zig-zag sequence.

A common trick in such problems is to re-sequence the matrix - in other words, there is no reason you need to store the matrix such that (x,y) pairs are sequentially rastered. For example, look how JPEG iterates over a transformed block after its quantization stage. In another example, in the case of the finite difference time domain model for solving the wave equation, an efficient implementation may alternate through a matrix using square sub-blocks, iterated in a checkerboard-style sequence. Nothing mandates that you store or iterate your matrix elements in any specific order, provided that you know how to obtain the coefficient at any row and column. That may require a simple conversion from standard coordinates into the index in your custom data structure.

All of these tricks are used because reordering can improve performance for some specific calculation, much like pre-sorting a list yields good efficiency for search algorithms on that list. If you think about your problem, you're essentially trying to sort the elements of a matrix, which implies that you want a mapping of these matrix elements into a single (1-D) sequence. I'm sure if you draw a picture, you'll see how you can conceptually traverse the "rings" of your matrix... and then you just need to deduce an equation that represents that traversal.

Nimur (talk) 14:07, 20 October 2015 (UTC)

Thank you all for the answers! However, I haven't succeeded to find a solution yet, as I am in the very beginning of an introductory CS course, and had not tackled such problems before (we have just started discussing simple sorting algorithms). Can you please give me another hint/recommended way of working towards the solution? Thanks, 31.154.144.146 (talk) 16:24, 20 October 2015 (UTC)

Size N array with elements a_i,j i and j being the row and column (I assume the index starts at 1, could be zero, depends on the programming language; a_i,j is a[i,j]). There are (N+1)/2 rings, and you search for a value equal to n:

You can use binary search algorithm to find the right ring, but lets keep it simple, simply test one value of each ring until you find a ring with a value smaller than n:

For i=1 to (N+1)/2: if a_i,i<=n then ....

Once the test is true, you know that n could be in either ring i or the previous ring i-1. Test all values in ring i: if you find n, return(1); If none found: test ring i-1. If none found there, return(0).

(you could also test if any value in ring i is larger than n, if that's the case you won't need to test ring i-1 because they'll all be larger as well, but I wouldn't bother, makes the program more complex, without gaining anything)

Ring i is a square with corners at coordinates i and N-i+1. For testing the values, it's easiest imo to test 4 values (one on each side of the square) at the same time. For example:

For p=i to N-i+1:

if (a_i,p==n OR a_N-i+1,p==n OR a_p,i==n OR a_p,N-i+1==n) then return(1)

Make sure your code works for all cases: for example: if a_1,1<n, only ring 1 has to be tested, there's no ring zero. Ssscienccce (talk) 17:32, 20 October 2015 (UTC)

Thanks! 31.154.144.146 (talk) 18:44, 20 October 2015 (UTC)

Woops, I tried to be too smart, wanted to prevent that the corners were tested twice, but leaving off the +1 doesn't work, would test two corners twice, two others not at all. see yellow correction. All corners are tested twice, but that's no big deal.

To only test each value once:

For p=i to N-i:

if (a_i,p==n OR a_N-i+1,p+1==n OR a_p+1,i==n OR a_p,N-i+1==n) then return(1). I think... Ssscienccce (talk) 21:11, 20 October 2015 (UTC)

Two approaches:

A) If you only have to do this check once, and the matrix isn't huge, then just check against every element in the array in the normal order (check one row or column first, then the next, etc.). It's not the most efficient method, but keeping the code simple and thus less error-prone also has value, and the extra CPU time won't be significant.

B) If you need to repeat this operation many times, or the matrix is huge, then I would copy the matrix into a flat list, which is in numeric order. You would do this by first copying each ring to a temporary list, sort it, then add it to the main list in sorted order (even a bubble sort wouldn't be too bad to sort each ring). At that point you can do a binary search, linked to above, to quickly determine if any number is in the full list representing the sorted matrix, and can compare with the first element in the list (or last, depending on if you sorted in descending or ascending order) to see if it's smaller.

I can help with any of these steps if you need it. StuRat (talk) 19:11, 20 October 2015 (UTC)

If you are going to go through the trouble of restructuring the representation of the data, I would use insertion sort and create a linked list of all elements. That would take less than O(n log n) time. Then, searching the new list would take O(log n) time. It would not be much improvement to have multiple lists to search. From a very technical standpoint, if I had multiple lists, the first check would cut how many lists I am looking at in half, then I'd cut that in half and then cut that in half until I have one list. Then, I would cut that list in half over and over until I either find or don't find what I need. With a single sorted list, I'd cut it in half and then in half until I find what I am looking for (or don't find it). So, both ways do the same thing: cut search space in half with each round. 199.15.144.250 (talk) 16:45, 23 October 2015 (UTC)

Only two problems. If you use insertion sort, your complexity is O(n²), not O(n log n). And you cannot use binary search on linked lists - binary search needs random access, i.e. an array. If you have an already partially ordered set, you could use quicksort. If you want a linked data structure, you could use a binary search tree. --Stephan Schulz (talk) 01:14, 24 October 2015 (UTC)

My understanding is that it's already partially ordered, but in a specific way. That is, the elements in each ring are unordered, but the rings themselves are ordered. Hence the strategy of only sorting the elements in each ring, separately, rather than sorting the entire array together. StuRat (talk) 02:16, 24 October 2015 (UTC)

Yes. But 199 suggested to completely sort the elements. That said, if I'd set this exercise for first-year students, I would expect a solution that reduces complexity from O(n²) (in the number of rows/columns of the matrix) with a naive search to O(n) with the algorithm roughed out by Ssscienccce. --Stephan Schulz (talk) 15:23, 24 October 2015 (UTC)

And my method would completely sort the elements, just more efficiently. Say one ring has elements from 100-199, and the next ring has 200-299. By sorting each ring separately, then concatenating the results, the entire list should then be sorted. We save time by not trying to sort the rings relative to each other. StuRat (talk) 18:13, 24 October 2015 (UTC)

Hadamrd Gate

Assuming we have $|x\rangle =|0a\rangle +|1b\rangle$.

Performing Hadamrad on the first qubit yields $|0\rangle (|a\rangle +|b\rangle )$.

Performing Hadamrad on the first qubit, again, yields $(|0\rangle +|1\rangle )(|a\rangle +|b\rangle )\neq |x\rangle$.

But Hadamard is self-inverse (=the inverse of iteslf), so performing Hadamrd twice should return x, so this is probably wrong... I guess the result of the first time we performed Hadamrd is not what I wrote above. So, what is the correct result? 31.154.92.193 (talk) 17:33, 20 October 2015 (UTC)

--Edit-- Moreover, denoting $T=H\otimes I$ (T is the tensor product of Hadamrd and the Identity gates, so T performs Hadamrd on the first qubit only), we have: $T(|0a\rangle +|1b\rangle )=T((|0\rangle +|1\rangle )(|a\rangle +|b\rangle ))=|0\rangle (|a\rangle +|b\rangle )$, so T is not an injection, and thus, is not a unitary transformation... What is/ are my mistake/s? 80.246.140.106 (talk) 18:18, 20 October 2015 (UTC)

Ignoring normalization, $T(|0a\rangle +|1b\rangle )=(|0\rangle +|1\rangle )|a\rangle +(|0\rangle -|1\rangle )|b\rangle =|0\rangle (|a\rangle +|b\rangle )+|1\rangle (|a\rangle -|b\rangle )$, so your first step is correct only if a=b. -- BenRG (talk) 22:43, 20 October 2015 (UTC)

Thank you! 31.154.92.193 (talk) 05:44, 21 October 2015 (UTC)

Sound Recorder (Windows)

The Sound Recorder (Windows) included in Vista is useful for recording audio to a file but it has to be manually controlled. How can I control it from a program written in a language such as C or BASIC ? Bestfaith (talk) 23:29, 20 October 2015 (UTC)

I found AutoIt very useful (years ago, before I switched to linux). My favorite windows app, made it very easy to automate tasks (send keystrokes, menu commands, mouse clicks to individual windows, start and close programs, respond to events), read window contents (like names of open files), perform file operations based on that info etc.. . Not sure if it's what you're looking for, but worth a look. Ssscienccce (talk) 02:35, 21 October 2015 (UTC)