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
Nugget of joy that I started some time ago, but got put on hold just tad. I found myself in need of orthogonal latin squares of size 16. Turns out that it is ridiculously simple when using XOR as the base. There are a lot of amazing patterns in XOR, and this following code in Python makes use of some of them. I started out with some brute force using XOR with a size of 8, but terminated early because I just needed a few working samples as oppossed to the whole data set. Then I played with the samples until I found the patterns governing the whole. The patterns governing XOR size=8 hold true for XOR size=16... and on up for higher powers of 2. Once I had the patterns down in a certain sub-arena, things went pretty damn quick. Imagine trying to brute force 16!*16!*16!. No thanks. I'll find the patterns and go from there. This first chunk of code is brute force, but only 14!/11!=2184. And it will spit out 416 valid solutions to screen and to pickled file. A few things to note: - All solutions are a permutations of the XOR grid. - The permutations of the XOR grid are 1d rows only. There are some interesting things that go on with re-mapped values and redundancy, but too much to talk about right now. [code] #!/usr/bin/env python # -*- coding: utf-8 -*- import pickle import itertools def ndlist(s, v): # http://stackoverflow.com/questions/13447882/python-2-7-creating-a-multidimensional-list # by pterodragon return [ndlist(s[1:], v) for i in range(s[0])] if s else v def remap(rgrid,rseq): ngrid=[] for i in rseq: ngrid.append(rgrid[i]) return ngrid def is_ortho(agrid,bgrid): isbit=0 tsize=len(agrid) olist=[] for j in range(tsize): for i in range(tsize): olist.append(tsize*agrid[j][i]+bgrid[j][i]) t=set(olist) if len(t)==(tsize*tsize): isbit=1 return isbit ss=16 tgrid=ndlist([ss,ss],0) for j in range(ss): for i in range(ss): tgrid[j][i]=j^i pseq=[1,3,4,5,6,7,8,9,10,11,12,13,14,15] fseq=[] tcount=0 for x in itertools.permutations( pseq, 3): s=[0] y=[2] y.extend(x) for i in y: t=[] for v in s: t.append(i^v) s.extend(t) ts=set(s) if len(ts)==ss: rmgrid=remap(tgrid,s) obit=is_ortho(tgrid,rmgrid) if obit: fseq.append(y) print('{} --> {}').format(y,s) tcount=tcount+1 print('tcount={}').format(tcount) output = open('xor16_orthoseq.pkl', 'wb') pickle.dump(fseq, output,-1) output.close() [/code] This second chunk of code will load the solutions from the pickled file, pick one at random, expand into a latin square, double-check that it is still orthogonal to the base XOR grid, and dump it screen. [code] #!/usr/bin/env python # -*- coding: utf-8 -*- import pickle import random def ndlist(s, v): # http://stackoverflow.com/questions/13447882/python-2-7-creating-a-multidimensional-list # by pterodragon return [ndlist(s[1:], v) for i in range(s[0])] if s else v def cout_2dgrid(cgrid): ll=len(cgrid) cmap=['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'] for row in range(ll): pme=' ' for col in range(ll): pme=pme+' '+cmap[ cgrid[row][col] ] print(pme) print('') return def remap(rgrid,rseq): ngrid=[] for i in rseq: ngrid.append(rgrid[i]) return ngrid def is_ortho(agrid,bgrid): isbit=0 tsize=len(agrid) olist=[] for j in range(tsize): for i in range(tsize): olist.append(tsize*agrid[j][i]+bgrid[j][i]) t=set(olist) if len(t)==(tsize*tsize): isbit=1 return isbit ss=16 tgrid=ndlist([ss,ss],0) for j in range(ss): for i in range(ss): tgrid[j][i]=j^i pkl_file = open('xor16_orthoseq.pkl', 'rb') xseq = pickle.load(pkl_file) y=random.choice(xseq) s=[random.choice( range(ss) )] for i in y: t=[] for v in s: t.append(i^v) s.extend(t) print('s={}\n').format(s) ogrid=remap(tgrid,s) cout_2dgrid(ogrid) fcheck=is_ortho(tgrid,ogrid) if fcheck: print('yes, ortho') else: print('fail') [/code] On one hand, it is a bit boring because it doesn't really dig into slews of combinations and permutations. On the other hand, it is pretty amazing to see what can be done with patterns. 16!*16!*16! vs. 14!/11! heh
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