# Shuffling a list

Several years ago, I wrote a list-shuffling handler which worked by traversing the list and swapping each item encountered with another chosen at random from all the items in the list. It was pretty fast, but — as was pointed out to me at the time — the number of possible permutations it produced could never be an exact multiple of the number of items in the list, so there was always a slight bias towards some permutations being more likely to occur than the others.

Ignoring the pseudo-randomness built into computer randomising systems anyway, the way to ensure that every permutation has an equal chance of happening is to eliminate items from the process as they’re placed. The Fisher-Yates Shuffle is a simple algorithm which randomises a list’s order “in place”. It’s like the shuffle I wrote, but the randomly chosen other item is never one of those which has already been placed:

``````on shuffle(myList)
-- Code posted by Mark J. Reed on the AppleScript-Users list in May 2005.
repeat with i from (count of myList) to 2 by -1
set j to random number from 1 to i
if i ≠ j then
set temp to item i of myList
set item i of myList to item j of myList
set item j of myList to temp
end if
end repeat
end shuffle

set aList to {}
repeat with i from 1 to 100
set end of aList to i
end repeat

shuffle(aList)
return aList
``````

In AppleScript, this might possibly be sped up slightly by referencing the list through a property in a script object, but the main bottleneck is actually the ‘random number’ function. In fact AppleScript’s ‘some’ specifier is so much faster that, even though it requires a couple of additional lists to be set up, its use knocks a staggering amount off the time:

``````on shuffle(myList)
script o
property lst : myList -- Original list.
property vals : myList's items -- Different list, but containing the same instances of the items.
property indices : {}
end script

-- Build a list of indices.
set len to (count myList)
repeat with i from 1 to len
set end of o's indices to i
end repeat

repeat with i from 1 to len
-- Randomly select an unused index.
set j to some integer of o's indices
-- Move the item at that index in the duplicate list to the current position in the original list.
set item i of o's lst to item j of o's vals
-- Eliminate the random index from further selection.
set item j of o's indices to missing value
end repeat
end shuffle

set aList to {}
repeat with i from 1 to 100
set end of aList to i
end repeat

shuffle(aList)
return aList
``````

If you’re running Sierra or later, there’s an ASObjC method which is faster still — although it returns a shuffled copy rather than shuffling the original list, if that’s relevant to you:

``````use AppleScript version "2.6" -- High Sierra (10.13) or later. (Actually OK in 10.12 too, but Sierra's AS version is the same as El Capitan's.)
use framework "Foundation"
use framework "GameplayKit" -- For the shuffledArray() function.

on shuffle(mylist)
set myArray to current application's class "NSArray"'s arrayWithArray:(mylist)
return (myArray's shuffledArray()) as list
end shuffle

set aList to {}
repeat with i from 1 to 100
set end of aList to i
end repeat

set shuffledList to shuffle(aList)
``````

You can also choose from several random sources when using ASObjC. This also allows you to run the code on earlier systems (10.11 and later) because GamePlayKit itself appeared before the shuffling method was added to NSArray.

Here’s Nigel’s last script using a Mersenne Twister source:

``````use AppleScript version "2.5" -- 10.11 or later
use framework "Foundation"
use framework "GameplayKit"

on shuffle(mylist)
set randomSource to current application's GKMersenneTwisterRandomSource's new()
set myArray to randomSource's arrayByShufflingObjectsInArray:mylist
return myArray as list
end shuffle

set aList to {}
repeat with i from 1 to 100
set end of aList to i
end repeat

set shuffledList to shuffle(aList)

``````

The shuffledArray() method uses a system-shared arc4random function, and I would’t be surprised if AppleScript is using the same (unless it’s still using something older and more predictable). So the above could also be written using GKARC4RandomSource instead of GKMersenneTwisterRandomSource. There are also seeding options.

Other sources you can use include GKLinearCongruentialRandomSource, GKShuffledDistribution, and GKGaussianDistribution.

That’s easy for you to say! ‘ :lol: ’

I’m not sure if you’re suggesting I was unclear, but all those classes are just subclasses of GKRandomSource, and you can simply swap one for the other in the code above.

And slightly off-topic, here’s a script for throwing a die 100 times:

``````use AppleScript version "2.5" --  (10.11) or later
use framework "Foundation"
use framework "GamePlayKit"

set theDist to current application's GKRandomDistribution's d6()
-- or:
--set theDist to current application's distributionForDieWithSideCount:6

set theList to {}
repeat 100 times
set end of theList to theDist's nextInt()
end repeat
return theList
``````

No. Sorry. I was just making a joke about the succession of very long words. Your post itself was very clear. Thanks for the additional information.

Hi, all. I explored a similar vanilla shuffling idea with some in an early 2016 post using letter characters.

``````
set staticAlpha to "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
set mutable to staticAlpha
set scrambled to {}

repeat count mutable times
tell mutable's some item to set {AppleScript's text item delimiters, scrambled's end} to {it, it}
set mutable to mutable's text item 1 & mutable's text item 2
end repeat

set text item delimiters to ""
set staticAlpha to scrambled as text

``````

I wrote the following today, as the previous version didn’t work with numbers. I haven’t tested either for speed or sampled their distribution, however, I think the general randomness will get successively better; it leaves the source more scrambled than it was found.

``````
property init : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} --or generate a set
set scrambled to {}
recurse(init)
set init to scrambled

on recurse(nums)
set chopped to {}
set my scrambled's end to nums's some item
repeat with anItem in nums
if anItem is not in my scrambled then set chopped's end to anItem as number
end repeat
if (count nums) > 1 then recurse(chopped)
end recurse

``````

–edited for minor optimizations

Hi Marc.

That’s an interesting way to do it. I think it’s OK for randomness.

As expected, with 100 items, it’s slightly not-as-fast as the some handler I posted, since it tests each randomly selected item against the items which have been selected so far to see if it’s been selected already. If it has, another selection has to be made. Mine only selects from items which haven’t been selected so far, so each item’s guaranteed only to be selected once. With 1000 items, yours runs for about half a minute before giving up with a “stack overflow” error, so presumably there’s a huge amount of recursion going on then.

Setting ‘scrambled’’s value before declaring it global only works because it’s a run handler variable in your script. In fact it doesn’t need to be declared at all in that case: the ‘my’ in the handler will find it anyway. But if its value’s set in an ordinary handler, it will need to have been declared as a global already somewhere above that point in the script.

I didn’t realize this, but it makes sense. Thanks.

Hello again, Nigel. I spotted a likely efficiency in your method; it appears that the third list isn’t needed. I took a few liberties:

``````
set numList to {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} --whatever
copy numList to indices --independent dupe

repeat with counter from 1 to count numList
set unused to my indices's some integer
set my numList's item counter to my indices's item unused
set my indices's item unused to null
end repeat

numList
``````

Hi Marc.

Yes. You can do that when the list you want to shuffle only contains integers.