Creating a random or shuffled array with GameplayKit

Scripting Forums Code Exchange
#1

I spent some time learning how to create random and shuffled arrays with GameplayKit and found this topic to be a bit involved. So, I thought I would summarize what I’ve learned.

First, you should decide whether the randomization needs to be “cryptographically robust”. If so, GameplayKit should not be used.

Next, you need to select a random source. Games have particular requirements and, as a result, not all of the random sources are random in the lay sense of the term. However, GKARC4RandomSource and GKMersenneTwisterRandomSource are reasonably random, and they are probably the best choices in most circumstances.

Thirdly, you should decide whether you want to create a random or shuffled array–the primary distinction being that a random array can include duplicates and a shuffled array will not (provided the source array doesn’t include duplicates).

To shuffle an array, there are three basic options. At first glance the GKShuffledDistribution class seems a good choice but is slow in my testing. The second and third options are similar and are demonstrated below:

use framework "Foundation"
use framework "GameplayKit"
use scripting additions

set theList to {"a", "b", "c", "d", "e"}

-- use arrayByShufflingObjectsInArray
set randomSource to current application's GKARC4RandomSource's new()
set shuffledArray to randomSource's arrayByShufflingObjectsInArray:theList
return shuffledArray as list

-- use shuffledArrayWithRandomSource
set theArray to current application's NSArray's arrayWithArray:theList
set randomSource to current application's GKARC4RandomSource's new()
set shuffledArray to theArray's shuffledArrayWithRandomSource:randomSource
return shuffledArray as list

If a randomized array is desired, the situation is both simpler and more complicated. The following comment from the documentation applies to games but applies equally well to a more generalized use:

In most cases, you need random numbers that are uniformly distributed across a specific range. For this task, use the GKRandomDistribution class.

The following is an example,

use framework "Foundation"
use framework "GameplayKit"
use scripting additions

set startNumber to 1
set endNumber to 10
set numberCount to 5
set randomNumbers to current application's NSMutableArray's new()
set randomDistribution to current application's GKRandomDistribution's distributionWithLowestValue:startNumber highestValue:endNumber
repeat numberCount times
	randomNumbers's addObject:(randomDistribution's nextInt())
end repeat
return randomNumbers as list

The above script does not specify a random source and that’s because distributionWithLowestValue:highestValue: defaults to GKARC4RandomSource. To designate a random source:

use framework "Foundation"
use framework "GameplayKit"
use scripting additions

set startNumber to 1
set endNumber to 10
set numberCount to 5
set randomNumbers to current application's NSMutableArray's new()
set randomSource to current application's GKMersenneTwisterRandomSource's new()
set randomDistribution to current application's GKRandomDistribution's alloc()'s initWithRandomSource:randomSource lowestValue:1 highestValue:10
repeat numberCount times
	randomNumbers's addObject:(randomDistribution's nextInt())
end repeat
return randomNumbers as list

A simple question is how to randomize an existing array directly, and I couldn’t find an easy answer to that. So, I created an array of random numbers and applied those random numbers to the source array. For example,

use framework "Foundation"
use framework "GameplayKit"
use scripting additions

set theList to {"a", "b", "c", "d", "e"}
set theArray to current application's NSArray's arrayWithArray:theList
set arrayCount to theArray's |count|()
set randomItems to current application's NSMutableArray's new()
set randomDistribution to current application's GKRandomDistribution's distributionWithLowestValue:0 highestValue:(arrayCount - 1)
repeat arrayCount times
	set randomItem to theArray's objectAtIndex:(randomDistribution's nextInt())
	randomItems's addObject:randomItem
end repeat
return randomItems as list

A final comment should be made concerning basic AppleScript. The “random number” command can be used to get a random number, and the “some” reference form will randomly return an item from a list. Both of these are easy to implement and reasonably quick, and they will satisfy in most situations. However, as far as I am aware, there is not a direct method to shuffle a list with basic AppleScript

A MacScripter thread on this topic can be found here

An informative page from the GameplayKit documentation can be found here

1 Like
#2

Hi @peavine. There’s a discussion on doing this (and a mention of GamePlayKit) here.

#3

