Super Permutations

Permutations, in its simplest form, is all about counting. Of course, that's probably oversimplifying things but essentially, what we try to do is count how many times we can arrange a given set of elements without repeating them. It comes up in many areas of lives and it would be very useful to know about them.

But as we encounter an increasing number of elements in a given set, it becomes more difficult to count them by hand so we developed shortcuts. So what happens if you put all those permutations together in one string? You get a superpermutation.

So, a permutation is a special arrangement of symbols. A “superpermutation,” in a sense, is a special arrangement of permutations: It is a sequence of symbols that contains every possible permutation of those symbols. For example, stringing together all six permutations of {A, B, C} gives us ABCACBBACBCACABCBA, a superpermutation of {A, B, C}.

But, at 18 symbols long, this is not the shortest possible superpermutation of {A, B, C}. We can shorten it without losing any of the permutations it contains. Notice the double B: ABCACBBACBCACABCBA

Removing one of the Bs means we’ll no longer have CBB or BBA in our sequence, but neither of those are permutations of {A, B, C}, so we don’t need them. Now we have: ABCACBACBCACABCBA

This shortened sequence still contains every permutation of {A, B, C}, so it’s a valid superpermutation. In fact, you can also remove other unnecessary letters. And when you can make things shorter, the natural mathematical question to ask is, “How short can you make it?” So, how long is the shortest superpermutation of {A, B, C}?

(Image credit: Big Mouth for Quanta Magazine)