OZONE Asylum
Forums
Server-Side Scripting - Oh my!
Latin Squares and XOR
This page's ID:
33315
Search
QuickChanges
Forums
FAQ
Archives
Register
Edit Post
Who can edit a post?
The poster and administrators may edit a post. The poster can only edit it for a short while after the initial post.
Your User Name:
Your Password:
Login Options:
Remember Me On This Computer
Your Text:
Insert Slimies »
Insert UBB Code »
Close
Last Tag
|
All Tags
UBB Help
The first thing we are going to look at is two very particular latin squares of size 4. Both of those being: [code] 0 1 2 3 0 1 2 3 1 0 3 2 1 0 3 2 2 3 0 1 2 3 1 0 3 2 1 0 3 2 0 1 [/code] Why those two? Because those are the only two that exist. You can perm one all you want and you will never get the other one. They are reduced to complete uniqueness with regards to perming. The first one is the XOR pattern. Fairly easy. Ah, but the second one is very different from the first in a very different way other than perming. The second square [b]does not any orothogonal latin mates[/b]. None. Do the perms and check for yourself. Shouldn't take any coder too long to try it. The second square does not have any orthogonal mates, but the first one does. And there is a funny little trick to finding them. There is a cute little series of swaps that does it. Let's look at that first one in groups like this: [code] ..C C D D A 0 1 2 3 A 1 0 3 2 B 2 3 0 1 B 3 2 1 0 [/code] 'A' is a group of two rows. 'B' is a group of two rows. 'C' is a group of two columns. 'D' is a group of two columns. Step 1: Swap any group with itself. - swap one A and the other A - swap one B and the other B - swap one C and the other C - swap one D and the other D Step 2: Swap one from one group with another group in the same vert or horz. - Swap either A with either B - Swap either C with either D Or you can do Step 2 first and then Step 1. It doesn't matter. If you do those swaps, you will always get an orthogonal to the first XOR grid above. Again, try it for yourself. Not that hard to code. I originally did it with a pencil and graph paper before moving on to code. I'm low-tech like that sometimes. Heh. Now, this is where it gets into distribution. We want a very particular kind of even distribution that can be found in latin squares, and no place better than in a latin square. Or rather, in this case, orthogonal latin squares. If you can create this distribution with small orthogonals, you can expand it to find more orthogonals in larger squares. [code] 0 1 2 3 0 3 2 1 1 0 3 2 1 2 3 0 2 3 0 1 3 0 1 2 3 2 1 0 2 1 0 3 First latin square flattened for rows: 0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0 Second latin square flattened for cols: 0 3 2 1 1 2 3 0 3 0 1 2 2 1 0 3 [/code] Once they are flattened, notice how they pair-up: [code] 0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0 0 3 2 1 1 2 3 0 3 0 1 2 2 1 0 3 00 13 22 31 11 02 33 20 23 30 01 12 32 21 10 03 0 6 A D 5 2 F 8 B C 1 6 E 9 4 3 [/code] Pretty sweet, huh? As a matter of fact, using that kind of pairing making is easy to check to see if two grids are orthogonal. In that example, it would be 2 bits in base(4) producing 16 unique numbers. Not that hard to code. So, use those two flattened lines of othogonals to cull a larger square. Since 4x4=16, those two can be used to cull an XOR=16 grid. Lay it out, pick a number, squish, and solve. [code] |0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0 --+------------------------------- 0 |0 1 2 3 4 5 6 7 8 9 A B C D E F 3 |1 0 3 2 5 4 7 6 9 8 B A D C F E 2 |2 3 0 1 6 7 4 5 A B 8 9 E F C D 1 |3 2 1 0 7 6 5 4 B A 9 8 F E D C 1 |4 5 6 7 0 1 2 3 C D E F 8 9 A B 2 |5 4 7 6 1 0 3 2 D C F E 9 8 B A 3 |6 7 4 5 2 3 0 1 E F C D A B 8 9 0 |7 6 5 4 3 2 1 0 F E D C B A 9 8 3 |8 9 A B C D E F 0 1 2 3 4 5 6 7 0 |9 8 B A D C F E 1 0 3 2 5 4 7 6 1 |A B 8 9 E F C D 2 3 0 1 6 7 4 5 2 |B A 9 8 F E D C 3 2 1 0 7 6 5 4 2 |C D E F 8 9 A B 4 5 6 7 0 1 2 3 1 |D C F E 9 8 B A 5 4 7 6 1 0 3 2 0 |E F C D A B 8 9 6 7 4 5 2 3 0 1 3 |F E D C B A 9 8 7 6 5 4 3 2 1 0 0 |0 0 0 0 1 |1 1 1 1 --+------- --+------- 0 |0 5 A F 1 |2 7 8 D 0 |7 2 D 8 1 |5 0 F A 0 |9 C 3 6 1 |B E 1 4 0 |E B 4 1 1 |C 9 6 3 2 |2 2 2 2 3 |3 3 3 3 --+------- --+------- 2 |0 5 A F 3 |2 7 8 D 2 |7 2 D 8 3 |5 0 F A 2 |9 C 3 6 3 |B E 1 4 2 |E B 4 1 3 |C 9 6 3 [/code] Just for fun, let's take a look at all 4 of those mini-grids in the big square. You know, just the intersetions that we are after: [code] |0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0 --+------------------------------- 0 |0 . . . . 5 . . . . A . . . . F 3 |. . . 2 . . 7 . . 8 . . D . . . 2 |. . 0 . . . . 5 A . . . . F . . 1 |. 2 . . 7 . . . . . . 8 . . D . 1 |. 5 . . 0 . . . . . . F . . A . 2 |. . 7 . . . . 2 D . . . . 8 . . 3 |. . . 5 . . 0 . . F . . A . . . 0 |7 . . . . 2 . . . . D . . . . 8 3 |. . . B . . E . . 1 . . 4 . . . 0 |9 . . . . C . . . . 3 . . . . 6 1 |. B . . E . . . . . . 1 . . 4 . 2 |. . 9 . . . . C 3 . . . . 6 . . 2 |. . E . . . . B 4 . . . . 1 . . 1 |. C . . 9 . . . . . . 6 . . 3 . 0 |E . . . . B . . . . 4 . . . . 1 3 |. . . C . . 9 . . 6 . . 3 . . . [/code] In that whole grid, those are the only parts that we are interested in looking at. In those points, there is a very easy to find transversal that will lead to a full-on orthogonal. How do we do that? Let's look at mini-grid(0) and solve for (0,1,2,3) and their indices in the big grid. [code] 0 |0 0 0 0 --+------- 0 |0 5 A F 0 |7 2 D 8 0 |9 C 3 6 0 |E B 4 1 0=(0,0) 1=(0,15) 2=(7,5) 3=(9,10) [/code] Then you do mini_grid(1) and solve for (4,5,6,7). And so-on for the other mini-grids. Once you get all of that, you will have a transversal. And that transversal can easily be turned into an orthogonal to the XOR=16 grid. Start with easy orthos of size 4, and get orthos of size 16. Boom. Done. Not bad. Here is an example (not the above data) of doing such a thing: [code] 0 1 2 3 4 5 6 7 8 9 A B C D E F F E D C B A 9 8 7 6 5 4 3 2 1 0 5 4 7 6 1 0 3 2 D C F E 9 8 B A A B 8 9 E F C D 2 3 0 1 6 7 4 5 E F C D A B 8 9 6 7 4 5 2 3 0 1 1 0 3 2 5 4 7 6 9 8 B A D C F E B A 9 8 F E D C 3 2 1 0 7 6 5 4 4 5 6 7 0 1 2 3 C D E F 8 9 A B D C F E 9 8 B A 5 4 7 6 1 0 3 2 2 3 0 1 6 7 4 5 A B 8 9 E F C D 8 9 A B C D E F 0 1 2 3 4 5 6 7 7 6 5 4 3 2 1 0 F E D C B A 9 8 3 2 1 0 7 6 5 4 B A 9 8 F E D C C D E F 8 9 A B 4 5 6 7 0 1 2 3 6 7 4 5 2 3 0 1 E F C D A B 8 9 9 8 B A D C F E 1 0 3 2 5 4 7 6 [/code] But you can take it further. Since 16x16=256, you can do all of that again to get an ortho of size 256. And so on. As a whole, it may seem a bit complex to understand and code. But it's not. Doing all of this is wicked easy. The only part that was difficult was understanding the bits and putting them together in a new way for the first time. Once you do that, you will be all like, "Damn, that was easy. Why didn't I think of that sooner?" You know, something along those lines. Yes, I fought hard to get there, but now that I'm there it's all like whatever - because the bits that make up the whole and how to put them together really is that easy. Fucking genius. Now, if you'll excuse me, I have some lager to down and come code to clean. ugh... formatting [small](Edited by [url=http://ozoneasylum.com/user/351]warjournal[/url] on 11-10-2018 22:53)[/small]
Loading...
Options:
Enable Slimies
Enable Linkwords
« Backwards
—
Onwards »
Maximum Security
OZONE
DHTML/Javascript
Server-Side Scripting - Oh my!
CSS - DOM - XHTML - XML - XSL - XSLT
Stupid Basic HTML
Visual Therapy
Photoshop
Photoshop Pong, Anyone?
***WARNING*** BIG SIG APPROACHING
Photography
3D Modelling & Rendering
Multimedia/Animation
Print Graphics
Holding Pens
Philosophy and other Silliness
Outpatient Counseling
Site reviews!
Mad Scientists' Laboratory
Getting to know the Grail