Search

Superpermutations: What's so Super in it?

Written by Sohail Sarkar

Let me tell you this when I heard “superpermutation” for the first time I was pumped. The fact that it has super in it just makes it cool to hear or say. I thought about using it to gain some attention in school but as it turns out, right now my friends and teachers call me the nerd math boy.


So beware. NERD ALERT AHEAD.


Permutations & Combinations


You may remember “permutations and combinations” from your math class. Anyways it’s always great to revise.


Permutations are just like shuffling. So imagine you have 3 cards: 1,2 & 3. The question that a permutation asks is, “In how many ways can you arrange all three cards?”. So let’s do that.

We have

123, 132, 231, 213, 312, & 321


That wasn’t hard at all. Anyways the answer is six. You can arrange the cards in one of the above three ways.


Now stepping to combinations. Imagine you have the same three cards, but this time the question, “In how many ways can you choose cards from the set?”.


We can choose 1, 2, or 3 cards at a time from the given set. To be precise we can form combinations of sizes 1, 2, or 3.


When we choose only 1 card at a time we have- 1 or 2 or 1 (3 ways)

When we choose 2 cards at a time we have- 12 or 23 or 13 (3 ways)

When we choose 3 cards we have the good old- 123 (1 way)


And the answer would be a total of 7 ways.


Now what you might have noticed is that the main difference in a permutation and combination is that one focuses on the arrangement and the other on choosing respectively. To be more precise in permutation the order of the elements matter but combinations are subsets and hence the order of its elements does not matter.


That being said I think that’s all I should tell for now. They can be studied in much depth if you want to, so definitely give it a try.



Superpermutations


Superpermutations are really fancy and as Wikipedia says, “a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring.”

To be honest back in 2018, when I read this for the 1st time, it was a bit intimidating. But trust me it got only better. So continue reading.


Now we remember permutations for 1, 2, and 3.

Why don’t we try finding the permutation for 1, and 2?


We have

12 and 21

That was easy.


Basically a superpermutation is a string of numbers that contain all the permutations. What is a string you ask? A string is a sequence of characters, these characters can be numerical digits, letters, punctuation marks, etc.


That being said, it would mean that the superpermutation of 1 and 2 will be:

1221


Well, congratulations. You just found out the superpermutation of 1 and 2.


It would only be logical if we try to find out the superpermutation of 1, 2, and 3. So why wait? Here we go again


The permutations for 1,2 and 3 are:

123 132

231 213

312 321


And arranging them together we get:

123132231213312321


Congratulations on your second superpermutation.



Seriously that’s all, I don’t think it deserves the word “Super”


To be honest I said the same thing. What’s so super in super-\permutation. It’s not cool. It’s boring and perhaps a dumb idea that should not exist at all.


But here is it, let me tell you why it’s so interesting by asking a question, “What is the smallest string that we can write that will contain all the permutations?”


For start let’s do it with 1 and 2:

One of it’s longest superpermutation is 1221.

The smallest superpermutation?

121


Why?

121 contains both 12 and 21 in itself ergo 121 is the smallest string.

Again what’s so super about it you may ask.


Well, why don’t we try it with 1, 2, and 3:

Trust me it’s solvable but not easy.

One of the longest superpermutation is 123132231213312321.

The smallest superpermutation?

123121321


It contains all 6 permutations 123, 231, 312, 213, 213, and 132.

Check it out yourselves.


What’s fascinating is that the smallest superpermutation is 6 digits smaller than the largest.

Yellow: 123

Violet: 231

Red: 312

Green: 321

Purple: 213

Indigo: 132


Note:

You might notice that I was using the words “One of the longest superpermutation”, there’s a reason why I chose to say that. You see each string can be arranged in many ways.

For {1,2}

1221 is one of the longest arrangements.

2112 is another way of representing the same.

The same holds for {1,2,3}.Hence, just to make things clean it’s important to think about everything that’s revolving around.


For the sake of fun. Let’s consider the superpermutation for {1,2,3,4}


One of it’s longest superpermutation:

123412431342132414231432213421432431241323142341342134123214324131243142412341324231421343124321


