superpermutation (1054B)
1 # Superpermutation 2 3 https://en.wikipedia.org/wiki/Superpermutation 4 5 Given a number n, shortest word on alphabet {1, ..., n} containing all permutations as contiguous subsequence, aka "Haruhi problem" 6 7 Related problem: [superpattern], shortest permutation on n elements containing all k-element permutation as a [permutation_pattern] 8 9 Related notion: [universal_word] (all contiguous factors) 10 11 Related notion: shortest word containing all permutations as a [subsequence] 12 - discussed here https://mathoverflow.net/questions/165303/shortest-supersequence-of-all-permutations-of-n-elements 13 - on [oeis] https://oeis.org/A062714 14 - article surveying this: https://www.tandfonline.com/doi/full/10.1080/00029890.2021.1835384#d1e3032 15 - lower bound [kleitman1976lower] 16 - [conp_hard] to detect, cf [uznanski2015all] by [przemyslaw] 17 - from https://cstheory.stackexchange.com/questions/31559/recognizing-sequences-with-all-permutations-of-1-ldots-n-as-subsequence 18 19 Up: [combinatorics] 20 21 See also: [universal_random_word], [universal_word], [de_bruijn_sequence]