Sattolo cycle: Difference between revisions
(Added Sidef) |
m (→version 1: recode the algorithm to the new specification, used the test cases for verification, add/changed comments.) |
||
Line 131: | Line 131: | ||
This REXX example uses a zero-based array; the array elements can be of any type. |
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).*/ |
<lang rexx>/*REXX program implements and displays a Sattolo shuffle for an array (of any type).*/ |
||
parse arg a |
parse arg a /*obtain optional arguments from the CL*/ |
||
say 'original:' space(a) /*display the original list of items.*/ |
|||
⚫ | |||
n=words(a) /*obtain the number of elements in list*/ |
n=words(a) /*obtain the number of elements in list*/ |
||
do j=0 for n; @.j=word(a, j+1); end /*assign an element to the @. array. */ |
do j=0 for n; @.j=word(a, j+1); end /*assign an element to the @. array. */ |
||
/* [↑] build an array of given items. */ |
|||
do i= |
do i=n-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.*/ |
parse value @.i @.j with @.j @.i /*swap two array elements, J is random.*/ |
||
end /*i*/ |
end /*i*/ /* [↑] shuffle @ via Sattolo algorithm*/ |
||
$= |
$= /* [↓] build a list of shuffled items.*/ |
||
do k= |
do k=0 for n; $=$ @.k; end /*append the next element in the array.*/ |
||
say ' Sattolo:' $ |
say ' Sattolo:' space($) /*stick a fork in it, we're all done. */</lang> |
||
{{out|output|text= when using the |
{{out|output|text= when using the input of: [a null]}} |
||
<pre> |
<pre> |
||
⚫ | |||
original: -1 0 1 2 00 44 5 {6} 7 ~ 8 7.9 one two ¬¬ four +4 five six /\ [nine] Ace |
|||
Sattolo: |
|||
Sattolo: 7 ~ {6} +4 44 5 00 7.9 two [nine] four one 0 -1 /\ ¬¬ five 8 Ace 1 2 six |
|||
</pre> |
|||
{{out|output|text= when using the input of: <tt> 10 </tt>}} |
|||
<pre> |
|||
original: 10 |
|||
Sattolo: 10 |
|||
</pre> |
|||
{{out|output|text= when using the input of: <tt> 10 20 30 </tt>}} |
|||
<pre> |
|||
original: 10 20 30 |
|||
Sattolo: 20 30 10 |
|||
</pre> |
|||
{{out|output|text= when using the input of: <tt> 11 12 13 14 15 16 17 18 19 20 21 22 </tt> |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
'''output''' when using the input of: <tt> -1 0 00 oNe 2.7 /\ [] +6e1 <nowiki> ~~~ </nowiki> </tt>}} |
|||
<pre> |
|||
original: -1 0 00 one 2.7 /\ [] +6e1 ~~~ |
|||
Sattolo: /\ 00 +6e1 0 ~~~ oNe -1 2.7 [] |
|||
</pre> |
</pre> |
||
Revision as of 18:43, 5 September 2016
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 with indices ranging from to , the algorithm can be defined as follows (pseudo-code):
for from last downto 1 do: let = random integer in range swap [] with []
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 , rather than . 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 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>
J
This task currently needs a better description. That said, this achieves the result of the Sattolo cycle:
<lang J> ({~ ?~@#)</lang>
Example use:
<lang J> ({~ ?~@#)
({~ ?~@#) ,10
10
({~ ?~@#) 10 20
10 20
({~ ?~@#) 10 20 30
30 10 20
({~ ?~@#) 11+i.12
20 15 11 12 17 14 13 18 19 22 21 16</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>
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>
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 /*obtain optional arguments from the CL*/ say 'original:' space(a) /*display the original list of items.*/ n=words(a) /*obtain the number of elements in list*/
do j=0 for n; @.j=word(a, j+1); end /*assign an element to the @. array. */ /* [↑] build an array of given items. */ do i=n-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 /*i*/ /* [↑] shuffle @ via Sattolo algorithm*/
$= /* [↓] build a list of shuffled items.*/
do k=0 for n; $=$ @.k; end /*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
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")