Sattolo cycle

Sattolo cycle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The   Sattolo cycle   is an algorithm for randomly shuffling an array in such a way that each element ends up in a new position.

Task

Implement the Sattolo cycle for an integer array (or, if possible, an array of any type).

Specification

Given an array $items$ with indices ranging from $0$ to $last$, the algorithm can be defined as follows (pseudo-code):

for $i$ from last downto 1 do:
    let $j$ = random integer in range $0\leq j<i$
    swap $items$[$i$] with $items$[$j$]

Notes:

• It 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.
• The algorithm can also be amended to iterate from left to right, if that is more convenient.
• The only difference between this and the Knuth shuffle, is that $j$ is chosen from the range $0\leq j<i$, rather than $0\leq j\leq i$. This is what ensures that every element ends up in a new position, as long as there are at least two elements.

Test cases

Input array	Possible output arrays
[]	[]
[10]	[10]
[10, 20]	[20, 10]
[10, 20, 30]	[20, 30, 10] [30, 10, 20]
[11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]	39,916,800 possibilities. You'll know you have a correct one if it has the same elements as the input array, but none in their original place.

Related tasks

• Knuth shuffle

---

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>

Example use:

<lang J> ({~ ?~@#)

  ({~ ?~@#) ,10

10

  ({~ ?~@#) 10 20

10 20

  ({~ ?~@#) 10 20 30

30 10 20

  ({~ ?~@#) 11+i.12

20 15 11 12 17 14 13 18 19 22 21 16</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

version 1

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

version 2

<lang rexx>n=25 Do i=0 To n

 a.i=i
 b.i=i
 End

Call show ' pre' Do i=n to 1 By -1

 j=random(0,i-1)
 Parse Value a.i a.j With a.j a.i
 End

Call show 'post' Do i=0 To n

 If a.i=b.i Then
   Say i a.i '=' b.i
 End

Exit Show: ol=arg(1) Do i=0 To n

 ol=ol right(a.i,2)
 End

Say ol Return</lang>

Output:

 pre  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
post  3  4  8 18 14 21 20 13 10  1 25  7  2 24 12 23  5 11  6 22 16 19  9  0 15 17

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")