Wednesday, September 18, 2019

#1 2019-09-01 05:34:59 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5005

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:

Applescript:

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:

Applescript:

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:

Applescript:

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.
use scripting additions

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)


NG

Offline

 

#2 2019-09-01 06:34:17 am

Shane Stanley
Member
From:: Australia
Registered: 2002-12-07
Posts: 5894

Re: Shuffling a list

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:

Applescript:

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

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.


Shane Stanley <sstanley@myriad-com.com.au>
www.macosxautomation.com/applescript/apps/
latenightsw.com

Offline

 

#3 2019-09-01 08:54:46 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5005

Re: Shuffling a list

Shane Stanley wrote:

GKARC4RandomSource instead of GKMersenneTwisterRandomSource […] GKLinearCongruentialRandomSource, GKShuffledDistribution, and GKGaussianDistribution.


That's easy for you to say!  ‘ lol


NG

Offline

 

#4 2019-09-01 06:42:10 pm

Shane Stanley
Member
From:: Australia
Registered: 2002-12-07
Posts: 5894

Re: Shuffling a list

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:

Applescript:

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

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


Shane Stanley <sstanley@myriad-com.com.au>
www.macosxautomation.com/applescript/apps/
latenightsw.com

Offline

 

#5 2019-09-02 12:40:38 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5005

Re: Shuffling a list

Shane Stanley wrote:

I'm not sure if you're suggesting I was unclear


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


NG

Offline

 

#6 2019-09-02 06:11:04 pm

Marc Anthony
Member
From:: Dallas, TX
Registered: 2006-04-27
Posts: 893

Re: Shuffling a list

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

Applescript:


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.

Applescript:


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

Last edited by Marc Anthony (2019-09-03 04:26:40 pm)

Offline

 

#7 2019-09-03 01:51:15 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5005

Re: Shuffling a list

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.


NG

Offline

 

#8 2019-09-03 04:22:46 pm

Marc Anthony
Member
From:: Dallas, TX
Registered: 2006-04-27
Posts: 893

Re: Shuffling a list

Nigel Garvey wrote:

'scrambled'...doesn't need to be declared at all in that case: the 'my' in the handler will find it..



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

Offline

 

#9 2019-09-03 07:01:45 pm

Marc Anthony
Member
From:: Dallas, TX
Registered: 2006-04-27
Posts: 893

Re: Shuffling a list

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:

Applescript:


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

Offline

 

#10 2019-09-04 02:28:38 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5005

Re: Shuffling a list

Hi Marc.

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


NG

Offline

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)