Welcome to the staging ground for new communities! Each proposal has a description in the "Descriptions" category and a body of questions and answers in "Incubator Q&A". You can ask questions (and get answers, we hope!) right away, and start new proposals.
Are you here to participate in a specific proposal? Click on the proposal tag (with the dark outline) to see only posts about that proposal and not all of the others that are in progress. Tags are at the bottom of each post.
Find the shortest possible string containing all permutations of 1, 2, 3 Question
There are 6 permutations of the numbers 1, 2, 3.
They are:
123
132
213
231
312
321
The goal is to make a string (as short as possible) using the digits 1, 2 and 3 so that each of the above 6 permutations occur at least once in consecutive positions in the string.
The sample string below contains all 6 permutations. The string is 12 digits long but there are shorter strings that contain all 6 permutations.
As examples, the permutation 213 occurs in the positions marked AAA and the permutation 123 occurs in the positions marked BBB.
AAA BBB
132132323123
What is the shortest string that satisfies the above conditions?
I know what the shortest string length is.
If you post a correct string with that shortest possible length, I plan to upvote your answer.
If you also give a proof that your answer is minimal which I find easy to understand, I plan to mark your answer as Works for me.
1 answer
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| will.octagon.gibson | (no comment) | Aug 4, 2026 at 15:58 |
Proposed solution
123121321 for 9 symbols.Reasoning
The first three symbols should be a permutation because otherwise we can trim the first symbol without losing any permutation. Without loss of generality we can start with 123. Given a prefix, call a one-symbol continuation of it "good" if it contributes a new permutation.
The only good continuation of 123 is 1, and the only good continuation of 1231 is 2. There are no good continuations of 12312 because 123 is already contained in the string. So we have three permutations in five symbols. The other three permutations can similarly be done in five symbols, and by choosing to start at 2 we can overlap and save a symbol, giving nine symbols in total.
The result has only one three-symbol substring which doesn't contribute a necessary permutation: the central 121. To improve on that would require starting with a permutation and making five good extensions, and we've already seen that this is impossible.
0 comment threads
0 comment threads