Steev writes (via email to me):
"
Once simple way that works for >1 shuffles (but less than all of them) is to search the list for the first element != array[n-1], and re-position all the elements from array[0] to array[pos] at the end, but in reverse order.

You can repeat this,

* iteratively, with the same starting set
* continually, starting with the position you left off
* or recursively, with the resultant set from either method above

Depending on CPU constraints you should do all the above, generating an array of results, from which you can filter duplicates.
"

Hey to make it abit clearer, what do you define as shuffled.. for example the array is shuffled if two numbers are in a different place compared to the original?

This seems to mostly do it, but it is far from perfect. I haven't thought about the algorithm super hard, but I think there are possible permutations that it won't find because it ignores anything where intermediate steps during all the swapping have the same number next to itself. I don't know if that is ok for your purposes or not.

Let me know if the Python code is hard to follow/translate to your language of choice:

from random import choice
def do_swap(a,i1,i2):
a[i1], a[i2] = a[i2], a[i1]
def no_dupes_together_shuffle(a):
a = list(a) # copy the original instead of modifying in place
left1 = -1
right1 = -1
for i1 in range(len(a)):
current1 = a[i1]
if (i1+1)<len>
right1 = a[i1+1]
else:
right1 = -1
possible_swaps = []
left2 = -1
for i2 in range(i1+1, len(a)):
current2 = a[i2]
if (i2+1)<len>
right2 = a[i2+1]
else:
right2 = -1
if (current1!=left2 and
current1!=right2 and
current2!=left1 and
current2!=right1):
possible_swaps.append(i2)
left2 = current2
if len(possible_swaps):
do_swap(a,i1,choice(possible_swaps))
left1 = current1
return a

oh nuts, it mangled the indentation. I guess I'll try out ctrlv.it: http://ctrlv.it/id/MjM3ODA0

I decided that it could be treated as a search through state spaces, so wrote as solution as a fairly (VERY) clunky iterative search.
- make an open and a closed list
- push the starting state as a node on the open list
(a node has the current state of the solution so far)
- iterate:
-- if open list is empty, exit
-- else: remove a random one from the open list, expand the possible next states by adding a valid number from the source list to the solution so far
-- add all the valid nodes to the open list
-- if one of those next states is a valid solution, either return it add it to a list of solutions

Haven't really tried to optimise it yet, but it does the job.
A quirk of how it generates next "moves" means that if you return the first solution it's biased towards using up the variety of numbers early on in the output.

Interesting point about what you define as a "good" shuffle. I guess if you build up a full list you could sort them by distance and pick from the better results.

Because I am a huge nerd, I also wrote something to enumerate all valid shuffles. http://ctrlv.it/id/MjM3ODI3

Note that we are in Combinatorial Explosion Town so don't run this with a long array and expect it to finish before hell freezes over ;)

Thanks folks! Lots to mull on here!

What is a good shuffle? Well it depends, right? For the example edge case I gave [1,2,1,2,1], the only 'good' shuffle is no shuffle. In the general case though, I'd like an algorithm which gives me back a sensible amount of shuffling, assuming that is possible. So something any algorithm you can repeat a bunch of times to iteratively shuffle more and more is good - which relies on knowing that you aren't breaking the rules at each stage.

I am not keen on any solution which goes along the lines: generate all possible orders of the array elements, evaluate whether they meet the criteria, and pick randomly from the valid solutions. Time is on my side to an extent (and n in practice is fairly small) but that seems quite inelegant.

Steev: I like the look of your solution! I started along these lines myself, but never thought to reverse the subset you extract before pushing it back in, which gets you out of all kinds of horridness.

Ed: I *think* the problem with your solution is that you can enter a fail state early, but not know. Then get near the end and be unable to finish. But I'm not entirely sure - may have misunderstoof.

