Knuth shuffle: Difference between revisions

{{trans|Python}}

L(i) (x.len - 1 .< 0).step(-1)

V j = random:(0..i)

V x = Array(0..9)

knuth_shuffle(&x)

{{out}}

=={{header|360 Assembly}}==

{{trans|BBC BASIC}}

* Knuth shuffle 02/11/2015

KNUTHSH CSECT

YREGS

END KNUTHSH

{{out}}

<pre>

Runs on easy6502, which has a random number generated memory-mapped at zero page address <code>$FE</code> that updates after every instruction. Works on any array size up to and including 256 bytes. (The code I wrote here prior to this edit was much faster but only worked on arrays of exactly 256 bytes in size). The reason for this was that constraining a random number generator that can produce any 8-bit value to a subset is tricky, since just "rolling again" if out of range will eventually cause the program to lock up if it can't produce a value in range purely by chance. This method uses a bit mask that shifts right as the loop counter decreases to zero, which means that even when only a few bytes still need to be shuffled, the routine is just as quick as it was at the beginning.

define tempMask $ff

define range $00

end:

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program knuthshuffle64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

=={{header|ACL2}}==

(defun array-swap (name array i j)

array

(1- (first (dimensions name array)))

=={{header|Action!}}==

BYTE i

PrintE("Shuffled data:")

PrintTable(tab,size)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Knuth_shuffle.png Screenshot from Atari 8-bit computer]

=={{header|Ada}}==

This implementation is a generic shuffle routine, able to shuffle an array of any type.

type Element_Type is private;

type Array_Type is array (Positive range <>) of Element_Type;

procedure Generic_Shuffle (List : in out Array_Type) is

List(K) := T;

end loop;

An example using Generic_Shuffle.

with Generic_Shuffle;

Ada.Text_IO.Put(Integer'Image(Integer_List(I)));

end loop;

=={{header|Aime}}==

The shuffle function works on any type (the lists are heterogenous).

shuffle(list l)

{

}

}

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G}}

