OZONE Asylum
Forums
Server-Side Scripting - Oh my!
Unique Shuffle, Chaos-n-Chains
This page's ID:
33322
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
This all started because I wanted to do a unique shuffle by position. It can't be that difficult, right? My first solution was doing a perm, keeping the ones that I like, and picking one at random. Fine for small numbers, but I can get crazy sometimes. This route quickly became far to unweildly and infeasible. My next solution was to do a daisy chain. This little ditty: [code] 0 1 2 3 4 1 2 3 4 0 01 12 23 34 40 [/code] And I was happy for quite some time. Even though I was aware of a problem, I was happy. Now I want to fix that problem. That problem being this little guy: [code] 0 1 2 3 4 1 0 3 4 2 [/code] I did some brute force to get some data to work from. I took that data, thought it up, and nailed it. I even learned about the coin change problem along the way. A bit long-winded, but I was about to be happy again. Fast enough with larger sequences and easy enough to code. Happy day! As I was going about my crazy macak routine, I noticed something in my notes. It tickled my brain. "Hey, that looks familiar. I've seen that before. OMG I bet it would work!" And then my crazy got even macakier. Rather than dig it out of my archives, I re-wrote it in under an hour. When you see how simple the code is, you'll see why it didn't take long at all to code. Well before I was daisy chaining, I was playing a game of "Can Be, Can't Be, Has to Be". That right there was the start of my sudoku journey. I wasn't thinking in terms of unique shuffle by position; rather, I was taking more of a quantum approach. The problem looks like this: [code] 0 1 2 3 4 5 1 2 3 4 0 . [/code] What do you put in that last position? You can't put anything in there. It Can't Be any number. But if you take one step back and re-arrange it like so: [code] 0 1 1 2 2 3 3 4 4 [5, 0] 5 [0] [/code] Now, 4 Can Be 5 or 0. However, 5 Has to Be 0. I've seen this problem more than a few times with people trying to make sudoku grids or latin squares from scratch. Me? I solved it with one simple rule that I call "Minimum in Pool". Since 5 has the least amount of possibilities, pick from it's pool. And 4 will fall into place. [code] [code] 0 1 0 1 0 1 1 2 1 2 1 2 2 3 2 3 2 3 3 4 3 4 3 4 4 [5, 0] 4 [5] 4 5 5 [0] 5 0 5 0 0 1 2 3 4 5 1 2 3 4 5 0 [/code] Fire up your pools, remove self from pools, find all pools with minimum number of possibilities, pick one of those pools, pick from that pool, prune, and go again, No big deal. What got me thinking that this will work is the fact that you are picking from pools at random. There is no need to pick a particular chain sequence because they will happen incidently. The chains are a product of probability - not the other way around. Big rush to get the code running just so I could see the numbers. I was getting really sloppy towards the end. Here is a sample data set from my brute force: [code] n=7 [2, 2, 3], 48 3% [2, 3, 2], 72 4% [3, 2, 2], 90 5% [2, 5], 144 8% [5, 2], 360 16% [3, 4], 180 10% [4, 3], 240 13% [7], 720 38% g00dcount=1854 [/code] My newly re-coded Min Pool shuffler currently has very poor formatting, so I am providing a sample with manual formatting: [code] n=7 i=1000 [2, 2, 3], 29, 3% [2, 3, 2], 31, 3% [3, 2, 2], 43, 4% [2, 5], 65, 7% [5, 2], 191, 19% [3, 4], 97, 10% [4, 3], 151, 15% [7], 393, 39% len=8 [/code] I rounded the percentages (by hand), but damn close enough for me. Even with a mostly random algorithm, I am getting the kind of variation that I want. Yes! Happy dance for real this time! The chains are incidental. They just happen, and they happen close enough to the truth of brute force. Get it? Here is the code that does that, but the output is extremely sloppy: [code] #!/usr/bin/env python import random import copy def find_chains(aseq,bseq): keepme=0 findme=[] rlist=[] while aseq: if findme==[]: pcount=1 keepme=aseq.pop(0) findme=bseq.pop(0) else: t=aseq.index(findme) aseq.pop(t) findme=bseq.pop(t) pcount+=1 if keepme==findme: findme=[] rlist.append(pcount) return rlist def unique_shuffle(mpool): fpool=[] # build the pools for i in range(len(mpool)): t=copy.deepcopy(mpool) t.remove(mpool[i]) fpool.append(t) for i in range(len(mpool)): # find minimum length minl=len(mpool)+1 for p in fpool: if isinstance(p,list): t=len(p) if t<minl: minl=t # build list of minimums ml=[] for p in range(len(fpool)): if isinstance(fpool[p],list): if len(fpool[p])==minl: ml.append(p) # pick a pool a=random.choice(ml) # pick random from pool b=random.choice(fpool[a]) fpool[a]=b # prune for i in range(len(fpool)): if isinstance(fpool[i],list): if b in fpool[i]: fpool[i].remove(b) return fpool tl=list(range(7)) mlist=[] olist=[] for i in range(1000): x=unique_shuffle(tl) y=find_chains(copy.deepcopy(tl),copy.deepcopy(x)) if y not in mlist: mlist.append(y) olist.append(1) else: # it is already in mlist[] j=mlist.index(y) k=olist[j] olist[j]=k+1 ts=sum(olist) for i in range(len(mlist)): print(mlist[i],olist[i],float(olist[i])/float(ts) ) print('\nlen={}'.format(len(olist))) [/code] Look at how ridiculously simple that whole thing is. No crazy equations or convoluted acrobatics. Simple, yet powerful. And it is fast enough to where I can toss some monster sequences into it without grinding my teeth. There are a few things that I want to note about the above implementation, but for another day. Mistress Chaos. Manipulating patterns. Too much fun. Any questions? Pending any, I'm off to play. Woo!
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