# 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.

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 ${\displaystyle \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 ${\displaystyle j}$ is chosen from the range 0 ${\displaystyle \leq }$ j < i, rather than 0 ${\displaystyle \leq }$ j ${\displaystyle \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.

## C

This is generic to the extreme, although the function is technically being fed strings, it can handle any type, as shown in the outputs below :

### Interactive and without hardcoded inputs

<lang C> /*Abhishek Ghosh, 9th November 2017*/

1. include<stdlib.h>
2. include<stdio.h>
3. include<time.h>

void sattoloCycle(void** arr,int count){ int i,j; void* temp;

if(count<2) return; for(i=count-1;i>=1;i--){ j = rand()%i; temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } }

int main(int argC,char* argV[]) { int i;

if(argC==1) printf("Usage : %s <array elements separated by a space each>",argV[0]); else{

               srand((unsigned)time(NULL));


sattoloCycle((void*)(argV + 1),argC-1);

for(i=1;i<argC;i++) printf("%s ",argV[i]); } return 0; } </lang> Output:

C:\rosettaCode>sattoloCycle.exe ""

C:\rosettaCode>sattoloCycle.exe 10
10
C:\rosettaCode>sattoloCycle.exe 10 20
20 10
C:\rosettaCode>sattoloCycle.exe 10 20 30
30 10 20
C:\rosettaCode>sattoloCycle.exe 11 12 13 14 15 16 17 18 19 20 21 22
16 17 11 12 13 20 22 14 15 21 18 19
C:\rosettaCode>sattoloCycle.exe s a t t o l o C y c l e
l o s a t c e t o l C y
C:\rosettaCode>sattoloCycle.exe 1 2.3 4.2 1 3 e r q t 2 1 oo 2.1 eds
1 2.1 2.3 q r eds 1 e 3 t 1 2 oo 4.2
C:\rosettaCode>sattoloCycle.exe totally mixed up random string ( 1 2.3 2 ) which will get even more { a 2 q.1 } mixed up.
mixed q.1 a 1 up ) 2 even { will ( } 2 more totally random get which string up. 2.3 mixed


### Non Interactive and with hardcoded inputs

Same code but with hardcoded integer arrays as in the task to show that the function can handle any type. <lang C> /*Abhishek Ghosh, 9th November 2017*/

1. include<stdlib.h>
2. include<stdio.h>
3. include<time.h>

void sattoloCycle(void** arr,int count){ int i,j; void* temp;

if(count<2) return; for(i=count-1;i>=1;i--){ j = rand()%i; temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } }

int main() { int i;

int a[] = {}; int b[] = {10}; int c[] = {10, 20}; int d[] = {10, 20, 30}; int e[] = {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22};

srand((unsigned)time(NULL)); sattoloCycle((void*)a,0);

printf("\nShuffled a = "); for(i=0;i<0;i++) printf("%d ",a[i]);

sattoloCycle((void*)b,1);

printf("\nShuffled b = "); for(i=0;i<1;i++) printf("%d ",b[i]);

sattoloCycle((void*)c,2);

printf("\nShuffled c = "); for(i=0;i<2;i++) printf("%d ",c[i]);

sattoloCycle((void*)d,3);

printf("\nShuffled d = "); for(i=0;i<3;i++) printf("%d ",d[i]);

sattoloCycle((void*)e,12);

printf("\nShuffled e = "); for(i=0;i<12;i++) printf("%d ",e[i]);

return 0; } </lang> Output:

Shuffled a =
Shuffled b = 10
Shuffled c = 20 10
Shuffled d = 20 30 10
Shuffled e = 13 18 14 20 17 15 21 19 16 12 22 11


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

## D

<lang D>import std.stdio;

void main() {

   auto items = [0,1,2,3,4,5];
sattoloCycle(items);
items.writeln;


}

/// The Sattolo cycle is an algorithm for randomly shuffling an array in such a way that each element ends up in a new position. void sattoloCycle(R)(R items) {

   import std.algorithm : swapAt;
import std.random : uniform;

   for (int i=items.length; i-- > 1;) {
int j = uniform(0, i);
items.swapAt(i, j);
}


}

unittest {

   import std.range : lockstep;
auto o = ['a', 'b', 'c', 'd', 'e'];

   auto s = o.dup;
sattoloCycle(s);
foreach (a, b; lockstep(o, s)) {
assert(a != b, "An element stayed in place unexpectedly.");
}


}</lang>

Output:

Several runs shown

[2, 4, 1, 5, 3, 0]
[3, 0, 4, 5, 1, 2]
[3, 5, 4, 1, 0, 2]
[5, 4, 3, 0, 2, 1]


## Factor

<lang factor>USING: arrays io kernel literals math math.ranges prettyprint random sequences ; IN: rosetta-code.sattolo-cycle

(sattolo) ( seq -- seq' )
   dup dup length 1 - 1 [a,b]
[ dup iota random rot exchange ] with each ;


sattolo ( seq -- seq/seq' )
   dup length 1 > [ (sattolo) ] when ;


{

   { }
{ 10 }
{ 10 20 }
{ 10 20 30 }
$[ 11 22 [a,b] >array ]  } [  [ "original: " write . ] [ "cycled: " write sattolo . ] bi nl  ] each</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: { 16 19 20 13 17 18 22 14 21 15 11 12 }  ## 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 ## Go <lang go> package main import ( "math/rand" "fmt" ) func main() { list := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} for i := 1; i <= 10; i++ { sattoloCycle(list) fmt.Println(list) } } func sattoloCycle(list []int) { for x := len(list) -1; x > 0; x-- { j := rand.Intn(x) list[x], list[j] = list[j], list[x] } } </lang> Output: [4 5 1 7 3 9 10 2 8 6] [7 9 5 1 2 3 4 8 6 10] [2 3 9 4 6 8 7 1 10 5] [6 2 10 1 8 4 5 9 7 3] [8 3 7 2 10 1 6 4 9 5] [7 5 1 4 9 2 3 10 6 8] [6 8 3 10 2 4 7 1 5 9] [1 6 8 7 9 5 4 2 3 10] [9 5 10 6 2 8 1 7 4 3] [7 3 1 10 4 2 8 6 5 9]  ## Haskell <lang haskell>import Control.Monad ((>=>), (>>=), forM_) import Control.Monad.Primitive import qualified Data.Vector as V import qualified Data.Vector.Mutable as M import System.Random.MWC type MutVec m a = M.MVector (PrimState m) a -- Perform an in-place shuffle of the vector, making it a single random cyclic -- permutation of its initial value. The vector is also returned for -- convenience. cyclicPermM :: PrimMonad m => Gen (PrimState m) -> MutVec m a -> m (MutVec m a) cyclicPermM rand vec = forM_ [1..M.length vec-1] upd >> return vec  where upd i = uniformR (0, i-1) rand >>= M.swap vec i  -- Return a vector that is a single random cyclic permutation of the argument. cyclicPerm :: PrimMonad m => Gen (PrimState m) -> V.Vector a -> m (V.Vector a) cyclicPerm rand = V.thaw >=> cyclicPermM rand >=> V.unsafeFreeze test :: Show a => [a] -> IO () test xs = do  let orig = V.fromList xs cyc <- withSystemRandom . asGenIO$ \rand -> cyclicPerm rand orig
putStrLn $"original: " ++ show orig putStrLn$ "  cycled: " ++ show cyc


main :: IO () main = do

 test ([] :: [()])
test [10 :: Int]
test [10, 20 :: Int]
test [10, 20, 30 :: Int]
test [11..22 :: Int]
-- Also works for other types.
test "abcdef"</lang>

Output:
$./sattolo original: [] cycled: [] original: [10] cycled: [10] original: [10,20] cycled: [20,10] original: [10,20,30] cycled: [20,30,10] original: [11,12,13,14,15,16,17,18,19,20,21,22] cycled: [13,14,16,11,17,20,18,21,22,15,19,12] original: "abcdef" cycled: "cfeabd"  ## 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-1; i > 0; i--) { 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-1; i > 0; i--) { var j = Math.floor(Math.random() * i); var tmp = items[i]; items[i] = items[j]; items[j] = tmp; }  }</lang> ## Julia Works with: Julia version 0.6 <lang julia>function sattolocycle!(arr::Array, last::Int=length(arr))  for i in last:-1:2 j = rand(1:i-1) arr[i], arr[j] = arr[j], arr[i] end return arr  end @show sattolocycle!([]) @show sattolocycle!([10]) @show sattolocycle!([10, 20, 30]) @show sattolocycle!([11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22])</lang> Output: sattolocycle!([]) = Any[] sattolocycle!([10]) = [10] sattolocycle!([10, 20, 30]) = [30, 10, 20] sattolocycle!([11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]) = [19, 20, 15, 11, 17, 18, 21, 22, 13, 16, 12, 14] ## Kotlin <lang scala>// version 1.0.6 fun <T> sattolo(items: Array<T>) {  for (i in items.size - 1 downTo 1) { val j = (Math.random() * i).toInt() val t = items[i] items[i] = items[j] items[j] = t }  } fun main(args: Array<String>) {  val items = arrayOf(11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22) println(items.joinToString()) sattolo(items) println(items.joinToString())  }</lang> Sample output: Output: 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22 22, 11, 19, 12, 21, 14, 18, 20, 17, 16, 13, 15  ## Lua <lang Lua>function sattolo (items)  local j for i = #items, 2, -1 do j = math.random(i - 1) items[i], items[j] = items[j], items[i] end  end math.randomseed(os.time()) local testCases = {  {}, {10}, {10, 20}, {10, 20, 30}, {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}  } for _, array in pairs(testCases) do  sattolo(array) print("[" .. table.concat(array, ", ") .. "]")  end</lang> Output: [] [10] [20, 10] [30, 10, 20] [15, 17, 22, 18, 16, 19, 21, 11, 12, 13, 20, 14] ## Modula-2 <lang modula2>MODULE SattoloCycle; FROM FormatString IMPORT FormatString; FROM RandomNumbers IMPORT Randomize,Random; FROM Terminal IMPORT WriteString,WriteLn,ReadChar; PROCEDURE SwapInt(VAR a,b : INTEGER); VAR t : INTEGER; BEGIN  t := a; a := b; b := t;  END SwapInt; TYPE  ARR = ARRAY[0..5] OF INTEGER;  VAR  buf : ARRAY[0..63] OF CHAR; items : ARR; i,j : INTEGER;  BEGIN  Randomize(0); items := ARR{0,1,2,3,4,5};   FOR i:=0 TO HIGH(items) DO j := Random(0,i); SwapInt(items[i], items[j]); END;   FOR i:=0 TO HIGH(items) DO FormatString(" %i", buf, items[i]); WriteString(buf) END;   ReadChar  END SattoloCycle.</lang> ## Objeck Translation of: Objeck <lang objeck>class Sattolo {  function : Main(args : String[]) ~ Nil { array := [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; SattoloCycle(array); array->ToString()->PrintLine(); }   function : SattoloCycle(items : Int[]) ~ Nil { each(i : items) { j := (Float->Random() * 100.0)->As(Int) % items->Size(); tmp := items[i]; items[i] := items[j]; items[j] := tmp; }; }  } </lang> Output: [9,8,4,5,10,1,2,6,3,7]  ## Objective-C <lang objc>#import <Foundation/Foundation.h> @interface NSMutableArray (SattoloCycle) - (void)sattoloCycle; @end @implementation NSMutableArray (SattoloCycle) - (void)sattoloCycle {  for (NSUInteger i = self.count-1; i > 0; i--) { NSUInteger j = arc4random_uniform(i); [self exchangeObjectAtIndex:i withObjectAtIndex:j]; }  } @end</lang> ## OCaml <lang ocaml>let sattolo_cycle arr =  for i = Array.length arr - 1 downto 1 do let j = Random.int i in let temp = arr.(i) in arr.(i) <- arr.(j); arr.(j) <- temp done</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>

## Phix

<lang Phix>sequence cards = tagset(52) puts(1,"Before: ") ?cards for i=52 to 2 by -1 do

   integer r = rand(i-1)
{cards[r],cards[i]} = {cards[i],cards[r]}


end for puts(1,"After: ") ?cards for i=1 to 52 do

   if cards[i]=i then ?9/0 end if


end for if sort(cards)!=tagset(52) then ?9/0 end if puts(1,"Sorted: ") ?sort(cards)</lang>

Before: {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:  {51,47,8,9,20,5,43,21,12,2,7,19,4,32,10,23,30,29,31,38,13,44,41,26,42,15,34,46,27,33,40,18,24,17,28,48,3,45,11,22,39,1,35,49,36,14,6,25,50,16,52,37}
Sorted: {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}


## PHP

<lang PHP>function sattoloCycle($items) {  for ($i = 0; $i < count($items); $i++) {$j = floor((mt_rand() / mt_getrandmax()) * $i);$tmp = $items[$i];
$items[$i] = $items[$j];
$items[$j] = $tmp; } return$items;


} </lang>

## PicoLisp

<lang PicoLisp>(seed (in "/dev/urandom" (rd 8)))

(de sattolo (Lst)

  (for (N (length Lst) (>= N 2) (dec N))
(let I (rand 1 (dec N))
(xchg (nth Lst N) (nth Lst I)) ) ) )


(let L (range 1 15)

  (println 'before L)
(sattolo L)
(println 'after L) )</lang>

Output:
before (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)
after (4 1 12 6 2 13 9 11 8 5 3 14 7 15 10)


## Python

<lang python> >>> from random import randrange >>> def sattoloCycle(items): for i in range(len(items) - 1, 0, -1): j = randrange(i) # 0 <= j <= i-1 items[j], items[i] = items[i], items[j]

>>> # Tests >>> for _ in range(10): lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] sattoloCycle(lst) print(lst)

[5, 8, 1, 2, 6, 4, 3, 9, 10, 7] [5, 9, 8, 10, 4, 3, 6, 2, 1, 7] [10, 5, 8, 3, 9, 1, 4, 2, 6, 7] [10, 5, 2, 6, 9, 7, 8, 3, 1, 4] [7, 4, 8, 5, 10, 3, 2, 9, 1, 6] [2, 3, 10, 9, 4, 5, 8, 1, 7, 6] [5, 7, 4, 6, 2, 9, 3, 10, 8, 1] [3, 10, 7, 2, 9, 5, 8, 4, 1, 6] [2, 6, 5, 3, 9, 8, 10, 7, 1, 4] [3, 6, 2, 5, 10, 4, 1, 9, 7, 8] >>> </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;   (to match the pseudo-code).

The array elements can be of any type (even mixed):   integer, floating point, characters, ···

The array elements are specified via the command line (C.L.). <lang rexx>/*REXX program implements and displays a Sattolo shuffle for an array (of any type).*/ parse arg a; say 'original:' space(a) /*obtain args from the CL; display 'em.*/

  do x=0 for words(a);  @.x=word(a, x+1);  end  /*assign all elements to the @. array. */
/* [↑]  build an array of given items. */
do #=x-1  by -1  to 1;  j=random(0, #-1)  /*get a random integer between 0 & I-1.*/
parse value @.#  @.j    with    @.j  @.#  /*swap two array elements, J is random.*/
end   /*j*/                               /* [↑]  shuffle @ via Sattolo algorithm*/


$= /* [↓] build a list of shuffled items.*/  do k=0 for x;$=$@.k; end /*k*/ /*append the next element in the array.*/  say ' Sattolo:' strip($) /*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
original: 10 20
Sattolo: 20 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

## Ring

<lang ring>

1. Project : Sattolo cycle

a = "123456789abcdefghijklmnopqrstuvwxyz" n = len(a) sit = list(n)

for i = 1 to n

   sit[i] = substr(a, i, 1)


next showsit() for i = n to 1 step -1

   j = floor(i * random(9)/10) + 1
h = sit[i]
sit[i] = sit[j]
sit[j] = h


next showsit()

func showsit

    for i = 1 to n
see sit[i] + " "
next
see nl


</lang> Output:

1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z
i v 3 c 7 x 6 5 4 n a b r t e f g 2 8 u m o p w q l j h 9 s d y k z 1


## Ruby

<lang ruby> > class Array > def sattolo_cycle! > (length - 1).downto(1) do |i|

• j = rand(i)

> self[i], self[j] = self[j], self[i] > end > self > end > end => :sattolo_cycle!

> # Tests > 10.times do

• p [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].sattolo_cycle!

> end [10, 6, 9, 7, 8, 1, 3, 2, 5, 4] [3, 7, 5, 10, 4, 8, 1, 2, 6, 9] [10, 3, 4, 8, 9, 7, 1, 5, 6, 2] [8, 7, 4, 2, 6, 9, 1, 5, 10, 3] [2, 7, 5, 10, 8, 3, 6, 9, 4, 1] [2, 10, 8, 6, 1, 3, 5, 9, 7, 4] [8, 5, 6, 1, 4, 9, 2, 10, 7, 3] [5, 4, 10, 7, 2, 1, 8, 9, 3, 6] [9, 8, 4, 2, 6, 1, 5, 10, 3, 7] [9, 4, 2, 7, 6, 1, 10, 3, 8, 5] => 10</lang>

## Run BASIC

<lang Runbasic>a$= "123456789abcdefghijklmnopqrstuvwxyz" n = len(a$) dim sit$(n) ' hold area to string global n for i = 1 to n ' put string in array  sit$(i) = mid$(a$,i,1)


next i

call shoSit ' show before change

for i = n to 1 step -1

   j		= int(i * rnd(1)) + 1
h$= sit$(i)
sit$(i) = sit$(j)
sit$(j) = h$


next i

call shoSit ' show after change end

sub shoSit

   for i = 1 to n
print sit\$(i);" ";
next i
print


end sub

</lang>

Output:
1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z
d c 5 e v 3 n 7 8 h r p 2 y j l s x q 6 f 9 o a u i w 4 1 m g z t k b 

## Scala

<lang Scala>def shuffle[T](a: Array[T]): Array[T] = {

 scala.util.Random.shuffle(a)
a


}</lang>

## SequenceL

<lang sequenceL> import <Utilities/Random.sl>; import <Utilities/Sequence.sl>;

sattolo(x(1), seed) := shuffle(x, seedRandom(seed), size(x));

shuffle(x(1), RG, n) := let next := getRandom(RG); in x when n <= 1 else shuffle(swap(x, n, next.Value mod (n - 1) + 1), next.Generator, n - 1);

swap(list(1), i(0), j(0)) := swapHelper(list, i, j, list[i], list[j]); swapHelper(list(1), i(0), j(0), vali(0), valj(0)) := setElementAt(setElementAt(list, i, valj), j, vali);

</lang>

## Sidef

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

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


}</lang>

## Smalltalk

Works with: GNU Smalltalk

<lang Smalltalk>SequenceableCollection extend [

   sattoloCycle
[1 to: self size-1 do:
[:a || b |
b := Random between: a+1 and: self size.
self swap: a with: b]]


]</lang> Modifies the collection in-place. Collections that don't support that, like strings, will throw an exception.

Use example: <lang Smalltalk>st> #() copy sattoloCycle () st> #(10) copy sattoloCycle (10 ) st> #(10 20) copy sattoloCycle (20 10 ) st> #(10 20 30) copy sattoloCycle (30 10 20 ) st> #(10 20 30) copy sattoloCycle (20 30 10 ) st> #(11 12 13 14 15 16 17 18 19 20 21 22) copy sattoloCycle (22 13 17 18 14 12 15 21 16 11 20 19 ) st> 'Sattolo cycle' asArray sattoloCycle asString 'yocS talcelto'</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")