Knuth shuffle: Difference between revisions
→{{header|Uiua}}
| (28 intermediate revisions by 16 users not shown) | |||
Line 512:
print(a)
)</syntaxhighlight>
=={{header|Amazing Hopper}}==
<syntaxhighlight lang="c">
#include <basico.h>
algoritmo
v={},n=19
'0,1,2,3,4,5,6,7,8,9,"\t","\v","\v","A","B","C","D","E","F"' enlistar en 'v'
imprimir ("Original:\n[",v,"]\n\n")
imprimir (rareti( n, #(ceil(rand(n))), n, intercambiar en (v)),\
"Processed:\n[", v,"]\n" )
terminar
</syntaxhighlight>
{{out}}
<pre>
Original:
[0,1,2,3,4,5,6,7,8,9, ,
,
,A,B,C,D,E,F]
Processed:
[F,B, ,1,9,
,2,D,5,6,4,8,C,7,A,
,3,0,E]
</pre>
=={{header|AppleScript}}==
Line 1,079 ⟶ 1,107:
200 FOR I = 1 TO 25
210 PRINT A(I);" ";: NEXT I
220 END</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1
Line 1,101 ⟶ 1,128:
NEXT I%
PRINT</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
The [[#GW-BASIC|GW-BASIC]] solution works without any changes.
==={{header|GW-BASIC}}===
{{works with|PC-BASIC|any}}
{{works with|BASICA}}
{{works with|Chipmunk Basic}}
<syntaxhighlight lang="qbasic">100 CLS
110 RANDOMIZE TIMER
120 DIM CARDS(51)
130 PRINT "before:"
140 FOR L0 = 0 TO 51
150 CARDS(L0) = L0
160 PRINT STR$(CARDS(L0));" ";
170 NEXT L0
180 FOR L0 = 51 TO 0 STEP -1
190 CARD = INT(RND(1)*(L0+1))
200 IF CARD <> L0 THEN T = CARDS(CARD) : CARDS(CARD) = CARDS(L0) : CARDS(L0) = T
210 NEXT L0
220 PRINT : PRINT
230 PRINT "after:"
240 FOR L0 = 0 TO 51
250 PRINT STR$(CARDS(L0));" ";
260 NEXT L0
270 PRINT
280 END</syntaxhighlight>
==={{header|IS-BASIC}}===
Line 1,127 ⟶ 1,182:
320 NEXT
330 END DEF</syntaxhighlight>
==={{header|Minimal BASIC}}===
<syntaxhighlight lang="qbasic">100 REM Knuth shuffle
110 RANDOMIZE
120 DIM B(51)
130 PRINT "BEFORE:"
140 FOR L0 = 0 TO 51
150 LET B(L0) = L0
160 PRINT B(L0);" ";
170 NEXT L0
180 FOR L0 = 51 TO 0 STEP -1
190 LET C = INT(RND*(L0+1))
200 IF C <> L0 THEN 220
210 GOTO 250
220 LET T = B(C)
230 LET B(C) = B(L0)
240 LET B(L0) = T
250 NEXT L0
260 PRINT
270 PRINT
280 PRINT "AFTER:"
290 FOR L0 = 0 TO 51
300 PRINT B(L0);" ";
310 NEXT L0
320 PRINT
330 END</syntaxhighlight>
==={{header|OxygenBasic}}===
<syntaxhighlight lang="text">uses chaos
uses timeutil
seed=GetTickCount
Line 1,139 ⟶ 1,219:
j=irnd(1,100)
swap d[i],d[j]
next</syntaxhighlight>
==={{header|QB64}}===
Line 1,404 ⟶ 1,483:
=={{header|C++}}==
'''Compiler:''' [[g++]] (version 4.3.2 20081105 (Red Hat 4.3.2-7))
<syntaxhighlight lang="cpp" line="1">#include <cstdlib>
#include <algorithm>
#include <iterator>
Line 1,410 ⟶ 1,489:
template<typename RandomAccessIterator>
void knuthShuffle(RandomAccessIterator begin, RandomAccessIterator end) {
if(begin == end) {
return;
}
for(unsigned int n = end - begin - 1; n >= 1; --n) {
unsigned int k = rand() % (n + 1);
Line 1,665 ⟶ 1,747:
=={{header|EasyLang}}==
<syntaxhighlight
proc shuffle . a[] .
for
swap a[r] a[i]
.
.
arr[] = [ 1 2 3 ]
print arr[]
</syntaxhighlight>
Line 1,796 ⟶ 1,879:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import system'routines;
import extensions;
Line 1,808 ⟶ 1,891:
var max := self.Length;
for(int i := 0
{
var j := randomGenerator.
self.exchange(i,j)
Line 1,821 ⟶ 1,904:
public program()
{
var a := Array.allocate
console.printLine(a.randomize())
Line 1,827 ⟶ 1,910:
{{out}}
<pre>
</pre>
Line 2,177 ⟶ 2,260:
void local fn KnuthShuffle( mutArr as CFMutableArrayRef )
NSUInteger i, j, count
count = len(mutArr)
for i =
j = rnd(
MutableArrayExchangeObjects( mutArr, i, j )
next
end fn
Line 2,191 ⟶ 2,273:
CFMutableArrayRef mutArr
NSUInteger i
mutArr = fn MutableArrayWithObjects( @0, @1, @2, @3, @4, @5, @6, @7, @8, @9, NULL )
NSLog( @"Before shuffle: %@", fn ArrayComponentsJoinedByString( mutArr, @"" ) )
for i = 1 to
fn KnuthShuffle( mutArr )
NSLog( @"%@", fn ArrayComponentsJoinedByString( mutArr, @"" ) )
next
Line 2,503 ⟶ 2,585:
=={{header|Inform 6}}==
<syntaxhighlight lang="inform 6">[ shuffle a n i j tmp;
for (i = n - 1: i > 0: i--) {
j = random(i + 1) - 1;
tmp = a->j;
a->j = a->i;
a->i = tmp;
}
];</syntaxhighlight>
Line 2,647 ⟶ 2,728:
for (i = arr.length - 1; i > 0; i -= 1) {
rand = Math.floor((i + 1) * Math.random());//get random between zero and i (inclusive)
temp = arr[rand];
arr[rand] = arr[i]; //swap i (last element) with random element.
arr[i] = temp;
}
Line 2,674 ⟶ 2,755:
3,1,2 16460
3,2,1 16596</pre>
===ES6===
Line 4,435 ⟶ 4,515:
[15 1 51 20 45 29 43 8 13 3 41 35 11 7 37 9 38 17 32 48 40 25 44 18 14 50 42 34 2 21 12 4 26 19 23 24 28 46 36 10 5 16 6 49 22 33 39 47 31 52 30 27]
</pre>
=={{header|RPL}}==
Indexes of RPL lists and arrays start at 1.
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
DUP SIZE 2 '''FOR''' j
j RAND * CEIL
GET LAST OVER j GET PUT j ROT PUT
-1 '''STEP'''
≫ '<span style="color:blue">KNUTH</span>' STO
|
<span style="color:blue">KNUTH</span> ''( {items} ➝ {items} )'' <span style="color:grey">// works also with [items]</span>
for j from last downto 2 do:
let k = random integer in range 1 ≤ k ≤ j
swap items[j] with items[k]
|}
=={{header|Ruby}}==
Line 4,635 ⟶ 4,738:
[8,9,7,3,4,5,1,2,6]
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program knuth_shuffle;
setrandom(0);
array := [1..10];
print("Before shuffling:", array);
shuffle(array);
print("After shuffling: ", array);
proc shuffle(rw tup);
loop for i in [1..#tup-1] do
j := random [i+1..#tup];
[tup(i), tup(j)] := [tup(j), tup(i)];
end loop;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>Before shuffling: [1 2 3 4 5 6 7 8 9 10]
After shuffling: [7 8 1 10 2 5 6 9 4 3]</pre>
=={{header|Sidef}}==
Line 4,717 ⟶ 4,840:
<pre>1 2 3 4 5 6 7 8 9 10 ->
2 10 4 9 1 5 6 8 7 3</pre>
=={{header|SparForte}}==
As a structured script.
<syntaxhighlight lang="ada">#!/usr/local/bin/spar
pragma annotate( summary, "shuffle" );
pragma annotate( description, "Implement the Knuth shuffle (aka the" );
pragma annotate( description, "Fisher-Yates-Durstenfeld shuffle)" );
pragma annotate( description, "for an integer array (or, if possible, an array of any" );
pragma annotate( description, "type). The Knuth shuffle is used to create a random" );
pragma annotate( description, "permutation of an array." );
pragma annotate( description, "Note: spar has a built-in arrays.shuffle() function that does this." );
pragma annotate( see_also, "http://rosettacode.org/wiki/Knuth_shuffle" );
pragma annotate( author, "Ken O. Burtch" );
pragma license( unrestricted );
pragma restriction( no_external_commands );
procedure shuffle is
subtype array_element_type is string;
type magic_items is array(1..3) of array_element_type;
a : magic_items := ( "bell", "book", "candle" );
t : array_element_type;
k : integer;
begin
for i in reverse arrays.first( a ) .. arrays.last( a )-1 loop
k := integer( numerics.rnd( i+1 ) ) - 1 + arrays.first(a);
t := a(i);
a(i) := a(k);
a(k) := t;
end loop;
for i in arrays.first( a ) .. arrays.last( a ) loop
? a(i);
end loop;
end shuffle;</syntaxhighlight>
{{out}}
<pre>
$ spar shuffle
bell
candle
book
$ spar shuffle
candle
bell
book</pre>
=={{header|Stata}}==
Line 4,744 ⟶ 4,918:
=={{header|Swift}}==
Version that works in Swift 5.x and probably above. This version works for any mutable bidirectional collection although O(n) time complexity can only be guaranteed for a RandomAccessCollection where the index meets the Apple requirements for O(1) access to elements.
Also has the advantage that it implemented the algorithm as written at the top of this page i.e. it counts down from the end and picks the random element from the part of the array that has not yet been traversed.
<syntaxhighlight lang="swift">extension BidirectionalCollection where Self: MutableCollection
{
mutating func shuffleInPlace()
{
var index = self.index(before: self.endIndex)
while index != self.startIndex
{
// Note the use of ... below. This makes the current element eligible for being selected
let randomInt = Int.random(in: 0 ... self.distance(from: startIndex, to: index))
let randomIndex = self.index(startIndex, offsetBy: randomInt)
self.swapAt(index, randomIndex)
index = self.index(before: index)
}
}
}
var a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a.shuffleInPlace()
print(a)
</syntaxhighlight>
{{out}}
<pre>[1, 5, 2, 7, 6, 0, 9, 8, 4, 3]</pre>
'''Simple version (any Swift version):''' Extend Array with shuffle methods; using arc4random_uniform from C stdlib:
Line 4,912 ⟶ 5,113:
:DelVar D
:Return
=={{header|Transd}}==
<syntaxhighlight lang="Scheme">#lang transd
MainModule: {
// Define an abstract type Vec to make the shuffling
// function polymorphic
Vec: typedef(Lambda<:Data Bool>(λ d :Data()
(starts-with (_META_type d) "Vector<"))),
kshuffle: (λ v Vec() locals: rnd 0
(for n in Range( (- (size v) 1) 0) do
(= rnd (randr (to-Int n)))
(with tmp (cp (get v n))
(set-el v n (get v rnd))
(set-el v rnd tmp))
)
(lout v)
),
_start: (λ
(with v [10,20,30,40,50,60,70,80,90,100]
(lout "Original:\n" v)
(lout "Shuffled:")
(kshuffle v))
(lout "")
(with v ["A","B","C","D","E","F","G","H"]
(lout "Original:\n" v)
(lout "Shuffled:")
(kshuffle (cp v))
// Transd has a built-in function that performs the same
// kind of random shuffle
(lout "Built-in shuffle:")
(lout (shuffle v)))
)
}</syntaxhighlight>
{{out}}
<pre>
Original:
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Shuffled:
[20, 60, 100, 80, 70, 10, 50, 90, 40, 30]
Original:
["A", "B", "C", "D", "E", "F", "G", "H"]
Shuffled:
["G", "A", "D", "B", "F", "E", "C", "H"]
Built-in shuffle:
["A", "E", "C", "H", "G", "F", "B", "D"]
</pre>
=={{header|TUSCRIPT}}==
Line 4,963 ⟶ 5,213:
after:
19 4 49 9 27 35 50 11 2 29 22 48 33 15 17 42 47 28 41 18 34 21 30 39 3 8 23 12 36 26 0 46 7 44 13 14 16 40 10 25 31 32 51 24 20 38 45 6 43 1 5 37</pre>
=={{header|Uiua}}==
{{works with|Uiua|0.10.0-dev.1}}
Build pairs of indexes to be swapped then apply these as a fold.
<syntaxhighlight lang="Uiua">
Knuth ← ∧(⍜⊏⇌)≡(⊟⌊×⚂.)⇌↘1⇡⧻.
Knuth ⇡10
</syntaxhighlight>
Typical output:
<pre>
[3 0 6 5 7 8 4 1 9 2]
</pre>
=={{header|UNIX Shell}}==
Line 5,163 ⟶ 5,425:
9 13 8 18 10 1 17 15 0 16 14 19 3 2 7 11 6 4 5 12 </pre>
=={{header|V (Vlang)}}==
Updated to Vlang version 0.2.2
<syntaxhighlight lang="go">import rand
Line 5,193 ⟶ 5,455:
=={{header|Wren}}==
<syntaxhighlight lang="
var rand = Random.new()
| |||