Sattolo cycle: Difference between revisions
m (→version 1: simplified a DO loop.) |
|||
Line 417: | Line 417: | ||
end /*j*/ /* [↑] shuffle @ via Sattolo algorithm*/ |
end /*j*/ /* [↑] shuffle @ via Sattolo algorithm*/ |
||
$= /* [↓] build a list of shuffled items.*/ |
$= /* [↓] build a list of shuffled items.*/ |
||
do k=0 for |
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. */</lang> |
say ' Sattolo:' space($) /*stick a fork in it, we're all done. */</lang> |
||
{{out|output|text= when using the input of: [a null]}} |
{{out|output|text= when using the input of: [a null]}} |
Revision as of 17:43, 7 February 2017
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++
<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>
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
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; i-- > 1;) { 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; i--> 1;) { var j = Math.floor(Math.random() * i); var tmp = items[i]; items[i] = items[j]; items[j] = tmp; }
}</lang>
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]
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>
Python
Copied from Wikipedia:
<lang python>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</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; the array elements can be of any type. <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 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. */</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 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
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
Sidef
Modifies the array in-place: <lang ruby>func sattolo_cycle(arr) {
for i in (arr.len ^.. 1) { arr.swap(i, i.irand) }
}</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")