Sattolo cycle: Difference between revisions
→{{header|VBA}}: handling any type |
|||
Line 1,163: | Line 1,163: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
<lang vb>Private Sub Sattolo(Optional ByRef a As Variant) |
<lang vb>Private Sub Sattolo(Optional ByRef a As Variant) |
||
⚫ | |||
If Not IsMissing(a) Then |
If Not IsMissing(a) Then |
||
⚫ | |||
For i = UBound(a) To LBound(a) Step -1 |
For i = UBound(a) To LBound(a) Step -1 |
||
j = Int(i * Rnd) + 1 |
j = Int(i * Rnd) + 1 |
||
Line 1,175: | Line 1,175: | ||
Public Sub program() |
Public Sub program() |
||
Dim b As Variant, c As Variant, d As Variant, e As Variant |
Dim b As Variant, c As Variant, d As Variant, e As Variant |
||
Randomize |
|||
'imagine an empty array on this line |
'imagine an empty array on this line |
||
b = [{10}] |
b = [{10}] |
||
Line 1,180: | Line 1,181: | ||
d = [{10, 20, 30}] |
d = [{10, 20, 30}] |
||
e = [{11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}] |
e = [{11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}] |
||
f = [{"This ", "is ", "a ", "test"}] |
|||
Debug.Print "Before:" |
Debug.Print "Before:" |
||
Sattolo 'feeding an empty array ;) |
Sattolo 'feeding an empty array ;) |
||
Line 1,203: | Line 1,205: | ||
Debug.Print "After: "; |
Debug.Print "After: "; |
||
For Each i In e: Debug.Print i;: Next i: Debug.Print |
For Each i In e: Debug.Print i;: Next i: Debug.Print |
||
Debug.Print "Before:"; |
|||
For Each i In f: Debug.Print i;: Next i: Debug.Print |
|||
Sattolo f |
|||
Debug.Print "After: "; |
|||
For Each i In f: Debug.Print i;: Next i: Debug.Print |
|||
End Sub |
|||
</lang>{{out}}<pre>Before: |
|||
After: |
After: |
||
Before: 10 |
Before: 10 |
||
After: 10 |
After: 10 |
||
Before: 10 20 |
Before: 10 20 |
||
After: |
After: 20 10 |
||
Before: 10 20 30 |
Before: 10 20 30 |
||
After: |
After: 20 10 30 |
||
Before: 11 12 13 14 15 16 17 18 19 20 21 22 |
Before: 11 12 13 14 15 16 17 18 19 20 21 22 |
||
After: |
After: 16 18 19 17 12 20 22 14 11 13 15 21 |
||
Before:This is a test |
|||
After: testa is This |
|||
</pre> |
</pre> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
<lang zkl>fcn sattoloCycle(list){ // in place |
<lang zkl>fcn sattoloCycle(list){ // in place |
Revision as of 11:01, 31 December 2018
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).
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.
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>
- 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; } </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>
- 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; } </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>
- 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;
} </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 }
Free Pascal
<lang pascal>program sattolocycle; {$ifdef fpc}{$mode delphi}{$endif} uses math; var
a:Array of cardinal; i,j:integer; t:cardinal;
begin
randomize; a:=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]; i := length(a); while i > 0 do begin dec(i); j :=randomrange(Low(a),i); t:=a[i];a[i]:=a[j];a[j]:=t; write(a[i]:4); end;
end.</lang>
Output in Free Pascal: 2 14 12 13 0 1 15 9 7 6 3 18 10 4 16 5 19 8 11 17 Note output in Delphi differs because of different PRNG algorithms
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
<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>
Nim
<lang nim>import random
proc sattoloCycle[T](a: var openArray[T]) =
var j = 0 if a.len < 2: return for i in countdown(a.high, 1): j = rand(int.high) mod i swap a[j], a[i]
var a: seq[int] = @[] var b: seq[int] = @[10] var c: seq[int] = @[10, 20] var d: seq[int] = @[10, 20, 30] var e: seq[int] = @[11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
randomize()
a.sattoloCycle() echo "Shuffled a = ", $a
b.sattoloCycle() echo "\nShuffled b = ", $b
c.sattoloCycle() echo "\nShuffled c = ", $c
d.sattoloCycle() echo "\nShuffled d = ", $d
e.sattoloCycle() echo "\nShuffled e = ", $e</lang>
- Output:
Shuffled a = @[] Shuffled b = @[10] Shuffled c = @[20, 10] Shuffled d = @[20, 30, 10] Shuffled e = @[20, 21, 14, 17, 13, 18, 12, 22, 11, 15, 16, 19]
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
<lang perl>@a = 0..30;
printf "%2d ", $_ for @a; print "\n"; sattolo_cycle(\@a); printf "%2d ", $_ for @a; print "\n";
sub sattolo_cycle {
my($array) = @_; for $i (reverse 0 .. -1+@$array) { my $j = int rand $i; @$array[$j, $i] = @$array[$i, $j]; }
}</lang>
- Output:
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 26 27 28 29 30 18 5 9 25 3 23 12 2 26 21 16 4 11 15 20 1 27 10 29 7 6 28 24 8 13 17 19 0 14 30 22
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 values can be of any type (even mixed): integer, floating point, characters, ···
The values of 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 16output 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>
- 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
<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>
VBA
<lang vb>Private Sub Sattolo(Optional ByRef a As Variant)
Dim t As Variant, i As Integer If Not IsMissing(a) Then For i = UBound(a) To LBound(a) Step -1 j = Int(i * Rnd) + 1 t = a(i) a(i) = a(j) a(j) = t Next i End If
End Sub Public Sub program()
Dim b As Variant, c As Variant, d As Variant, e As Variant Randomize 'imagine an empty array on this line b = [{10}] c = [{10, 20}] d = [{10, 20, 30}] e = [{11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}] f = [{"This ", "is ", "a ", "test"}] Debug.Print "Before:" Sattolo 'feeding an empty array ;) Debug.Print "After: " Debug.Print "Before:"; For Each i In b: Debug.Print i;: Next i: Debug.Print Sattolo b Debug.Print "After: "; For Each i In b: Debug.Print i;: Next i: Debug.Print Debug.Print "Before:"; For Each i In c: Debug.Print i;: Next i: Debug.Print Sattolo c Debug.Print "After: "; For Each i In c: Debug.Print i;: Next i: Debug.Print Debug.Print "Before:"; For Each i In d: Debug.Print i;: Next i: Debug.Print Sattolo d Debug.Print "After: "; For Each i In d: Debug.Print i;: Next i: Debug.Print Debug.Print "Before:"; For Each i In e: Debug.Print i;: Next i: Debug.Print Sattolo e Debug.Print "After: "; For Each i In e: Debug.Print i;: Next i: Debug.Print Debug.Print "Before:"; For Each i In f: Debug.Print i;: Next i: Debug.Print Sattolo f Debug.Print "After: "; For Each i In f: Debug.Print i;: Next i: Debug.Print
End Sub
</lang>
- Output:
Before:After: Before: 10 After: 10 Before: 10 20 After: 20 10 Before: 10 20 30 After: 20 10 30 Before: 11 12 13 14 15 16 17 18 19 20 21 22 After: 16 18 19 17 12 20 22 14 11 13 15 21 Before:This is a test After: testa is This
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")