Permutation Products

Richard Ambler / December 2019

Welcome to Permutation Products, a little demo of the trotter library.

Lots of alphabet permutations!

There are 403,291,461,126,605,635,584,000,000 permutations of the letters of the alphabet! If we were to list all the permutations according to the Steinhaus-Johnson-Trotter ordering, the first and last ten permutations would be:

abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxzy
abcdefghijklmnopqrstuvwzxy
abcdefghijklmnopqrstuvzwxy
abcdefghijklmnopqrstuzvwxy
abcdefghijklmnopqrstzuvwxy
abcdefghijklmnopqrsztuvwxy
abcdefghijklmnopqrzstuvwxy
abcdefghijklmnopqzrstuvwxy
abcdefghijklmnopzqrstuvwxy
...

bacdefghijklmnopzqrstuvwxy
bacdefghijklmnopqzrstuvwxy
bacdefghijklmnopqrzstuvwxy
bacdefghijklmnopqrsztuvwxy
bacdefghijklmnopqrstzuvwxy
bacdefghijklmnopqrstuzvwxy
bacdefghijklmnopqrstuvzwxy
bacdefghijklmnopqrstuvwzxy
bacdefghijklmnopqrstuvwxzy
bacdefghijklmnopqrstuvwxyz

(And if we were to list them all, the above list - with each line taking up one centimeter, say - would span 13,443,048,704,220,187 lightyears!)

If we were to store these permutations in a list such that each permutation took up only one bit of memory, the list would take up 43,724,947 exabytes! If we needed to find a particular permutation in the list, and each check took only 10^-12 seconds, a brute force search could take up to 127,882,883,411,531,467 millennia!

However, we can use properties of the arrangement to create pseudo-lists that ostensibly store the permutations using an insignificant amount of memory, and that can look up permutations fairly instantaneously.

As a demonstration of this, use the text input fields below to input permutations P and Q in cyclic notation. (For example, we could input (ate)(cod)(fish), which corresponds to tbocaigfsjklmndpqrheuvwxyz.)

As you input P and Q, this page will calculate the composition, or group product, of P and Q, and locate each of the three permutations in the pseudo-list 'containing' all possible permutations.

Have fun!