Generating random permutations
Revision as of 10: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 | |...")
Problem Description
Generating random permutation of an input string.
Bounds Chart
Error creating thumbnail: Unable to save thumbnail to destination
Step Chart
Error creating thumbnail: Unable to save thumbnail to destination
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 |