Sattolo cycle: Difference between revisions

Content added Content deleted

Inline

Revision as of 20:18, 4 April 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.

Task

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  $\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 $j$ is chosen from the range 0 $\leq$ j < i, rather than 0 $\leq$ j $\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.

Related tasks

Knuth shuffle

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;

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

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>

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}

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

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