# 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

 /*Abhishek Ghosh, 9th November 2017*/ #include<stdlib.h>#include<stdio.h>#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;}

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.

 /*Abhishek Ghosh, 9th November 2017*/ #include<stdlib.h>#include<stdio.h>#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;}

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

 #include <ctime>#include <string>#include <iostream>#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;}
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#

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;    }}

## 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 <> "" : WendPrint : Print "hit any key to end program"SleepEnd
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

import Control.Monad ((>=>), (>>=), forM_)import Control.Monad.Primitiveimport qualified Data.Vector as Vimport qualified Data.Vector.Mutable as Mimport 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" 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:

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

Example use:

   sattolo ''    sattolo ,1010   sattolo 10 2020 10   sattolo 10 20 3030 10 20   sattolo 11+i.1219 18 15 21 12 17 22 16 20 13 11 14

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

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

## Julia

Works with: Julia version 0.6
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 arrend @show sattolocycle!([])@show sattolocycle!([10])@show sattolocycle!([10, 20, 30])@show sattolocycle!([11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22])
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

// 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())}

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

function sattolo (items)    local j    for i = #items, 2, -1 do        j = math.random(i - 1)        items[i], items[j] = items[j], items[i]    endend 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
Output:
[]
[10]
[20, 10]
[30, 10, 20]
[15, 17, 22, 18, 16, 19, 21, 11, 12, 13, 20, 14]

## Perl 6

This modifies the array passed as argument, in-place.

sub sattolo-cycle (@array) {    for reverse 1 .. @array.end -> $i { my$j = (^$i).pick; @array[$j, $i] = @array[$i, $j]; }} ## Phix sequence cards = tagset(52)puts(1,"Before: ") ?cardsfor i=52 to 2 by -1 do integer r = rand(i-1) {cards[r],cards[i]} = {cards[i],cards[r]}end forputs(1,"After: ") ?cardsfor i=1 to 52 do if cards[i]=i then ?9/0 end ifend forif sort(cards)!=tagset(52) then ?9/0 end ifputs(1,"Sorted: ") ?sort(cards) 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 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;}  ## 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) ) 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  >>> 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]>>>  ## 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′))) 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.). /*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. */ 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 n=25Do i=0 To n a.i=i b.i=i EndCall 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 EndCall show 'post'Do i=0 To n If a.i=b.i Then Say i a.i '=' b.i EndExitShow:ol=arg(1)Do i=0 To n ol=ol right(a.i,2) EndSay olReturn 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  # Project : Sattolo cycle# Date : 2017/11/02# Author : Gal Zsolt (~ CalmoSoft ~)# Email : <[email protected]> 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] = hnext showsit() func showsit for i = 1 to n see sit[i] + " " next see nl  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  ## Run BASIC a$	= "123456789abcdefghijklmnopqrstuvwxyz"n	= len(a$)dim sit$(n)      '  hold area to stringglobal 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 changeend sub shoSit for i = 1 to n print sit$(i);" ";    next i    printend sub
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 

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

## Sidef

Modifies the array in-place:

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

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

## zkl

fcn sattoloCycle(list){	// in place   foreach i in ([list.len()-1 .. 1,-1]){      list.swap(i,(0).random(i));  # 0 <= j < i   }   list}
sattoloCycle([0..9].walk().copy()).println();sattoloCycle("this is a test".split()).println();
Output:
L(6,3,8,2,5,7,1,0,9,4)
L("test","this","is","a")