Sattolo cycle
Implement the Sattolo cycle for an integer array (or, if possible, an array of any type).
Sattolo cycle is use to shuffle an array ensuring each index is 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>
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")