CloudFlare suffered a massive security issue affecting all of its customers, including Rosetta Code. All passwords not changed since February 19th 2017 have been expired, and session cookie longevity will be reduced until late March.--Michael Mol (talk) 05:15, 25 February 2017 (UTC)

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

Python[edit]

Copied from Wikipedia:

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

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;   the array elements can be of any type.

/*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 i=x-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 /*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:' space($) /*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 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

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