|
gptkbp:instanceOf
|
gptkb:algorithm
|
|
gptkbp:alsoKnownAs
|
gptkb:Fisher–Yates_shuffle
|
|
gptkbp:application
|
games
random sampling
simulations
shuffling cards
|
|
gptkbp:category
|
randomization algorithm
|
|
gptkbp:complexity
|
O(n)
|
|
gptkbp:describedYear
|
1938
|
|
gptkbp:field
|
computer science
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Knuth shuffle
|
|
gptkbp:input
|
array
|
|
gptkbp:modernVersionPublishedBy
|
gptkb:Donald_Knuth
|
|
gptkbp:modernVersionPublishedIn
|
gptkb:The_Art_of_Computer_Programming
|
|
gptkbp:modernVersionPublishedYear
|
1969
|
|
gptkbp:namedAfter
|
gptkb:Donald_Knuth
|
|
gptkbp:originallyDescribedBy
|
gptkb:Frank_Yates
gptkb:Ronald_Fisher
|
|
gptkbp:output
|
random permutation
|
|
gptkbp:property
|
in-place algorithm
linear time
unbiased permutation
|
|
gptkbp:purpose
|
randomly permute a finite sequence
|
|
gptkbp:relatedTo
|
gptkb:Monte_Carlo_method
random permutation
random number generation
|
|
gptkbp:requires
|
generator
|
|
gptkbp:step
|
for i from n−1 downto 1 do
generate random integer j such that 0 ≤ j ≤ i
swap a[i] with a[j]
|
|
gptkbp:bfsParent
|
gptkb:Fisher–Yates_shuffle
|
|
gptkbp:bfsLayer
|
6
|