October 30th, 2010, 04:18 PM
pattern destroying shuffle?
I've searched high and low but thanks to the cardgames rage, Google is being pretty useless on this subject (while wikipedia and wolfram only cover pure random shuffling) so here goes.
I'm looking for the name of an algorithm, or researcher, or pretty much anything that might help me figure out a pattern-destructive shuffle algorithm.
To explain what I mean by that, some examples:
Let's say you have the following 10 numbered sequence:
Now let's say you want to shuffle them. A traditional approach is to simply randomize the positions of each element in the sequence:
0 1 2 3 4 5 6 7 8 9
Done, right? Well, so most of the shuffling pages (* bar music player song shuffling, see further down) tell me.
8 6 4 9 1 2 7 0 5 9
Except that I don't feel like it's actually optimally shuffled; 1 and 2 still follow each other immediately. 9 and 8 also follow each other (wrap-around) in that order (bi-directional).
So while it is surely 'shuffled' randomly, there's still remnants of a pattern left in there.
You could try interleaving them..
..but then I still have a pattern.
0 5 1 6 2 7 3 8 4 9
..looks a lot less like it has remnants of a pattern (for lack of knowing a term: 'pattern-y'). But how would I generate that? And -do- I want to generate that, or would I want to generate...
2 8 0 7 5 6 3 1 4 9
..which is also less pattern-y.. but which of the two is the least pattern-y? Is there an even less pattern-y sequence? I wouldn't know as I just jumbled the two by hand until they 'looked right'.
4 7 9 5 0 6 4 1 8 2
Now my guess is that music shuffling algorithms might be related.. but all the ones I have gone through pretty much limit themselves to a regular random shuffle with re-shuffling to make the first N songs not happen to be in the last N songs of the previous sequence, and similar techniques (e.g. http://blog.asmartbear.com/not-in-the-cards.html ).. where patterns are allowed just fine and there is no wrap-around of to the same sequence (one 'shuffled' sequence plays through, then a new 'shuffled' sequence is generated).
I'm not particularly looking for a prefab piece of code; if anybody has some key words I can search on.. name of an algorithm, name of a researcher, a paper, etc. I'm more than happy to go from there. Though if there is a prefab piece of code, I'm not one to decline a paste/link either.
Thanks in advance for any information that might help
Tags for this Thread
Click Here to Expand Forum to Full Width
This is a CodeGuru survey question.