Thanks Nigel. I tested your second script (which uses the some reference form) and it worked well. I ran a timing test with a list of 1000 numbers, and your script finished in 14 milliseconds compared with 2 milliseconds for the GameplayKit solution. However, this does not consider the time it takes initially to load GameplayKit, which can be substantial.

BTW, in my discussion in post 1, I did not mention NSArray’s shuffledArray method, which might seem an obvious choice. This method uses the sharedRandom random source, which is not very random (at least in a technical sense), and it’s no faster than the more-random alternatives. That’s why I skipped it.

#4

Thanks peavine. Looking at it again today, I think a hybrid of it with Mark’s and Marc’s ideas in that topic would be a better vanilla solution. It makes no discernable difference with modest numbers of items, but gains a definite speed advantage as the numbers increase:

on shuffle(myList)
	script o
		property lst : myList -- Original list.
		property indices : my lst's items -- Different list containing the same items.
	end script
	
	-- Replace the items in the already full-sized index list with indices.
	set len to (count o's lst)
	repeat with i from 1 to len
		set item i of o's indices to i
	end repeat
	
	repeat with i from len to 1 by -1
		-- Randomly select an unused index.
		set j to some integer of o's indices
		-- Swap the item at that index with the item at i.
		set v to o's lst's item i
		set o's lst's item i to o's lst's item j
		set o's lst's item j to v
		-- Eliminate index i from further consideration.
		set item i 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
1 Like
#5

Nigel. I tested your new shuffle script and the result was 10 milliseconds, as compared with the earlier result of 14 milliseconds. The test list contained 1000 consecutive numbers starting at the number 1, and the time it took to create this list was not included in the timing result.

I decided to test how long it would take to randomize the same list. The ASObjC script was the one included in my post 1 above, and the basic AppleScript is included below. The results were:

Basic AppleScript - 1 millisecond
ASObjC Script - 82 milliseconds

It should be noted, however, that using the ASObjC script to randomize an array of 20 items took only 2 milliseconds. Also, just as a matter of passing interest, I looked at the documentation to see how random the “some” reference form is, but I couldn’t find any information. I’m sure it’s fine for our needs.

The basic AppleScript was:

-- untimed code
set theList to {}
repeat with i from 1 to 1000
	set end of theList to i
end repeat

-- timed code
set randomList to getRandomList(theList, 1000)
on getRandomList(aList, randomListCount)
	script o
		property theList : aList
		property randomList : {}
	end script
	repeat randomListCount times
		set the end of o's randomList to some item of o's theList
	end repeat
	return o's randomList
end getRandomList
#7

The following is an example of a script in which GameplayKit might be of use. The script returns a password and does so by creating three random arrays of letters, numbers, and special characters. These arrays are merged and the resulting array shuffled. The timing result with GameplayKit in memory was 2 milliseconds.

use framework "Foundation"
use framework "GameplayKit"
use scripting additions

set thePassword to getPassword(8, 2, 2) -- parameters are letters, numbers, special characters

on getPassword(letterCount, numberCount, specialCharacterCount)
	set theLetters to characters of "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
	set theNumbers to characters of "123456789"
	set theSpecialCharacters to characters of "@#$%&"
	set randomLetters to getRandomCharacters(theLetters, letterCount)
	set randomNumbers to getRandomCharacters(theNumbers, numberCount)
	set randomSpecialCharacters to getRandomCharacters(theSpecialCharacters, specialCharacterCount)
	randomLetters's addObjectsFromArray:randomNumbers
	randomLetters's addObjectsFromArray:randomSpecialCharacters
	set randomSource to current application's GKARC4RandomSource's new()
	set randomCharacters to randomLetters's shuffledArrayWithRandomSource:randomSource
	return randomCharacters as list as text
end getPassword

on getRandomCharacters(theCharacters, theCount)
	set theCharacters to current application's NSArray's arrayWithArray:theCharacters
	set characterCount to theCharacters's |count|()
	set randomCharacters to current application's NSMutableArray's new()
	set randomDistribution to current application's GKRandomDistribution's distributionWithLowestValue:0 highestValue:(characterCount - 1)
	repeat theCount times
		set randomCharacter to theCharacters's objectAtIndex:(randomDistribution's nextInt())
		randomCharacters's addObject:randomCharacter
	end repeat
	return randomCharacters
end getRandomCharacters