Topic: Latin Squares and XOR (Page 1 of 1) Pages that link to <a href="http://ozoneasylum.com/backlink?for=33315" title="Pages that link to Topic: Latin Squares and XOR (Page 1 of 1)" rel="nofollow" >Topic: Latin Squares and XOR <span class="small">(Page 1 of 1)</span>\

 
warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

IP logged posted posted 10-07-2017 04:34 Edit Quote

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()




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')




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

warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

IP logged posted posted 10-11-2017 13:42 Edit Quote

T + XOR = F!

Transversals, yo.

code:
0 1 2 3       0 . . .   . 1 . .   . . 2 .   . . . 3
1 0 3 2  -->  . . 3 .   . . . 2   1 . . .   . 0 . .  ---+
2 3 0 1       . . . 1   . . 0 .   . 3 . .   2 . . .     |
3 2 1 0       . 2 . .   3 . . .   . . . 0   . . 1 .     |
                                                        |
0 1 2 3       0 . . .   . 1 . .   . . 2 .   . . . 3     |
2 3 0 1  <--  . . 0 .   . . . 1   2 . . .   . 3 . .  <--+
3 2 1 0       . . . 0   . . 1 .   . 2 . .   3 . . .
1 0 3 2       . 0 . .   1 . . .   . . . 2   . . 3 .




Find a bunch of transversals.
Play a rousing game of cover-all.
Flatten each trans to a single symbol.
Put it back together.
Boom. Orthogonal mate.

Try to find a transversal in this:

code:
0 1 2 3
1 0 3 2
2 3 1 0
3 2 0 1



Let's try some brute force on that little guy:

code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def cout_trans(cgrid,inds):

   ll=len(cgrid)

   bseq=['0','1','2','3','4','5','6','7',
         '8','9','A','B','C','D','E','F']

   for trow in range(ll):
      cme=' '
      for tcol in range(ll):
         if inds[trow]==tcol:
            cme=cme+' '+bseq[cgrid[trow][tcol]]
         else:
            cme=cme+' .'
      print(cme)
   print('')

   return


tgrid=[[0,1,2,3],
       [1,0,3,2],
       [2,3,1,0],
       [3,2,0,1]]

dr=len(tgrid)
tcount=0

for p in itertools.permutations(range(dr)):
   tset=set()
   for c in range(dr):
      tset.add( tgrid[c][p[c]]  )
   if len(tset)==dr:
      tcount=tcount+1
      cout_trans(tgrid,p)

print('tcount={}').format(tcount)



Toss other tgrids in there and see what it spits out
to screen.

When it comes to transversals and XOR, orthogonal mates
pop out all over the place. In most cases, brute force
the whole solution. Not the case with XOR. With XOR, one
transversal holds enough information for a complete orthogonal
mate solution.

With XOR, just one trans is all you need.

Here is a transversal using XOR=8 and the associated data:

code:
. . . . . 5 . .
  . . . . . . 7 .
  . . 0 . . . . .
  . 2 . . . . . .
  . . . . . . . 3
  . . . . 1 . . .
  6 . . . . . . .
  . . . 4 . . . .

  row=[0,1,2,3,4,5,6,7]
  col=[5,6,2,1,7,4,0,3]
  val=[5,7,0,2,3,1,6,4]



Try swapping that data around to make a permutation.
Something like:

code:
nrow=col
ncol=val
nval=row



You might be surprised (or not surprised) as to what
gets spit out.

One day I was playing with re-indexing transversal data
to the diagonal in the XOR grid. And I got some variables
mixed around. But I didn't think anything about it at
the time because I was still getting a valid orthogonal
mate. That was a real mind-bender. Once I realized, I
started mixing things up intentionally. More mind-bending.

Once you have a single transversal in an XOR grid, getting
a full orthogonal is wicked easy.

But how easy, or not easy, is it to get a transversal in
the first place? Well, when you are dealing with an XOR
grid base, not that hard at all. Depending on a few things.
Like your sense of humour.

warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

IP logged posted posted 10-13-2017 00:20 Edit Quote

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



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



Now we pick a 1.

code:
val=[0,1]
row=[0,2]
col=[0,3]

    1 2
  +----
1 | 0 3
3 | 2 1



Now for 2.

code:
val=[0,1,2]
row=[0,2,3]
col=[0,3,1]

    2
  +--
1 | 3



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 . .



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



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



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



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



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



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]



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 . . . . . . .



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




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



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



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

(Edited by warjournal on 10-13-2017 00:23)

(Edited by warjournal on 10-13-2017 00:24)



Post Reply
 
Your User Name:
Your Password:
Login Options: Remember Me On This Computer
 
Your Text:
Loading...
Options: Show Signature
Enable Slimies
Enable Linkwords

« BackwardsOnwards »

Show Forum Drop Down Menu