Minimal injective superstrings: A simpler generalization of superpermutations
It seems that I write about superpermutations way too frequently, and today I’m going to continue the trend. Recall that a superpermutation is a string on n symbols that contains all n! permutations of those n symbols as contiguous substrings. For example, when n = 3, the 3! = 6 permutations of the symbols “1”, “2”, and “3” are 123, 132, 213, 231, 312, and 321, and a superpermutation is
123121321
since it contains all 6 of those permutations as substrings. That superpermutation is “minimal”: no shorter superpermutation on 3 symbols exists. We know how long minimal superpermutations are when n ≤ 5, but when n ≥ 6 determining this minimal length is still an open problem.
Somewhat surprisingly, there is a natural generalization of this problem that is actually easier to solve… in all cases except for the original case (superpermutations) that we care about. Here’s how it works: instead of requiring that the superstring contain all permutations as substrings, fix an additional parameter k that specifies the length of the substrings that it must contain. We say that a (length-k) string is injective if all of the characters in it are distinct, and we say that an injective superstring is a string that contains all injective strings (for a fixed pair of parameters n and k) as contiguous substrings. What is the minimal length of an injective superstring?
The requirement that the characters in an injective string be distinct forces the inequality k ≤ n. In the extreme case when k = n, an injective string is simply a permutation, so an injective superstring is simply a superpermutation, in which case the problem of finding a minimal one is hard. However, all other cases are easy: whenever k < n, it is known that minimal injective superstrings have length exactly equal to n!/(n-k)! + (k-1). For example, if n = 3 and k = 2 then the injective strings (strings of length 2 on the symbols “1”, “2”, and “3” in which all characters are distinct) are 12, 13, 21, 23, 31, and 32, and a minimal injective superstring (of length n!/(n-k)! + (k-1) = 6/1 + 2 = 8) is 1231321.
My latest video demonstrates how to construct minimal injective superstrings, and explains why they are so much easier to construct than minimal superpermutations:
I must say this article is extremely well written, insightful, and packed with valuable knowledge that shows the author’s deep expertise on the subject, and I truly appreciate the time and effort that has gone into creating such high-quality content because it is not only helpful but also inspiring for readers like me who are always looking for trustworthy resources online. Keep up the good work and write more. i am a follower.
Somebody essentially lend a hand to make significantly posts I might state That is the very first time I frequented your web page and up to now I surprised with the research you made to create this particular put up amazing Excellent job
I do agree with all the ideas you have introduced on your post They are very convincing and will definitely work Still the posts are very short for newbies May just you please prolong them a little from subsequent time Thank you for the post
Your blog is a shining example of excellence in content creation. I’m continually impressed by the depth of your knowledge and the clarity of your writing. Thank you for all that you do.