Sattolo cycle
The Sattolo cycle is an algorithm for randomly shuffling an array in such a way that each element ends up in a new position.
Implement the Sattolo cycle for an integer array (or, if possible, an array of any type).
Sattolo's algorithm is defined as follows (pseudo-code):
let items = the input array for each index i of items, from right to left, excluding the left-most one, do: let j = randomly chosen index below i swap items[i] with items[j]
This modifies the input array in-place. If that is unreasonable in your programming language, you may amend the algorithm to return the shuffled items as a new array instead.
Also note that the only difference between this and the Knuth shuffle, is that is chosen from the range , rather than . This is what ensures that every element ends up in a new position.
C#
<lang csharp>private static readonly Random Rand = new Random();
void sattoloCycle<T>(IList<T> items) {
for (var i = items.Count; i-- > 1;) { int j = Rand.Next(i); var tmp = items[i]; items[i] = items[j]; items[j] = tmp; }
}</lang>
J
This task currently needs a better description. That said, this achieves the result of the Sattolo cycle:
<lang J> (?~ #)</lang>
Java
<lang Java>private static final Random rng = new Random();
void sattoloCycle(Object[] items) {
for (int i = items.length; i-- > 1;) { int j = rng.nextInt(i); Object tmp = items[i]; items[i] = items[j]; items[j] = tmp; }
}</lang>
JavaScript
<lang JavaScript>function sattoloCycle(items) {
for (var i = items.length; i--> 1;) { var j = Math.floor(Math.random() * i); var tmp = items[i]; items[i] = items[j]; items[j] = tmp; }
}</lang>
Perl 6
This modifies the array passed as argument, in-place.
<lang perl6>sub sattolo-cycle (@array) {
for reverse 1 .. @array.end -> $i { my $j = (^$i).pick; @array[$j, $i] = @array[$i, $j]; }
}</lang>
Python
Copied from Wikipedia:
<lang python>from random import randrange
def sattoloCycle(items):
i = len(items) while i > 1: i = i - 1 j = randrange(i) # 0 <= j <= i-1 items[j], items[i] = items[i], items[j] return</lang>
REXX
This REXX example uses a zero-based array; the array elements can be of any type. <lang rexx>/*REXX program implements and displays a Sattolo shuffle for an array (of any type).*/ parse arg a; a=space(a) /*obtain optional arguments from the CL*/ if a= then a='-1 0 1 2 00 44 5 {6} 7 ~ 8 7.9 one two ¬¬ four +4 five six /\ [nine] Ace' say 'original:' a n=words(a) /*obtain the number of elements in list*/
do j=0 for n; @.j=word(a, j+1); end /*assign an element to the @. array. */
do i=0 to n-2; j=random(i, n-1) /*get a random integer between I & N-1.*/ parse value @.i @.j with @.j @.i /*swap two array elements, J is random.*/ end /*i*/
$=@.0 /*start with the first element in array*/
do k=1 for n-1; $=$ @.k; end /*append the next element in the array.*/
say ' Sattolo:' $ /*stick a fork in it, we're all done. */</lang>
- output when using the default input:
original: -1 0 1 2 00 44 5 {6} 7 ~ 8 7.9 one two ¬¬ four +4 five six /\ [nine] Ace Sattolo: 7 ~ {6} +4 44 5 00 7.9 two [nine] four one 0 -1 /\ ¬¬ five 8 Ace 1 2 six
TypeScript
<lang TypeScript>function sattoloCycle<T>(items: Array<T>): void {
for (let i = items.length; i--> 1;) { const j = Math.floor(Math.random() * i); const tmp = items[i]; items[i] = items[j]; items[j] = tmp; }
}</lang>
zkl
<lang zkl>fcn sattoloCycle(list){ // in place
foreach i in ([list.len()-1 .. 1,-1]){ list.swap(i,(0).random(i)); # 0 <= j < i } list
}</lang> <lang zkl>sattoloCycle([0..9].walk().copy()).println(); sattoloCycle("this is a test".split()).println();</lang>
- Output:
L(6,3,8,2,5,7,1,0,9,4) L("test","this","is","a")