Generating random permutations

From Algorithm Wiki
Revision as of 11:56, 10 October 2022 by Admin (talk | contribs) (Created page with "== Problem Description== Generating random permutation of an input string. == Bounds Chart == 1050px == Step Chart == 1050px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links |- | rowspan="1" | Exp/Factorial | |...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Problem Description

Generating random permutation of an input string.

Bounds Chart

Generating random permutationsBoundsChart.png

Step Chart

Generating random permutationsStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic Sattolo's algorithm (1986)
nlogn
Linear Fisher–Yates/Knuth shuffle (1938)

Durstenfeld's Algorithm 235 (1964)

[- Radix sorting method (1887)]

logn
Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Generating_random_permutations&oldid=75"