Mike: It's kind of hard to see what your code is doing. Can you describe it briefly? It looks like you're picking a candidate which you can safely remove (its neighbours aren't the same), then reinserting somewhere safe. Is that right? The part that was confusing me was I couldn't figure out how the randomness was working - what 'from random import choice' means. I'm not a Python programmer though..

Ah no, the one thing mine doesn't do is hit dead ends, because it's traversing a tree of solutions, building up the resulting list as it goes and moving on to other branches if one fails.
The disadvantage of this is that it doesn't have a valid solution at each stage, but it does have a partial list that meets the "no matching neighbours" rule.

I played around with it to return all solutions, but it got very slow. It's guaranteed to find solutions if they exist and also (if you preserved the state of the search between requests) would be guaranteed to keep enumerating the solutions until they ran out, although it might need some work on where the randomness is injected for the order of solutions to be interesting.

I'll tidy it up and send you the code, for what it's worth. It feels a bit of a sledgehammer-to-crack-a-nut

Hmm actually, randomly picking from the "open" list instead of picking the first element has massively improved performance and quality of results. How odd!

Well, my first solution turned out to give really bad results for some inputs ([1,2,1,2] would never change, for instance).
So I tried something dumber. Well, 2 dumber ways.
First, I shuffle the array ignoring the neighbors restriction, then I iterate over it and when it finds a "bad" entry, it looks for something later in the list that fits there and swaps them.
If at some point while doing that it turns out the method isn't going to work, it bails and starts over.
If after some number of restarts it still hasn't got a valid shuffle, it tries a different dumb way.
Dumb way #2 iterates through the array, and for each item it checks if the section of the array starting at that point and going to the end can be reversed to get a valid order, then it flips a coin to see whether it should do it.
Both ways are pretty fast (depending on the input I guess) and the sorts of inputs that one is bad at, the other seems to be good at, so I think it's working out pretty well?

Here's the code I used: http://ctrlv.it/cpp/MjM3ODYz
It's in c++ this time with some example output at the bottom: (oops, just noticed a couple of the -1s in it should have used the INVALID #define, but you get the idea)

My first thought was pre-shuffle, then use a graph colouring algorithm of some form with that as input. So a bit like ExiteMike's "dumb way #1", but with dumbness dependent on algorithm used.

Thought about it a bit more, and if I had to do this sort of thing I'd probably try and shuffle like cards. So.. Take a find a sublist that can be removed without breaking the ordering requirements, find a place to put the sublist without breaking ordering requirements. Repeat n (tuneable for performance/quality) times.

Rather than writing clever algorithms for "find a sublist that can be removed" and "find a place to put the sublist" I'd just try positions randomly and throw them away (still incrementing towards n) if they won't work.

Maybe randomly decide to reverse the sublist too.

Won't be perfect, but I'd expect it to be both okay-ish (with high enough n), and as quick as you need it to be (with low enough n).

Hey folks!

So, it seems like there's some degree of agreement here: a generally good approach is to iterate through the array, and pick a random point to split the array, then move the split somewhere else. This is the basis of Steev's email, Mike's special_shuffle1 and Jonathan's suggestion. I'm gonna implement this, and experiment with various ways to pick the split point.

Ed: please send me your code! I'd really like to see what you did - the general approach sounds really useful.

I really appreciate the help! I usually love spending time pure CompSci problems like this, but I'm at the point with our game where I just don't have that time right now..

x

Two solutions:

1)
Pick a random entry from input list, add to a output list and remove from input list.
Pick another random entry from input list until you get something different from the previous value, add to output list and remove from input list
Repeat until you either succeed (input list empty) or fail (input list contains all same values as last value of output list)

2) Faster version of 1:
Sort the input list into bins by value. (bin structure= value, count)
Pick a random bin, add its value to the output list, decrement count.
Remove a bin when count = 0;
Pick another bin with a different value, add its value to output list, decrement count.
Repeat until success (no more bins) or fail (only one bin left with count > 1)

As far as I can see, you can prevent Steve's algorithm from getting into a fail state if you ensure that you don't start with countMostCommon > countAllTheRest+1. If at any point countMostCommon = countAllTheRest+1, you have to choose mostCommon, otherwise pick a random input that fulfils the normal criteria.

Cool, I think that would work and by ignoring the 'not 2 in a row' condition when mostCommon is chosen, the algorithm gracefully degrades to at least give you an output.

Great! Which one of you wants to write the pseudocode? ;)

http://ideone.com/Y2lbq