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
Started writing again. Going to go over what I was talking about in the first again using a different slant. First, this ol' boy: [code] 0 1 2 3 4 5 6 7 1 0 3 2 5 4 7 6 2 3 0 1 6 7 4 5 3 2 1 0 7 6 5 4 4 5 6 7 0 1 2 3 5 4 7 6 1 0 3 2 6 7 4 5 2 3 0 1 7 6 5 4 3 2 1 0 [/code] Then brute force perm the rows and columns. If it is orthogonal, spit it out. It went a lot faster than I was expecting. Time to stare at something like this: [code] 0 2 4 6 3 1 7 5 1 3 5 7 2 0 6 4 2 0 6 4 1 3 5 7 3 1 7 5 0 2 4 6 4 6 0 2 7 5 3 1 5 7 1 3 6 4 2 0 6 4 2 0 5 7 1 3 7 5 3 1 4 6 0 2 [/code] That is orthogonal to the XOR square of size 8. Bunches of those I was doing the Zen stare thing looking for any pattern that I could take advantage of. When I started lookinig at 1d groups in a recursive manner, the basic XOR pattern popped- out. Which makes total sense because it is XOR after all. Right? Using the above square, I extracted the sequence [2,4,3]. How do you use that 3-digit sequence and XOR to get an orthogonal? Well, that 3-digit example will give you a transversal, and the transversal will give you the orthogonal. As it turns out, any transversal in XOR will give you an orthogonal. So, 3 digits to transversal, transversal to orthogonal. Boom. Done. We are going to take those 3 digits and the starting number 0. XOR the first digit with 0 and extend. Xor that with the second digit, and extend again. One more time with the third digit. [code] [0,[2,4,3]] # starting number and XOR extend sequence [0]^2=[2] # xor with first [0,2] # extend [0,2]^4=[4,6] # xor with second [0,2,4,6] # extend [0,2,4,6]^3=[3,1,7,5] # xor with third [0,2,4,6,3,1,7,5] # extend [/code] That final 8-digit sequence is a transversal in the original XOR square. And there are quite a few ways to use it to generate a complete orthogonal square. The easiest way, in Python, is to re-index the rows: [code] # re-index rows using [0,2,4,6,3,1,7,5] 0 1 2 3 4 5 6 7 2 3 0 1 6 7 4 5 4 5 6 7 0 1 2 3 6 7 4 5 2 3 0 1 3 2 1 0 7 6 5 4 1 0 3 2 5 4 7 6 7 6 5 4 3 2 1 0 5 4 7 6 1 0 3 2 [/code] Just to give you a start on seeing other ways, here are two alternatives to getting a transversal from the same 8-digit sequence: [code] # by index by value 0 . . . . . . . 0 . . . . . . . . . 3 . . . . . . . . 2 . . . . . . . . 6 . . . . . . . . . 4 . . . . . . . 5 . . . . . . 6 . . . . . 7 . . . . . . . . . . . 3 . 4 . . . . . . . . . . 1 . . . . . . . . . . 1 . 7 . . . . . . . . . . . 2 . . . . 5 . . . . . [/code] Then play around with ways to use that to get a complete ortho square. I tried all sorts of ways, some wicked easy and some seriously convoluted, and they all worked. Back to some brute force. I went through and spit out all of the 3-digit sequences that worked. Here they are: [code] 243 341 413 512 612 713 245 345 416 516 615 715 251 352 432 532 631 731 256 357 436 537 637 736 261 361 452 543 641 751 265 367 457 547 647 756 273 372 463 573 672 763 276 375 467 576 675 765 [/code] There are 48 3-digit sequences that can be used to wicked quickly create an XOR orthogonal. Pick a starting number in the range[0...7], pick one of those sequences, and XOR extend it. In those 3-digit sequences, notice that none of them is a 0. Notice that the first digit is never 1. Notice that the second digit is never 2. Finally, notice that the third digit is never 4. If you think about it and how XOR works, this makes perfect sense. One more quick example. I'm going to take the sequence [2,4,3] and feed it [0...7]. The resulting square is the exact same as the first ortho that I showed above. [code] (0, [2, 4, 3], [0, 2, 4, 6, 3, 1, 7, 5]) (1, [2, 4, 3], [1, 3, 5, 7, 2, 0, 6, 4]) (2, [2, 4, 3], [2, 0, 6, 4, 1, 3, 5, 7]) (3, [2, 4, 3], [3, 1, 7, 5, 0, 2, 4, 6]) (4, [2, 4, 3], [4, 6, 0, 2, 7, 5, 3, 1]) (5, [2, 4, 3], [5, 7, 1, 3, 6, 4, 2, 0]) (6, [2, 4, 3], [6, 4, 2, 0, 5, 7, 1, 3]) (7, [2, 4, 3], [7, 5, 3, 1, 4, 6, 0, 2]) [/code] Seriously, how wicked cool is that? I also went through and did the same thing for XOR=16. Here is the first batch of 4-digit squences: [code] 238C 2483 2581 2681 2783 2815 2914 2A14 2B15 2C14 2D15 2E15 2F14 238D 2485 2586 2685 2786 2816 2917 2A17 2B16 2C17 2D16 2E16 2F17 238E 2489 2589 2689 2789 281C 291C 2A1C 2B1C 2C19 2D19 2E19 2F19 238F 248F 258E 268D 278C 281F 291F 2A1F 2B1F 2C1A 2D1A 2E1A 2F1A 239C 2491 2593 2693 2791 2834 2935 2A35 2B34 2C34 2D35 2E35 2F34 239D 2497 2594 2697 2794 2837 2936 2A36 2B37 2C37 2D36 2E36 2F37 239E 249A 259A 269A 279A 283D 293D 2A3D 2B3D 2C39 2D39 2E39 2F39 239F 249C 259D 269E 279F 283E 293E 2A3E 2B3E 2C3A 2D3A 2E3A 2F3A 23AC 24A1 25A3 26A3 27A1 2854 2954 2A54 2B54 2C51 2D51 2E51 2F51 23AD 24A7 25A4 26A7 27A4 2856 2956 2A56 2B56 2C53 2D53 2E53 2F53 23AE 24A9 25A9 26A9 27A9 285C 295D 2A5C 2B5D 2C5D 2D5C 2E5D 2F5C 23AF 24AF 25AE 26AD 27AC 285E 295F 2A5E 2B5F 2C5F 2D5E 2E5F 2F5E 23BC 24B3 25B1 26B1 27B3 2865 2965 2A65 2B65 2C61 2D61 2E61 2F61 23BD 24B5 25B6 26B5 27B6 2867 2967 2A67 2B67 2C63 2D63 2E63 2F63 23BE 24BA 25BA 26BA 27BA 286D 296C 2A6D 2B6C 2C6D 2D6C 2E6D 2F6C 23BF 24BC 25BD 26BE 27BF 286F 296E 2A6F 2B6E 2C6F 2D6E 2E6F 2F6E 23C4 24C1 25C1 26C1 27C1 2894 2985 2A94 2B85 2C81 2D91 2E91 2F81 23C5 24C7 25C6 26C5 27C4 2897 2986 2A97 2B86 2C83 2D93 2E93 2F83 23C6 24C9 25CA 26C9 27CA 289D 298D 2A9C 2B8C 2C8D 2D9C 2E9D 2F8C 23C7 24CF 25CD 26CD 27CF 289E 298E 2A9F 2B8F 2C8F 2D9E 2E9F 2F8E 23D4 24D3 25D3 26D3 27D3 28B5 29A4 2AB5 2BA4 2CB1 2DA1 2EA1 2FB1 23D5 24D5 25D4 26D7 27D6 28B6 29A7 2AB6 2BA7 2CB3 2DA3 2EA3 2FB3 23D6 24DA 25D9 26DA 27D9 28BC 29AC 2ABD 2BAD 2CBD 2DAC 2EAD 2FBC 23D7 24DC 25DE 26DE 27DC 28BF 29AF 2ABE 2BAE 2CBF 2DAE 2EAF 2FBE 23E4 24E3 25E3 26E3 27E3 28C5 29D5 2AD4 2BC4 2CD4 2DC5 2ED5 2FC4 23E5 24E5 25E4 26E7 27E6 28C7 29D7 2AD6 2BC6 2CD7 2DC6 2ED6 2FC7 23E6 24E9 25EA 26E9 27EA 28CD 29DC 2ADC 2BCD 2CD9 2DC9 2ED9 2FC9 23E7 24EF 25ED 26ED 27EF 28CF 29DE 2ADE 2BCF 2CDA 2DCA 2EDA 2FCA 23F4 24F1 25F1 26F1 27F1 28F4 29E4 2AE5 2BF5 2CF4 2DE5 2EF5 2FE4 23F5 24F7 25F6 26F5 27F4 28F6 29E6 2AE7 2BF7 2CF7 2DE6 2EF6 2FE7 23F6 24FA 25F9 26FA 27F9 28FC 29ED 2AED 2BFC 2CF9 2DE9 2EF9 2FE9 23F7 24FC 25FE 26FE 27FC 28FE 29EF 2AEF 2BFE 2CFA 2DEA 2EFA 2FEA [/code] Truly a thing of beauty. Brings a smile to my face. And that's just the first 416 sequences. There are 5,408 more to go. Heh. That is as big as I have gone using this particular pattern. The next size up that I have an interest in is 256. But I wouldn't use this method for creating XOR orthos of size 256. For size 256, I would use the fractal/distribution pattern in XOR. This is what I was talking about in the second post. I've since refined that particular fractal/distribution technique considerably.
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