Displays a permutation matrix, permuton heatmap, and P/Q tableaux generated via inverse RSK from a Young diagram shape. Explores conjectured permuton limit shapes. Draw shapes or use partition notation with Plancherel or staircase presets. Supports single permutations and multi-sample heatmap accumulation with configurable scaling.
Conjecture (L.P.): If a Young diagram has a limit shape on the scale $\sqrt{n}$, then random permutations have a limit in the sense of permutons.
Skip to simulation visualization
Random permutation via inverse RSK
About the Inverse RSK Algorithm
The inverse Robinson-Schensted-Knuth (RSK) correspondence takes a pair of Standard Young Tableaux (P, Q) of the same shape and recovers the permutation that generated them through the forward RSK algorithm.
How it works:
- Sample two independent random Standard Young Tableaux P and Q of the same shape using the hook-walk algorithm
- Apply the inverse RSK procedure:
- For each time step t = N down to 1, find t in the Q-tableau
- Extract the corresponding entry from the P-tableau
- Perform reverse bumping through the rows to recover the original inserted value
- The sequence of extracted values forms the permutation σ
Shape Input Methods:
- Draw Mode: Draw the outline of a Young diagram and specify target number of boxes
- Text Input & Presets:
- Manual: Enter comma-separated row lengths (e.g.,
5,4,3,2,1) or use exponential notation (e.g.,50^50,1^50for 50 rows of length 50 followed by 50 rows of length 1) - Plancherel: Sample random partition with given number of boxes using Plancherel measure
- Staircase: Generate staircase shape k, k-1, ..., 1
- Manual: Enter comma-separated row lengths (e.g.,
Output Formats:
- Small permutations (N ≤ 200):
- Full permutation array display:
σ = [3, 1, 4, 2, ...] - Detailed tableaux with numbered entries
- Permutation matrix with dots
- Full permutation array display:
- Medium permutations (200 < N ≤ 600):
- Truncated array display:
σ of size N (showing first 20): [σ(1), σ(2), ..., σ(20), ...] - Permutation matrix visualization with dots
- Color-coded tableaux (heat map style)
- Truncated array display:
- Large permutations (N > 600):
- Truncated array display with first 20 elements
- Summary statistics only for visualization
- Color-coded tableaux using UVA color scheme (orange to blue gradient)
Download Options:
- Download Shape λ: Saves the Young diagram as comma-separated row lengths in a text file
- Download Permutation σ: Saves the complete permutation as comma-separated values in a text file
- Files are timestamped with format:
shape_lambda_N{size}_{timestamp}.txtandpermutation_sigma_N{size}_{timestamp}.txt
Properties:
- Uniform distribution: Generates uniformly random permutations with given RSK shape
- Bijective: Perfect correspondence between permutations and SYT pairs
- Scalable: Uses WASM for large shapes (N > 500 boxes) with pure JS implementation for smaller cases
- Progress tracking: Shows progress bar for large simulations (N > 5000)
|
Permutation & Permuton Heatmap
Permutation Matrix
Permuton Heatmap
Standard Young Tableaux
P-tableau
Q-tableau
code
(note: parameters in the code might differ from the ones in simulation results below)-
Link to code(Interactive JS – see source) -
Link to code(WASM sampler for a single SYT)