Live briefing
Everything about Random permutation
Sequence where any order is equally likely
A random permutation is a sequence where any order of its items is equally likely at random, that is, it is a permutation-valued random variable of a set of objects. The use of random permutations is common in games of chance and in randomized algorithms in coding theory, cryptography, and simulation. A good example of a random permutation is the fair shuffling of a standard deck of cards: this is ideally a random permutation of the 52 cards. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: Random permutationA 5-minute orientation
- Skim a recent paper: Permutation Jensen–Shannon divergence for Random Permutation SetInfluential work since 2022
- Pick up a classic book: Tables of random permutationsThe most-reprinted book on the subject
- Read the landmark paper: Generating a random permutation with random transpositionsCited 390 times
- Go sideways: Fisher–Yates shuffleA closely related topic
- Go sideways: BogosortA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Generating a random permutation with random transpositions
Algorithm 235: Random permutation
Random Permutation Set
Non-random circular permutation of phage P22 DNA
Ordered cycle lengths in a random permutation
Maximum entropy of random permutation set
Random Permutation Set Reasoning
Eigenvalues of random lifts and polynomials of random permutation matrices
🆕 Influential since 2022
Permutation Jensen–Shannon divergence for Random Permutation Set
The Distance of Random Permutation Set
Order-2 Probabilistic Information Fusion on Random Permutation Set
A new orthogonal sum in Random Permutation Set
Unsourced Random Access Over Fading Channels via Data Repetition, Permutation, and Scrambling
đź“š Books worth reading
Tables of random permutationsLincoln E. Moses · 1963
Pratique moderne des probabilitésJ. C. Radix · 1991
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Fisher–Yates shuffle The Fisher–Yates shuffle is an algorithm for shuffling a finite sequence. The algorithm takes a list of all the elements of the sequence, and continually…
- Bogosort In computer science, bogosort (also known as permutation sort and stupid sort) is a sorting algorithm based on the generate and test paradigm. The function…
- Reservoir sampling Reservoir sampling is a family of randomized online algorithms for choosing a simple random sample, without replacement, of k items from a population of…
- Pseudorandom number generator A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers…
- Ziggurat algorithm The ziggurat algorithm is an algorithm for pseudo-random number sampling. Belonging to the class of rejection sampling algorithms, it relies on an underlying…
- Rao–Sandelius shuffle The Rao–Sandelius shuffle is a divide-and-conquer algorithm for shuffling a finite sequence. The algorithm takes a list of all the elements of the sequence…
- Birkhoff algorithm Birkhoff's algorithm (also called Birkhoff-von-Neumann algorithm) is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation…
- Pseudorandom generator theorem In computational complexity theory and cryptography, the existence of pseudorandom generators is related to the existence of one-way functions through…