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:

Code:

---

0 1 2 3 4 5 6 7 8 9

---

Now let's say you want to shuffle them. A traditional approach is to simply randomize the positions of each element in the sequence:

Code:

---

8 6 4 9 1 2 7 0 5 9

---

Done, right? Well, so most of the shuffling pages (* bar music player song shuffling, see further down) tell me.
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..

Code:

---

0 5 1 6 2 7 3 8 4 9

---

..but then I still have a pattern.

Now this..

Code:

---

2 8 0 7 5 6 3 1 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...

Code:

---

4 7 9 5 0 6 4 1 8 2

---

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


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

I'm not clear whether your intention is to write a "perfect music shuffler" or some sort of general purpose "pattern destroying" shuffler;

in the latter case, note that if we pick a random permutation of n numbers in [0,n-1] ( or equivalently and more correctly, if we sample a uniformly distributed random variable in the group of permutations of order n ) then the permutation "0 1 2 3 4 5 6 7 8 9" has the same probability of "4 7 9 5 0 6 4 1 8 2".
Therefore, "patterness" and "probability evenness" are two unrelated concepts.

Now, in physics ( and with a slightly different sense in information theory ) there is a measure of some basic notion of "patterness": the entropy. Hence, one option is to find a permutation that maximze a properly defined entropy. This might or might not solve your problem depending on what you exactly mean by "patterness". Indeed, we simply have recasted the problem into finding a suitable entropy definition for the system that satisfy your "patterness" condition.

This is a simpler problem in physics because there is (often) a physically natural notion of entropy. This is a simpler problem in information theory because there are natural notions of entropies in information systems ( Shannon entropy , Fisher entropy, and so on ... each with their own interpretations and relations ).

You need to make clear what you mean by "patterness" first, because there's no such universal concept.

Conversely, if your intent is to write a "perfect XXX shuffler", where XXX is some human related to-be-shuffled-thing, then "patterness" becomes a psychophysical property: you measure what makes a sequence of XXX's perceived as "patterned" by a prescribed population of humans in a prescribed environment, then you use those measurements to design random variables over sets of integer sequences that minimize the probability that a unifomly sampled human utters "hey, there's an annoying pattern there !".

Good points.

Yes, of course 0123456789 has the same probability as 4795064182; this would be not much different from a regular random shuffling.. sooner or later there will come a shuffle that will result in 0123456789. Let's discard that outright.

That leaves me with the remainder of your reply which rightfully points out that I have to define "patterness" and the situations in which that pattern would likely be the most disrupted.

I think the simplest analogy would be if you had a circle of lights, which would all light up in the order of the given sequence. If the sequence were 0123456789, then one would see a single light going round and round. If the sequence were 0516273849, then the light would jump from (first) one side of the circle to (second) roughly the opposite side, and (third) back... slowly appearing to go around in that fashion in large part due to the third and the first being in very close proximity.

So my thought right now is that each element in the non-shuffled sequence could be treated as a repelling force, with the repelling force between elements being the strongest in adjacent elements, and the weakest between elements furthest from eachother (in the circle of lights analogy.. the two lights opposite eachother).

Could we say that your notion of a "pattern destroying shuffle" is a shuffle where, given a circular sequence of objects, the objects are arranged such that no unordered pair of adjacent objects in the original sequence appears in the shuffled sequence?

We could, but it does go a bit beyond simple pairs..
e.g. input:
0123456789

skip-three:
0369258147

Then no pairs from the original are in the shuffled result... but it's still a clear pattern... whereas:
4795063182 (correction from previous which had two fours, typo)
... is not a clear pattern.

But yes, certainly if this were iteratively solved, the very first rule would be exactly as you said. Pairs from the input sequence should not appear in the output sequence either 'as is' or 'swapped'.

Quote:

---

Originally Posted by DivZero

Then no pairs from the original are in the shuffled result... but it's still a clear pattern... whereas:
4795063182 (correction from previous which had two fours, typo)
... is not a clear pattern.

---

That is really very vague though. It should be possible to find some equation that generates this "not a clear pattern" sequence, in which case we could argue that it is a clear pattern after all.

I think that the crux of the matter is that you have to define what you mean very clearly, otherwise your goal cannot be achieved. You also do not seem to have addressed this directly:

Quote:

---

Originally Posted by superbonzo

I'm not clear whether your intention is to write a "perfect music shuffler" or some sort of general purpose "pattern destroying" shuffler;

---

Right, which is why I started to ponder the nature of what makes the 'scrambled' pattern. I'm guessing if I can answer that, then answering the question of how I might go about generating it would be easier.

As for the question - the "pattern destroying" shuffler would be more correct; A music shuffler gets to take a shortcut by allowing the iteration N+1 of the sequence to be vastly different from sequence N, while in my case the sequence is fixed.

Quote:

---

Originally Posted by DivZero

Right, which is why I started to ponder the nature of what makes the 'scrambled' pattern. I'm guessing if I can answer that, then answering the question of how I might go about generating it would be easier.

As for the question - the "pattern destroying" shuffler would be more correct; A music shuffler gets to take a shortcut by allowing the iteration N+1 of the sequence to be vastly different from sequence N, while in my case the sequence is fixed.

---

The notion of randomness you're looking for is related to the so called Kolmogorov Complexity or algorithmic complexity.

But that's not the issue with music shuffling I think. What you want is not to have to hear a tune too often. This can be accomplish quite easily. It's just to "quarantaine" tunes that have been played recently.

Say you have 10 tunes. You divide them at random. Five forms a set and five are placed in a queue. You pick the next tune to be played at random from the set and the first tune in the queue is moved to the set. When a tune has been played it's placed last in the queue. Then repeat forever.

In this way tunes are picked at random among tunes that haven't been played for some time. And this probably is what a listener would call "at random" (although it's not a shuffle).

yeah, music is a different - but I thought potentially related - matter.. see earlier posts :)

I'll dig into Kolmogorov/algorithimic Complexity