Permutations of the Alphabet

Here you can download all possible permutations of the lowercase alphabet as .text files, and learn how to generate your own permutations in bash or PHP.

2537 views
d

By. Jacob

Edited: 2022-05-26 15:22

Sometimes it may be useful to know the number of character permutations in the alphabet for a given string length. We can calculate it by knowing the number of letters in the alphabet; since the English alphabet has 26 letters, we multiply 26*26=676 to find the number of letter permutations for a 2-character string.

This exercise will later allow you to generate permutations of basically anything, be it numbers, lower case- or upper case letters, and even UTF-8 symbols – including smiley symbols.

Note. If you are trying to generate permutations of the alphabet programmatically, then beware that the total possible combinations will increase exponentially, and potentially exhaust system resources rather quickly. I have personally crashed my computer and lost work from fooling around with this stuff.

It may be best to keep a database or file with pre-generated permutations, or even better, just spit out a given permutation when you need it. Since the permutations are always generated in the same order, you will also be able to keep a numeric record of which permutations has been used already by a system, and thereby ensure uniqueness.

Here is table containing the number of possible permutations of the alphabet for various string lengths:

LengthFormulaPermutationsFile?Size
2 26*26 or 26^3 676alphabet-two-letter-permutations.txt2.1 KB
3 26*26*26 or 26^3 17.576alphabet-three-letter-permutations.txt70.4 KB
4 26*26*26*26 or 26^4 456.976alphabet-four-letter-permutations.txt2.3 MB
5 26*26*26*26*26 or 26^5 11.881.376alphabet-five-letter-permutations.txt71.3 MB
6 26*26*26*26*26*26 or 26^6 308.915.776alphabet-six-letter-permutations.txt2.1 GB

Note. Each permutation in the files above is followed by a single line break (\n).

We do not necessarily need to create an algorithm for generating permutations. In Linux, it is also possible to generate permutations from a terminal with this very simple syntax: {a..z}.

To output all possible permutations of a two-letter string using the 26 letters of the alphabet:

echo {a..z}{a..z}

This will result in a space-separated list:

aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av aw ax ay az ba bb bc bd be bf bg...

Generate permutations from PHP

Being a web developer I personally use PHP a lot, so I came up with a function that will generate the permutations of the items in an input array and save them to a .txt file in batches.

The function is probably no a 100% optimised, but is fairly fast, and does not take up much memory since it is writing the permutations to a file as it goes. You could probably optimize it further by figuring out ideal buffer size for disk writes.

Here we go:

function permute(
  $max,
  $file_path,
  &$c2 = null,
  $i = 0,
  &$pArr = [],
  &$permutations = [],
  &$bytes_written = 0,
  &$item_list = [
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
  ]
) {
  $data = '';
  // Do not attempt to open the file again if it is already open by the process
  if (!isset($fp) || $fp == false) {
    $fp = fopen($file_path, "a");
  }

  // Remember the character from the previous loop
  if (isset($c2)) {
    $pArr["$i"] = $c2;
  }

  // Increment the counter +1 towards $max
  ++$i;

  // Loop through the alphabet
  foreach ($item_list as $c) {
    // If we have reached max nesting, add what we got to the permutations array
    if ($i === $max) {
      // Combine characters passed on by previous iteration until we have been through all combinations.
      // The method will execute the following order, the "X" marks the current item.
      // 1. aaaX
      // 2. aaXz
      // 3. aXzz
      // 4. Xzzz
      $pStr = implode('', $pArr);
      $permutations[] = $pStr . $c;
      // Save in batches to make the function faster
      $pCount = count($permutations);
      if ($pCount >= 80) {
        // Add a single line break before imploding
        // to avoid first item appearing on the same line as the previous when saving a batch
        if ($bytes_written > 0) {
          $data = "\n";
        }
        $data .= implode("\n", $permutations);
        // On fflush: If any buffering is used on the system, make sure we write data now
        // fflush should typically be called right after fwrite
        if (!fwrite($fp, $data) || !fflush($fp)) {
          throw new Exception("Error writing to permutations file.");
        }
        $bytes_written = $bytes_written + strlen($data);
        $data = '';
        $permutations = [];
      }
    } else {
      permute($max, $file_path, $c, $i, $pArr, $permutations, $bytes_written, $item_list);
    }
  }
  // Write potential leftover permutations that did not reach the batch_limit
  if (count($permutations) > 0) {
    if ($bytes_written > 0) {
      $data = "\n";
    }
    $data .= implode("\n", $permutations);
    if (!fwrite($fp, $data) || !fflush($fp)) {
      throw new Exception("Error writing to permutations file.");
    }
    $bytes_written = $bytes_written + strlen($data);
    $data = '';
    $permutations = [];
  }
  return $bytes_written;
}

You can call the function like this:

permute(4, $file_path)

Storing permutations takes a lot of space

A bit of a warning though, storing generated permutations is probably not needed, at least not when using them for URL shortening purposes; instead, you could have a database table containing the URLs, using a bigint() with auto_increment as the primary key column, and then a secondary table containing the used permutations that is linked to the first table with a foreign key.

This way you could quickly insert new URLs and ensure no issues with concurrently stored URLs. You can then generate the permutation corresponding to a specific numeric ID in the primary key column, because the permutations are generated in the same order every time you run the function.

Of course, if you use my function as a base, you will have to remove the part writing the permutations to a file, and instead insert the permutation in the second database table.

Again, this is possible because the generated permutations always come in the same order, so 1 would equal "aaaa" and 2 would equal "aaab" for example.

Using a bash script

You also could just create bash script and place it in usr/local/bin/permutations_2x.sh:

#!/bin/bash
echo {a..z}{a..z}

This can then be called from PHP with shell_exec:

echo shell_exec('permutations_2x.sh');

Since I use PHP a lot, I find shell_exec to be useful for interacting with other programs at times. However, this does probably work best if you are on a linux system.

Why are permutations interesting?

I have no idea. But, I personally had a need to generate all possible permutations of a two-letter string consisting of the 26 letters of the alphabet; I am planning to use this for various purposes, such as creating a URL-shortner, and/or minification purposes of long IDs.

A two-letter string gives me 676 possible combinations, which should be more than enough to satisfy my needs. I was thinking that I wanted to try it out for shortening long text strings in order to save bandwidth for mobile users, as I have now tested for myself, it however turns out GZIP and Brotli is better for this. But, it has still been a nice little programming challenge to solve.

The alphabet is also an ideal candidate to practice on; once you have written an algorithm that works on the alphabet, you should also be able to use it on longer strings consisting of numbers, text and even symbols or UTF-8 smileys.

Permutations and combinations are different

The letters "ABC" can be said to be a single combination, but it can be arranged 6 different ways (permutations without repetition of each letter):

abc acb bca bac cab cba

Remember, this is technically a single combination, because you still use the same three letters. But, if repetition of each letter is also allowed, you will instead get 27 (n^n) permutations of "ABC":

aaa aab aac aba abb abc aca acb acc baa bab bac bba bbb bbc bca bcb bcc caa cab cac cba cbb cbc cca ccb ccc

Combinations

The arrangement of the items in a combination does not matter, so in order to have more combinations, your blocks has to be unique. E.g.:

  • ABC
  • CBA
  • ABD
  • BDE

Note. The list has three unique combinations, because the first two items are basically the same, so the second item is not a unique combination and does not count.

Of course, this is more a math thing than a PHP-thing, but nevertheless still interesting for some purposes.

Tell us what you think: