Generate all possible strings with PHP

Being a web developer, I personally use PHP a lot, so I came up with a function that generates all possible strings from the items in an input array and saves them to a .txt file in batches.

The function is probably not 100% optimized, but it is fairly fast and does not use much memory, since it writes the generated strings to a file as it goes. You could probably optimize it further by determining the ideal buffer size for disk writes.

Here we go:

function generate_strings(
  $max,
  $fp = null,
  &$c2 = null,
  $i = 0,
  &$pArr = [],
  &$strings_buffer = [],
  &$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 = '';

  // 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 $strings_buffer array
    if ($i === $max) {
      // Combine characters passed on by previous iteration until we have been through all possible strings.
      // The method will execute the following order, the "X" marks the current item.
      // 1. aaaX
      // 2. aaXz
      // 3. aXzz
      // 4. Xzzz
      $string = implode('', $pArr);
      $strings_buffer[] = $string . $c;
      // Save in batches to make the function faster
      $buffer_count = count($strings_buffer);
      if ($buffer_count >= 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", $strings_buffer);
        // 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 strings file.");
        }
        $bytes_written = $bytes_written + strlen($data);
        $data = '';
        $strings_buffer = [];
      }
    } else {
      generate_strings($max, $fp, $c, $i, $pArr, $strings_buffer, $bytes_written, $item_list);
    }
  }
  // Write potential leftover strings that did not reach the batch_limit
  if (count($strings_buffer) > 0) {
    if ($bytes_written > 0) {
      $data = "\n";
    }
    $data .= implode("\n", $strings_buffer);
    if (!fwrite($fp, $data) || !fflush($fp)) {
      throw new Exception("Error writing to strings file.");
    }
    $bytes_written = $bytes_written + strlen($data);
    $data = '';
    $strings_buffer = [];
  }
  return $bytes_written;
}

You can call the function like this:

$file_path = 'strings-output-file.txt';

$fp = fopen($file_path, "a");

generate_strings(4, $fp);

Storing generated strings takes a lot of space

A bit of a warning, though: storing generated strings is probably unnecessary, at least 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, and generate a corresponding string from each numeric ID when needed.

This way, you could quickly insert new URLs while avoiding issues with concurrently stored URLs. Since the strings are generated deterministically in the same order, a specific numeric ID can always be mapped to the same string.

If you use my function as a starting point, you would therefore need to modify it so that it generates the string corresponding to a given numeric ID rather than generating and writing every possible string to a file.

This is possible because the generated strings always occur in the same order. For example, depending on the indexing convention used, 1 could correspond to aaaa, 2 to aaab, and so on.

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

echo shell_exec('generate_strings_2x.sh');

Why are generated strings interesting?

I have no idea. But I personally had a need to generate all possible two-letter strings consisting of the 26 letters of the English alphabet. I was planning to use them for various purposes, such as creating a URL shortener or shortening long IDs in HTML.

A two-letter string gives me 676 possible strings, which should be more than enough to satisfy my needs. I also wanted to experiment with replacing longer text strings with shorter identifiers in order to save bandwidth for mobile users. As I have since tested for myself, however, GZIP and Brotli are generally better suited for reducing the size of textual data. Still, this has 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 with the alphabet, you should also be able to adapt it to other sets of characters, including digits, uppercase and lowercase letters, symbols, and other Unicode characters such as emoji.

Permutations and combinations are different

In combinatorics, permutations and combinations have specific meanings. A permutation is an arrangement in which order matters, whereas a combination is a selection in which order does not matter. For example, the three distinct letters ABC can be arranged in 6 different ways, giving the following permutations without repetition:

abc acb bca bac cab cba

If repetition is allowed, we are no longer simply generating permutations of the three distinct letters. Instead, we can generate all possible strings of length 3 over the alphabet {a, b, c}. Since each of the three positions can contain any of the three letters, there are 3³ = 27 possible strings:

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