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
Okay, let's do some 2d reduction kind of stuff to find a transversal in this little guy: [code] 0 1 2 3 +-------- 0 | 0 1 2 3 1 | 1 0 3 2 2 | 2 3 0 1 3 | 3 2 1 0 [/code] We are going to look for (0,1,2,3) each in turn, add them to lists, and remove them from the grid. First we find 0 and do like so: [code] val=[0] row=[0] col=[0] 1 2 3 +------ 1 | 0 3 2 2 | 3 0 1 3 | 2 1 0 [/code] Now we pick a 1. [code] val=[0,1] row=[0,2] col=[0,3] 1 2 +---- 1 | 0 3 3 | 2 1 [/code] Now for 2. [code] val=[0,1,2] row=[0,2,3] col=[0,3,1] 2 +-- 1 | 3 [/code] And the last one left is 3, so the final data set for a transversal looks like this: [code] val=[0,1,2,3] row=[0,2,3,1] col=[0,3,1,2] 0 . . . . . 3 . . . . 1 . 2 . . [/code] Re-arrange a few things. In this case, the rows so that [0,2,3,1] is along the one diagonal: [code] 0 . . . . 2 . . . . 3 . . . . 1 0 1 2 3 3 2 1 0 1 0 3 2 2 3 0 1 [/code] Boom. We now have an orthogonal to the original XOR=4 grid. Pretty sweet, yes? And, as near as I can tell, that will always work for XOR=4. I've done it tons of times and it has never locked-out. If you stare at it long enough, you should be able to see how the diagonals play an important part in why it never locks-out. When you start playing around with doing the same trick with XOR=8, you are going to have to start getting a little bit smarter. I look at it as a game of distribution. Where can I pick from so that I still have options as I get further down the road? I don't want to get too greedy in one spot or else I will run out of possibilities and lock-out. [code] 0 1 2 3 4 5 6 7 +---------------- 0 | 0 1 2 3 4 5 6 7 1 | 1 0 3 2 5 4 7 6 2 | 2 3 0 1 6 7 4 5 3 | 3 2 1 0 7 6 5 4 4 | 4 5 6 7 0 1 2 3 5 | 5 4 7 6 1 0 3 2 6 | 6 7 4 5 2 3 0 1 7 | 7 6 5 4 3 2 1 0 [/code] Going to look at it in quadrants. The upper-left has the digits [0,1,2,3], as does the lower-right. And the other two quadrants have [4,5,6,7]. In the upper-left quad, going to pick 0 and 1. Append the data and reduce the grid. [code] val=[0,1] row=[1,2] col=[1,3] 0 2 4 5 6 7 +------------ 0 | 0 2 4 5 6 7 3 | 3 1 7 6 5 4 4 | 4 6 0 1 2 3 5 | 5 7 1 0 3 2 6 | 6 4 2 3 0 1 7 | 7 5 3 2 1 0 [/code] Now going to pick 2 and 3 from the lower-right. [code] val=[0,1,2,3] row=[1,2,5,6] col=[1,3,7,5] 0 2 4 6 +-------- 0 | 0 2 4 6 3 | 3 1 7 5 4 | 4 6 0 2 7 | 7 5 3 1 [/code] From here, everthing falls into place very nicely. Pick 4 and 5: [code] val=[0,1,2,3,4,5] row=[1,2,5,6,0,3] col=[1,3,7,5,4,6] 0 2 +---- 4 | 4 6 7 | 7 5 [/code] After 6 and 7, left with this data set: [code] val=[0,1,2,3,4,5,6,7] row=[1,2,5,6,0,3,4,7] col=[1,3,7,5,4,6,2,0] [/code] Our transversal looks like this: [code] val=[0,1,2,3,4,5,6,7] row=[1,2,5,6,0,3,4,7] col=[1,3,7,5,4,6,2,0] . . . . 4 . . . . 0 . . . . . . . . . 1 . . . . . . . . . . 5 . . . 6 . . . . . . . . . . . . 2 . . . . . 3 . . 7 . . . . . . . [/code] Just for fun, going to re-arrange to the other diagonal. [code] . . . . . . . 2 . . . . . . 5 . . . . . . 3 . . . . . . 4 . . . . . . 1 . . . . . . 6 . . . . . . 0 . . . . . . 7 . . . . . . . 5 4 7 6 1 0 3 2 3 2 1 0 7 6 5 4 6 7 4 5 2 3 0 1 0 1 2 3 4 5 6 7 2 3 0 1 6 7 4 5 4 5 6 7 0 1 2 3 1 0 3 2 5 4 7 6 7 6 5 4 3 2 1 0 [/code] Tada. Fun or boring? Depends on what you are after. As for me, I'm have a lot of fun exploring the patterns. Other than playing with patterns, not a lot of insight into latin squares and orthogonals in general. Just playing with patterns. ! BONUS ROUND ! I have been playing with sizing things up. Well, to the size of XOR=16. I'm going to stop at that size for awhile because that's the size that I need for my purposes. So I started playing with XOR=16. Tackling it like a distribution problem to find transversals in a hurry. Once I got it down, I started getting little blocks of numbers like this: [code] 2 5 B C 7 0 E 9 8 F 1 6 D A 4 3 [/code] Just by looking at that I can very easily see that finding transversals in XOR=16 is wicked easy and fast. Ah, but there is a little bit more to it than that. You see, those numbers are in base16. Now watch what happens when you convert it to base4 and pull the bits apart: [code] 02 11 23 30 0 1 2 3 2 1 3 0 13 00 32 21 1 0 3 2 3 0 2 1 20 33 01 12 2 3 0 1 0 3 1 2 31 22 10 03 3 2 1 0 1 2 0 3 [/code] Not only did it spit out an XOR pattern, but it spit out a corresponding orthogonal. Everytime. Seriously, how cool is that? edit: formating issues in a few spots i'm sure you'll figure it out [small](Edited by [url=http://ozoneasylum.com/user/351]warjournal[/url] on 10-13-2017 00:23)[/small] [small](Edited by [url=http://ozoneasylum.com/user/351]warjournal[/url] on 10-13-2017 00:24)[/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