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 cpp>

1. include <ctime>
2. include <string>
3. include <iostream>
4. include <algorithm>

class cycle{ public:

   template <class T>
   void cy( T* a, int len ) {
       int i, j;
       show( "original: ", a, len );
       std::srand( unsigned( time( 0 ) ) );

       for( int i = len - 1; i > 0; i-- ) {
           do {
               j = std::rand() % i;
           } while( j >= i );
           std::swap( a[i], a[j] );
       }

       show( "  cycled: ", a, len ); std::cout << "\n";
   }

private:

   template <class T>
   void show( std::string s, T* a, int len ) {
       std::cout << s;
       for( int i = 0; i < len; i++ ) {
           std::cout << a[i] << " ";
       }
       std::cout << "\n";
   }

}; int main( int argc, char* argv[] ) {

   std::string d0[] = { "" },
               d1[] = { "10" },
               d2[] = { "10", "20" };
   int         d3[] = { 10, 20, 30 },
               d4[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22 };
   cycle c;
   c.cy( d0, sizeof( d0 ) / sizeof( d0[0] ) );
   c.cy( d1, sizeof( d1 ) / sizeof( d1[0] ) );
   c.cy( d2, sizeof( d2 ) / sizeof( d2[0] ) );
   c.cy( d3, sizeof( d3 ) / sizeof( d3[0] ) );
   c.cy( d4, sizeof( d4 ) / sizeof( d4[0] ) );

   return 0;

} </lang>

Output:

original:
  cycled:

original: 10
  cycled: 10

original: 10 20
  cycled: 20 10

original: 10 20 30
  cycled: 30 10 20

original: 11 12 13 14 15 16 17 18 19 20 21 22
  cycled: 13 17 14 22 11 18 20 12 21 19 15 16

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>

FreeBASIC

<lang freebasic>' version 22-10-2016 ' compile with: fbc -s console ' for boundry checks on array's compile with: fbc -s console -exx

' sort from lower bound to the highter bound ' array's can have subscript range from -2147483648 to +2147483647

Sub sattolo_cycle(a() As Long)

   Dim As Long lb = LBound(a)
   Dim As ULong n = UBound(a) - lb +1
   Dim As ULong i, j

   Randomize Timer

   For i = n -1 To 1 Step -1
       j =Fix(Rnd * (i))       ' 0 <= j < i
       Swap a(lb + i), a(lb + j)
   Next

End Sub

' ------=< MAIN >=------

Dim As Long i, array(1 To 52)

For i = 1 To 52 : array(i) = i : Next

Print "Starting array from 1 to 52" For i = 1 To 52

   Print Using " ###";array(i);

Next : Print : Print

sattolo_cycle(array())

Print "After Sattolo_Cycle" For i = 1 To 52

   Print Using " ###";array(i);

Next : Print : Print

' empty keyboard buffer While InKey <> "" : Wend Print : Print "hit any key to end program" Sleep End</lang>

Output:

Starting array from 1 to 52
   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  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52

After Sattolo_Cycle
  40  48   7  25  32  17  44   4   8  13  18  47   5  29  10  20  49  39  11  51   3  21  46   2  38  16  28  37  12  50   1   9  52  19  22  30  36  27  45  15  24  23  33  41  14  31  43  26  35  34  42   6

J

The key "feature" of this algorithm is that it cannot generate some legal random permutations. For example, given a two element list, it will always reverse that list.

Implementation:

<lang J>sattolo=:3 :0

 for_i.}:i.-#y do.
   j=.?i
   y=. (<i,j) C. y
 end.
 y

) </lang>

Example use:

<lang J> sattolo

  sattolo ,10

10

  sattolo 10 20

20 10

  sattolo 10 20 30

30 10 20

  sattolo 11+i.12

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

Racket

<lang racket>#lang racket

although the shuffle is in-place, returning the shuffled vector makes

testing a little easier

(define (sattolo-shuffle v)

 (for ((i (in-range (sub1 (vector-length v)) 0 -1)))
   (define j (random i))
   (define tmp (vector-ref v i))
   (vector-set! v i (vector-ref v j))
   (vector-set! v j tmp))
 v)

(define (derangement-of? A B #:strict? (strict? #t))

 (match* (A B)
   [('() '()) #t]
   [((list a) (list a)) #:when strict? #t]
   [((list a _ ...) (list a _ ...)) #f]
   [((list _ as ...) (list _ bs ...))
    (derangement-of? as bs #:strict? #t)]
   [((vector as ...) (vector bs ...))
    (derangement-of? as bs #:strict? strict?)]))

(module+ test

 (require rackunit)

 (check-equal? (sattolo-shuffle (vector)) #())
 (check-equal? (sattolo-shuffle (vector 10)) #(10))
 (check-equal? (sattolo-shuffle (vector 'inky)) #(inky))

 (define v′ (sattolo-shuffle (vector 11 12 13 14 15 16 17 18 19 20 21)))

 v′
 
 (check-true (derangement-of? #(11 12 13 14 15 16 17 18 19 20 21) v′)))</lang>

Output:

'#(21 19 12 11 18 17 14 16 15 13 20)

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 /*obtain optional arguments from the CL*/ say 'original:' space(a) /*display the original list of items.*/ 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. */
                                                /* [↑]  build an array of given items. */
          do i=n-1 by -1 to 1;  j=random(0,i-1) /*get a random integer between 0 & I-1.*/
          parse value  @.i  @.j  with  @.j  @.i /*swap two array elements, J is random.*/
          end   /*i*/                           /* [↑]  shuffle @ via Sattolo algorithm*/

$= /* [↓] build a list of shuffled items.*/

          do k=0  for n;    $=$  @.k;   end     /*append the next element in the array.*/

say ' Sattolo:' space($) /*stick a fork in it, we're all done. */</lang>

output   when using the input of:   [a null]

original: 
 Sattolo: 

output   when using the input of:   10

original: 10
 Sattolo: 10

output   when using the input of:   10 20 30

original: 10 20 30
 Sattolo: 20 30 10

output   when using the input of:   11 12 13 14 15 16 17 18 19 20 21 22

original: 11 12 13 14 15 16 17 18 19 20 21 22
 Sattolo: 15 14 17 19 18 12 22 13 20 21 11 16

output   when using the input of:   -1 0 00 oNe 2.7 /\ [] +6e1 ~~~

original: -1 0 00 one 2.7 /\ [] +6e1 ~~~
 Sattolo: /\ 00 +6e1 0 ~~~ oNe -1 2.7 []

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

Sidef

Modifies the array in-place: <lang ruby>func sattolo_cycle(arr) {

   for i in (arr.len ^.. 1) {
       arr.swap(i, i.irand)
   }

}</lang>

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