(

ENTIER (random * ABS (b-a+1) + (a<b|a|b))

a[j] := t

OD

[20]INT a;

FOR i FROM 1 TO 20 DO a[i] := i OD;

knuth shuffle(a);

print(a)

=={{header|AppleScript}}==

===Iteration===

set array to {}

end repeat

Example:

----

Better:

on shuffle(theList, l, r)

set listLength to (count theList)

set array to {"Alpha", "Bravo", "Charlie", "Delta", "Echo", "Foxtrot", "Golf", "Hotel", "India", "Juliett", "Kilo", "Lima", "Mike"}

-- Shuffle all items (1 thru -1).

{{output}}

''eg.''

When a large number of random indices is required, it can actually be faster to create a list of integers and select from these using AppleScript's 'some' specifier than to call the StandardAdditions' 'random number' function repeatedly. But a better solution since Mac OS X 10.11 is to use the system's GameplayKit framework:

use framework "Foundation"

use framework "GameplayKit"

return theList

----

===Functional composition===

-- knuthShuffle :: [a] -> [a]

end script

end if

{{Out}}

e.g.

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

=={{header|Arturo}}==

if 0=size arr -> return []

print knuth [10]

print knuth [10 20]

=={{header|AutoHotkey}}==

ahk forum: [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=133 discussion]

MsgBox % shuffle("1,2,3,4,5,6,7,8,9")

s .= "," . a%A_Index%

Return SubStr(s,2) ; drop leading comma

For Arrays:

[https://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array#6274381 (translated from)]

shuffled:=shuffle(toShuffle)

;p(toShuffle) ;because it modifies the original array

}

return a

=={{header|AutoIt}}==

Dim $a[10]

ConsoleWrite('array before permutation:' & @CRLF)

Next

EndFunc

{{out}}

This example shows how to shuffle such arrays.

The elements can be integers, floating-point numbers, or strings.

function shuffle(array, len, i, j, t) {

for (i = len; i > 1; i--) {

for (i = 1; i < len; i++) printf "%s ", array[i]

printf "%s\n", array[len]

=={{header|BASIC}}==

DIM cards(51) AS INTEGER

PRINT LTRIM$(STR$(cards(L0))); " ";

NEXT

{{out}}

==={{header|Applesoft BASIC}}===

As mentioned in the Sinclair ZX81 BASIC solution, for very small positive integer values, a string is a much more memory-efficient array, but here is an example of an array with numbers. Line <code>150</code> initializes and prints each element in the array. Line <code>190</code> performs the swap of the elements.

110 REM KNUTH SHUFFLE

120 :

210 PRINT A(I);" ";: NEXT I

220 END

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1

==={{header|BBC BASIC}}===

DIM pack%(cards%)

FOR I% = 1 TO cards%

PRINT pack%(I%);

NEXT I%

==={{header|IS-BASIC}}===

110 RANDOMIZE

120 NUMERIC ARRAY(1 TO 20)

310 IF CARD<>I THEN LET T=A(CARD):LET A(CARD)=A(I):LET A(I)=T

320 NEXT

==={{header|OxygenBasic}}===

uses chaos

uses timeutil

swap d[i],d[j]

next

==={{header|QB64}}===

Shuffle and make sure that number does not take its place<br/>

and between cells at least 10% ... Shuffle from Russia

a = 100: DIM d(a): x=0: k=0: t$=CHR$(9): RANDOMIZE TIMER 'Shuffle_RUS.bas

PRINT ,: FOR i = 1 TO a: d(i)=i: NEXT

IF d(i) = i THEN PRINT -d(i); ELSE PRINT d(i);

NEXT

==={{header|Sinclair ZX81 BASIC}}===

The program works with the unexpanded (1k RAM) ZX81.

20 LET A$=""

30 FOR I=1 TO 26

120 PRINT AT 0,I-1;CHR$ (CODE A$(I)+128)

130 PRINT AT 0,J-1;CHR$ (CODE A$(J)+128)

{{out}}

While the program is running, we will see something like this (using lower case as a stand-in for inverse video):

==={{header|True BASIC}}===

{{trans|BASIC}}

RANDOMIZE

PRINT LTRIM$(STR$(cards(L0))); " ";

NEXT L0

{{out}}

<pre>Same as BASIC entry.</pre>

This code requires a <tt>bc</tt> with long names; the test program also requires a <tt>bc</tt> with the <tt>print</tt> statement.

{{works with|OpenBSD bc}}

scale = 0

trash = shuffle(10)

"Shuffled array: "; trash = print_array(10)

{{out}}

<pre>Original array: 11, 22, 33, 44, 55, 66, 77, 88, 99, 110

BQN's arrays are immutable, but variable values can be changed using the `↩` symbol. This program repeatedly changes the array's value using under.

𝕊 arr:

l ← ≠arr

P ⟨10⟩

P ⟨10, 20⟩

[https://mlochbaum.github.io/BQN/try.html#code=S251dGgg4oaQIHsKICDwnZWKIGFycjoKICBsIOKGkCDiiaBhcnIKICB7CiAgICBhcnIg4oapIOKMveKMvijin6jigKJyYW5kLlJhbmdlIGwsIPCdlanin6niirjiio8pYXJyCiAgfcKo4oaVbAogIGFycgp9ClAg4oaQIOKAolNob3cgS251dGgKClAg4p+o4p+pClAg4p+oMTDin6kKUCDin6gxMCwgMjDin6kKUCDin6gxMCwgMjAsIDMw4p+p Try It!]

=={{header|Brat}}==

(a.length - 1).to 1 { i |

random_index = random(0, i)

}

=={{header|C}}==

This shuffles any "object"; it imitates <tt>qsort</tt> in the syntax.

#include <string.h>

}

free(temp);

Alternatively, using Durstenfeld's method (swapping selected item and last item in each iteration instead of literally shifting everything), and macro'd function declaration/definition:

#include <stdlib.h>

printf(" %d", x[i]);

return 0;

=={{header|C sharp|C#}}==

{

System.Random random = new System.Random();

T temp = array[i]; array[i] = array[j]; array[j] = temp;

}

=={{header|C++}}==

'''Compiler:''' [[g++]] (version 4.3.2 20081105 (Red Hat 4.3.2-7))

#include <algorithm>

#include <iterator>

}

}

The standard library provides this in the form of <code>std::random_shuffle</code>.

#include <vector>

std::random_shuffle(array, array + 9); // shuffle C-style array

std::random_shuffle(vec.begin(), vec.end()); // shuffle STL container

=={{header|Clojure}}==

(reduce (fn [v i] (let [r (rand-int i)]

(assoc v i (v r) r (v i))))

This works by generating a sequence of end-indices from n-1 to 1, then reducing that sequence (starting with the original vector) through a function that, given a vector and end-index, performs a swap between the end-index and some random index less than the end-index.

=={{header|CLU}}==

lo: int := array[T]$low(a)

hi: int := array[T]$high(a)

stream$puts(po, int$unparse(i) || " ")

end

{{out}}

<pre>7 9 2 3 4 8 1 6 5</pre>

=={{header|CMake}}==

# stores the result in a list.

function(shuffle var)

endforeach(i)

set("${var}" ${answer} PARENT_SCOPE)

message(STATUS "${result}")

# One possible output:

=={{header|COBOL}}==

PROGRAM-ID. knuth-shuffle.

GOBACK

=={{header|CoffeeScript}}==

{{trans|JavaScript}}

n = a.length

while n > 1

for key, val of counts

{{out}}

<pre>

=={{header|Common Lisp}}==

(loop for i from (length sequence) downto 2

do (rotatef (elt sequence (random i))

(elt sequence (1- i))))

This operates on arbitrary sequences, but will be inefficient applied to a list as opposed to a vector. Dispatching on type, and using an intermediate vector to hold the contents of list can make both cases more efficient (since the array specific case can use <code>aref</code> rather than <code>elt</code>):

(etypecase sequence

(list (nshuffle-list sequence))

do (rotatef (aref array (random i))

(aref array (1- i)))

=={{header|Crystal}}==

i = items.size-1

while i > 1

i -= 1

end

=={{header|D}}==

===Standard Version===

A variant of the Knuth shuffle is in the D standard library Phobos:

import std.stdio, std.random;

a.randomShuffle;

a.writeln;

{{out}}

<pre>[8, 9, 3, 1, 7, 5, 4, 6, 2]</pre>

===One Implementation===

This shuffles any collection that supports random access, length and swapping of items:

void knuthShuffle(Range)(Range r)

a.knuthShuffle;

a.writeln;

=={{header|Delphi}}==

=={{header|DWScript}}==

var

i, j, tmp : Integer;

tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp;

end;

=={{header|E}}==

for bound in (2..(array.size())).descending() {

def i := random.nextInt(bound)

array[i] := t

}

# value: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].diverge()

? shuffle(arr, entropy)

? arr

=={{header|EasyLang}}==

for i = len a[] downto 2

r = random i

call shuffle arr[]

print arr[]

=={{header|EchoLisp}}==

Remark- The native '''shuffle''' function implementation in EchoLisp has been replaced by this one.

Thx Rosetta Code.

'(adrien 🎸 alexandre 🚂 antoine 🍼 ben 📚 georges 📷 julie 🎥 marine 🐼 nathalie 🍕 ))

→ (antoine 🎥 🚂 marine adrien nathalie 🍼 🍕 ben 🐼 julie 📷 📚 🎸 alexandre georges)

=={{header|Egel}}==

import "prelude.eg"

import "random.ego"

def main = shuffle (fromto 1 9)

=={{header|Eiffel}}==

class

APPLICATION

end

{{out}}

<pre>

=={{header|Elena}}==

ELENA 4.x:

import extensions;

console.printLine(a.randomize())

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Erlang}}

def shuffle( inputs ) do

n = length( inputs )

Map.update(acc, k, 1, &(&1+1))

end)

{{out}}

=={{header|Erlang}}==

-module( knuth_shuffle ).

Item = lists:nth( random:uniform(N), Inputs ),

{lists:delete(Item, Inputs), [Item | Acc]}.

{{out}}

<pre>

=={{header|ERRE}}==

CONST CARDS%=52

PRINT

END PROGRAM

=={{header|Euphoria}}==

{{trans|BASIC}}

cards = repeat(0,52)

integer card,temp

for i = 1 to 52 do

printf(1,"%d ",cards[i])

=={{header|F_Sharp|F#}}==

This is the original Fisher-Yates shuffle as described by the link:

let FisherYatesShuffle (initialList : array<'a>) = // '

initialList.[index] // and return the original item

seq {(initialList.Length) .. -1 .. 1} // Going from the length of the list down to 1

Here's the modified Knuth shuffle which shuffles the original array in place

let Swap i j = // Standard swap

let item = lst.[i]

[0..(ln - 2)] // For all indices except the last

|> Seq.iter (fun i -> Swap i (rnd.Next(i, ln))) // swap th item at the index with a random one following it (or itself)

Example:

=={{header|Factor}}==

There is a <code>randomize</code> word already in the standard library. Implementation:

dup length [ dup 1 > ]

[ [ iota random ] [ 1 - ] bi [ pick exchange ] keep ]

=={{header|Fantom}}==

{

static Void knuthShuffle (List array)

echo (b)

}

=={{header|Forth}}==

: shuffle ( deck size -- )

create deck 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ,

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

implicit none

end subroutine Shuffle

=={{header|FreeBASIC}}==

' compile with: fbc -s console

' for boundry checks on array's compile with: fbc -s console -exx

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>Starting array

=={{header|Frink}}==

The built-in method <CODE><I>array</I>.shuffle[]</CODE> implements the Fisher-Yates-Knuth shuffle algorithm:

a = [1,2,3]

a.shuffle[]

=={{header|FunL}}==

res = array( a )

n = a.length()

res(i), res(r) = res(r), res(i)

=={{header|Gambas}}==

'''[https://gambas-playground.proko.eu/?gist=58402023fbdc617ce10f6a85db721105 Click this link to run this code]'''

Dim iTotal As Integer = 40

Dim iCount, iRand1, iRand2 As Integer

Next

Output:

<pre>

=={{header|GAP}}==

ShuffleAlt := function(a)

local i, j, n, t;

# One may also call the built-in random generator on the symmetric group :

Random(SymmetricGroup(10));

=={{header|Go}}==

implementing a Fisher–Yates shuffle.)

import (

}

fmt.Println(a)

To shuffle any type:

import (

shuffle(a)

fmt.Println(a)

{{out|Example output}} (of either program)

<pre>

=={{header|Groovy}}==

Solution:

if (list == null || list.empty) return list

def r = new Random()

}

list

Test:

println list

println shuffle(list)

println shuffle(list)

{{out}}

<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

=={{header|Haskell}}==

mkRands :: Int -> IO [Int]

knuthShuffle :: [a] -> IO [a]

or, as an alternative to making two indexed references into the list with '''(!!)''':

import Data.Bool (bool)

main :: IO ()

Examples of use of either of the two versions above:

[(0,10),(8,18),(2,12),(3,13),(9,19),(4,14),(7,17),(1,11),(6,16),(5,15)]</pre>

Function for showing intermediate results:

knuthShuffleProcess =

{{out}} Detailed example:

<pre>*Main> knuthShuffleProcess ['a'..'k']

"iebjhkcgfad"</pre>

An imperative implementation using arrays and the <code>ST</code> monad:

import Data.STRef

import Control.Monad

where len = length list

newAry :: (Int, Int) -> [a] -> ST s (STArray s Int a)

=={{header|Icon}} and {{header|Unicon}}==

The <tt>shuffle</tt> method used here can shuffle lists, record fields, and strings:

show(shuffle([3,1,4,1,5,9,2,6,3]))

show(shuffle("this is a string"))

every writes(!A," ")

write()

{{out}}

<pre>->ks

-></pre>

Note that the gloriously succinct 'standard' Icon shuffle:

every !A :=: ?A

is subtly biased.

=={{header|Inform 6}}==

for(i = n - 1: i > 0: i--)

{

a->i = tmp;

}

=={{header|J}}==

The input array is transformed to a rectangular array of indexes. By doing this all kinds of arrays can serve as input (see examples below). The process is imitated by using using a fold, swapping elements in a restricted part of this index-array in each fold step.

Example of a transformed input:

0 0 0 0 0 0

1 1 0 0 0 0

4 3 0 0 0 0

5 0 0 0 0 0

The last row is the index-array that has to be shuffled. The other rows have valid indexes in the first two columns. The second column has a randomized value <= value first column.

The index-swapping is done by the part:

Finally, the shuffled indexes select elements from the original array.

Alternatively, instead of creating a rectangular array, the swapping indices and the original data can be individually boxed.

With this approach, the data structure with the swapping indices and the original data could look like this:

+---+-+---+---+-+-----+

|4 2|3|2 1|1 0|0|abcde|

Note that we have the original data here, instead of indices to select all of its items. Note also that we have only a single value in a box where an item is being "swapped" with itself (this is required by J's cycle operation (<code>C.</code>)).

The resulting definition looks like this:

Note that here we did not wind up with a list of indices which we used to permute the original data set. That data set is permuted directly. However, it is in a box and we do have to remove it from that box.

Permuting the data directly, instead of permuting indices, has performance implications when the items being swapped are large, but see the note at the end of this entry for J for how you would do this operation in a "real" J program.

1 1 1

1 0 0

11 2 3

11 2 3

0 11 2

1 2 3

+--+---+----+---+

|aA|bbB|cC%$|dD@|

+--+----+---+---+

|aA|cC%$|dD@|bbB|

In J the shuffling of an arbitrary array can easily be implemented by the phrase

( ref http://www.jsoftware.com/jwiki/JPhrases/RandomNumbers ):

Applied on the former examples:

8 7 13 6 10 11 5 9 12

+----+---+--+---+

|cC%$|bbB|aA|dD@|

=={{header|Java}}==

public static final Random gen = new Random();

array[k] = temp;

}

=={{header|JavaScript}}==

===ES5===

var rand, temp, i;

for (var key in res) {

print(key + "\t" + res[key]);

Results in:

<pre>1,2,3 16619

====Mutating in-place swap====

// knuthShuffle :: [a] -> [a]

return test();

})();

{{Out}}

e.g.

====Non-mutating swap====

// knuthShuffle :: [a] -> [a]

// MAIN ---

return test();

{{Out}}

e.g.

=={{header|Joy}}==

(* Take the size of the array (without destroying it) *)

dup dup size

[second] map.</syntaxhighlight>

Using knuth-shuffle (file shuffle.joy):

[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

knuth-shuffle.</syntaxhighlight>

where program.jq is the following program:

# 52-card deck:

def deck:

task,

(deck|knuthShuffle | nwise(13) | implode)

{{out}}

<pre>

{{works with|Julia|0.6}}

for i in length(v):-1:2

j = rand(r, 1:i)

v = collect(1:20)

{{out}}

=={{header|Kotlin}}==

internal val gen = java.util.Random()

}

require(s.toSortedSet() == ia.toSet())

}

{{out}}

<pre>xdhsvtnumjgbywiqoapcelkrfz

=={{header|Lambdatalk}}==

{def shuffle

{shuffle {B}}

-> [z,t,q,w,c,n,a,u,r,y,i,s,f,d,g,m,h,x,b,e,k,p,l,o,j,v]

=={{header|Lasso}}==

fail_if(

#p1 < 1 or #p2 < 1 or

}

{{out}}

<pre>staticarray(9, 5, 6, 1, 10, 8, 3, 4, 2, 7)</pre>

=={{header|Liberty BASIC}}==

UpperBound = 9

Dim array(UpperBound)

For i = 0 To UpperBound

Print array(i)

=={{header|Logo}}==

localmake "t item :i :a

setitem :i :a item :j :a

make "a {1 2 3 4 5 6 7 8 9 10}

shuffle :a

Lhogho does not have a setitem, and also does things more 'function'ally.

local "res

make "res []

make "a ( list 1 2 3 4 5 6 7 8 9 10 )

make "a shuffle :a

=={{header|Lua}}==

for n = #t, 1, -1 do

local k = math.random(n)

a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

table.shuffle(a)

=={{header|M2000 Interpreter}}==

Dim Base 0, A(3)

For k=1 to 6 {

}

=={{header|M4}}==

define(`randSeed',141592653)

define(`rand_t',`eval(randSeed^(randSeed>>13))')

show(`b')

shuffle(`b')

{{out}}

<pre>

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Usage of built-in function:

Custom function:

Module[{indices = {}, allindices = Range[Length[input]]},

Do[

];

input[[indices]]

Example:

=={{header|MATLAB}}==

Because this shuffle is done using rounds of operations on subsets of decreasing size, this is not an algorithm that can be vectorized using built-in MATLAB functions. So, we have to go old-school, no fancy MATLAB trickery.

for i = (numel(list):-1:2)