And drum roll for the smallest superpermutation for n=4{1,2,3,4}:

123412314231243121342132413214321


What’s beautiful is that the largest string contains 600 digits, whereas the smallest covers the whole thing using only 153 digits. Isn’t it just fascinating?


(To be honest, that’s a hell of a solution to a hell of a problem.)



In What Universe is this Tech?


Well, I must say it is inclined towards math but here’s the thing it is more inclined towards tech than you think.


I want you to imagine a scenario.


You are trying to crack the password for getting access into {“anything that you want to get into” imagine it yourself}

So you need a 5 digit password to open the {“whatever it is”}. There are only 5 digits in the pad: 1,2,3,4 and 5. If you enter them in the right order, the {“thing that you want”} will finally be yours.

You start by trying 12345. “Beep, Access Denied”.

Now you go for 12354. “Beep, Access Denied”.


You see a man walking through the corridor coming towards you in the camera you installed in the hallway, you have 5 mins to enter the code, take the {“the thing that you want”} and escape.


You get nervous and try 12453. “Beep, Access Denied”. You don’t have time to type in all 120 numbers that would sum up to 600 digits.


(You are scared and then you remember this article on Techvik)


And hurray you know what to do

You enter the 153 digits, which is the smallest superpermutation for n=5.

“Beep, Access Granted”. You take the {“thing that you want”} and escape.

In your earpiece, you hear, “Good Job Agent {“your name”}”.


While that scenario is very unlikely, what’s important is how easily superpermutations can save a ton of time by reducing computations.


This is very helpful for almost everything. We have always been trying to reduce the time taken for computers to solve or perhaps find something faster than usual.

In supercomputing, there are calculations that take tons of time to make or find the solution/instance/model/occurrence/illustrate something, and thanks to superpermutations, we can reduce that.

A supercomputer just like ordinary computers store information in classical bits i.e. 1s and 0s. And just imagine if we are able to run by tons of bits by not deleting a string of bits but by removing the first bit and adding the next bit to its tail from a sequence of strings of 1s and 0s that we can generate. Thanks to superpermutation we can do that, and trust me when I say this it saves tons and tons of time. If a 600-bit code can be reduced to 153-bit code imagine how fast that computer can work. Although it will be slower compared to computers that use Qubits i.e. Quantum Computers.


Imagine that the answer to a question is 16-bit code, there are 2¹⁶ i.e 65536 possible combinations with 1048576 digits that you need to cover, you might run a loop and go through every combination to find the one that is correct but using the concept of Superpermutation what you can do is find the smallest string, in this case, the string will have only 65551 digits compared to 1048576 digits but what’s interesting is that the string will have all 65536 possible combinations, and by removing the first bit and adding in the 17th bit at the end of the sequence you can testify every answer, this saves a lot of memory in the computer, reduces stress in it’s processing and of course, saves a ton of time.


Well, that’s not all. It’s possible to hack radio transmitted security systems using superpermutations.

Usually, ISM (Industrial Scientific Medical) transmissions are either an 8 bit or 12-bit code and have a frequency of 300 to 433 MegaHertz. It’s usually found that these receivers use a shift register, which is it takes each string of bits as a one 8 or 12-bit string, and instead of ignoring it if it’s wrong, it throws out the first bit and considers the next bit by appending it to its end.

This means that it’s not necessary to transmit these codes with gaps in them i.e. allowing us to merge every combination into one string.

And voila, you get access into the system that you are trying to infiltrate.


In fact, Superpermutations have great uses in other fields like Robotics, DNA sequencing,... etc.


I can go on but here’s the thing I want this article to represent how important and fun bits of recreational mathematics can be.

So that’s all for now.

REFERENCES:

https://www.youtube.com/watch?v=wJGE4aEWc28

https://www.youtube.com/watch?v=OZzIvl1tbPo

https://en.wikipedia.org/wiki/Superpermutation

https://www.quantamagazine.org/unscrambling-the-hidden-secrets-of-superpermutations-20190116/

https://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html

6 comments

TECHVIK

Copyright © 2019 by Techvik.