Sattolo cycle

From Rosetta Code
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[edit]

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  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 is chosen from the range 0 j < i, rather than 0 j 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++[edit]

 
#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#[edit]

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[edit]

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

Haskell[edit]

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"
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[edit]

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

Java[edit]

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[edit]

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

Kotlin[edit]

// 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[edit]

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
Output:
[]
[10]
[20, 10]
[30, 10, 20]
[15, 17, 22, 18, 16, 19, 21, 11, 12, 13, 20, 14]

Perl 6[edit]

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[edit]

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)
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[edit]

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

Python[edit]

 
>>> 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[edit]

#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[edit]

version 1[edit]

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[edit]

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

Run BASIC[edit]

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
 
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[edit]

 
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[edit]

Modifies the array in-place:

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

TypeScript[edit]

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[edit]

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