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
When I started looking into latin squares and sudoku, I came across an interesting problem. How do you shuffle a sequence so that each one is unique by position? [code] 0 1 2 3 1 2 3 0 [/code] If you were to use a regular random/shuffle function, the problem manifests like so: [code] 0 1 2 3 0 2 3 1 [/code] That's not good. Not good at all. The first position is the same and is completely invalid for my purposes. The whole point of shuffling is get get a certain kind of unique output. Let's say I have 8 digits and I want to shuffle the first 5. If one of those 5 comes back the same, then I only shuffled 4. If two come back the same, then I only shuffled 3. When I want something shuffled, I want it shuffled, damn it. For my purposes, I need that unique by position output. And I really need to avoid the possibility of everything coming back exactly the same (very bad). My first solution was to run a permutation, keep the valid ones in a list, and then pick one at random. It works, but seriously bogs down when trying to shuffle a sequence that is 16 long. That's a base perm of 16! and I don't want to do that. I don't even want to do 10!. And that's just once - not including the fact that I have to do it more than a few times. Imagine trying to do 10!*5. No. There has got to be a better way. After thinking about it for awhile, I decided on a daisy chain. [code] 0 1 2 3 1 2 3 0 01 12 23 30 len(chain)=[4] [/code] Using a daisy chain as such, I could pass a bunch of indices, shuffle them, and then put them back together (re-index): [code] a b c d e f g h 0 1 3 3 0 1 d a c b e f g h [/code] And I was happy with that for a few years. But I was doing some distribution tests a few weeks ago and some anomolies popped up. Nothing horrible, but enough to make me want to fix it. (I was aware of this years ago, but let it go at the time.) The problem is that there are far more valid solutions that should be included. Check this out: [code] 0 1 2 3 1 0 3 2 len(chain)=[2,2] [/code] With a full chain, a lot of solutions are excluded - and I mean a lot. Okay, time to start thinking about the possibility of smaller chains within the big chain. Mini-chains or sub-chains. My first stop was thinking about the basic possibilities. Something like this: [code] len(master_chain)=6 [2,2,2] [2,4] [6] [/code] I noticed, and it is easy to surmise, that the length of the sub-chains add up to the length of the master chain. I was sure that I wasn't the first one to think of this kind of problem. So I hit Google. Turns out that this problem is called [i]coin change[/i]. Damn near all hits were recursive and greedy. They did me no good. And then I found coinchanging.py by Kris Wright. [code] n=6 coins=[2,3,4,6] [2, 2, 2] [2, 4] [6] [/code] Simple, and bloody perfect. Notice that I did not include 1 or 5 in coins[]. This is because you can't have a chain with length 1. It's just not a chain with length=1. So, which one to pick? I mean, the probability of each chain can't be the same, right? Or can it? Time for some brute force to get some more data. I wrote it up to perm, take the valid solutions, and count the chains. I got this: [code] n=6 ([2, 2, 2], 15) ([2, 4], 30) ([3, 3], 40) ([4, 2], 60) ([6], 120) g00dcount=265 badcount=455 720 [/code] Okay... wtf? I know that those numbers are correct because I did a proper brute force. However, notice that my brute force shows [2,4] and [4,2] as seperate solutions. Even though both of those chains are identical, they are different. I'll see about explaining this later. What do those numbers mean? It means that a there is a 15:265 chance that the chain [2,2,2] will be picked. It means that there is a 40:265 chance that [3,3] will be picked. It means that there is a 30:265 chance that [2,4] will be picked. Or 60:265 that [4,2] will be picked. But, doing it coinchanger.py way since both chains are identical, 90:265 that [2,4] will be picked. Note: Going with full daisy chain ([6]) will yield only 120:265=45%. Like I mentioned earlier, a lot of valid solutions are being left out. Note: "g00dcount" was legit typo that I haven't bothered fixing. Note: ([6], 120) is actually (n-1)!. So now I have to figure out the probabilities that my brute force spits out. More staring at numbers, playing with formulas, and hardcore logical thinking. I live for this shit. Two sleepless nights later, I came up with this little ditty: [code] #!/usr/bin/env python from math import factorial as fact def nchoser_min1(n,r): # permutation without repetition # with a reduction in possibilities n=n-1 r=r-1 return fact(n)/fact(n-r) [/code] Using that, I can now calculate the probability of each chain. Let's take it for a spin with some hard coding. Note: I know that I'm not actually using formal N Chose R, AKA Combinations without Repetition. I am actually using Permutations without Repetition. [code] #!/usr/bin/env python from math import factorial as fact def nchoser_min1(n,r): # permutation without repetition # with reduction in possibilities n=n-1 r=r-1 return fact(n)/fact(n-r) print('n=6') print('') #[2, 2, 2] 15 a=nchoser_min1(6,2) b=nchoser_min1(4,2) c=nchoser_min1(2,2) print('[2, 2, 2] {}*{}*{}={}'.format(a,b,c,a*b*c)) gc0=a*b*c #[2, 4], 30 a=nchoser_min1(6,2) b=nchoser_min1(4,4) print('[2,4] {}*{}={}'.format(a,b,a*b)) gc1=a*b #[3, 3] 40 a=nchoser_min1(6,3) b=nchoser_min1(3,3) print('[3,3] {}*{}={}'.format(a,b,a*b)) gc2=a*b #[4, 2], 60 a=nchoser_min1(6,4) b=nchoser_min1(2,2) print('[4,2] {}*{}={}'.format(a,b,a*b)) gc3=a*b #[6], 120 a=nchoser_min1(6,6) print('[6] {}'.format(a)) gc4=a print('') print('g00dcount={}'.format(gc0+gc1+gc2+gc3+gc4)) [/code] And now side-by-side: [code] brute force n chose r n=6 n=6 ([2, 2, 2], 15) [2, 2, 2] 5*3*1=15 ([2, 4], 30) [2,4] 5*6=30 ([3, 3], 40) [3,3] 20*2=40 ([4, 2], 60) [4,2] 60*1=60 ([6], 120) [6] 120 g00dcount=265 g00dcount=265 [/code] So, yeah. The numbers add up every single time. I even played with some other hard code examples and those worked as well. Now I have the last piece and a plan-of-attack that can get me what I want. - Start with a chain length and pass it on to coinchanging.py. - Take each solution, perm when needed, and calculate the probability. - Pick a chain based on those probabilities. - Expand the chosen chain into groups. - Shuffle the whole thing all will-nilly. - Take each group in turn and daisy chain - Put it all back together. [code] n=6 0 1 2 3 4 5 based on probability, the chain picked is: [2,4] expand into mini-chains: 0 0 1 1 1 1 shuffle all willy-nilly: 1 0 1 1 1 0 take each mini-chain in turn and daisy chain shuffle put it all back together . 0 . . . 0 1 . 1 1 1 . 1 0 1 1 1 0 . 1 . . . 5 0 . 2 3 4 . 0 1 2 3 4 5 . 5 . . . 1 2 . 4 0 3 . 2 5 4 0 3 1 [2]=15 51 [4]=02 24 43 30 [/code] Ugh. I hope that makes sense. I have all of the pieces and I can start putting it all together. A little bit of a side-note. My use of the word "chain" is extremely lazy. Once I suss a few things out, I'll wax my nomenclature a bit better. In my next post, I'm going to clarify a few things. Stay tuned. edit: lol linkwords, not sure i can fix... edit: too funny, linkwords turning ( 'bracket' 6 'bracket' ) into (Phil) Medic! [small](Edited by [url=http://ozoneasylum.com/user/351]warjournal[/url] on 12-10-2018 16:09)[/small] [small](Edited by [url=http://ozoneasylum.com/user/351]warjournal[/url] on 12-10-2018 16:12)[/small] [small](Edited by [url=http://ozoneasylum.com/user/351]warjournal[/url] on 12-10-2018 16: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