General Permutations (Generating Random Permutations)

From Algorithm Wiki
Jump to navigation Jump to search


Given an input string/array, generate a single random permutation of the characters/elements of the string/array.

Related Problems

Related: Cyclic Permutations


$n$: number of elements

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Fisher–Yates/Knuth shuffle 1938 $O(n^{2})$ $O(n)$ Exact Randomized Time
Durstenfeld's Algorithm 235 1964 $O(n)$ $O({1})$ Exact Randomized Time
Radix sorting method 1887 $O(n)$ $O(n)$ Exact Randomized

Time Complexity Graph

Generating Random Permutations - General Permutations - Time.png