Every permutation of the alphabet up to 29 characters?

Question

I'm attempting to write a program that will generate a text file with every possible permutation of the alphabet from one character up to twenty-nine characters. I've chosen 29 as the longest English word that everyone knows is antidisestablishmentarianism which is 28 characters in length. There are longer ones, but they are mainly very technical and obscure.

I realise this will generate a huge number of strings. However I've no idea where to start or even how to figure out how many combinations this will generate.

Answers please for solutions in PHP, Processing, C++ or Java (I'm only familiar with those, PHP is preferred, but probably no the best for this I should imagine).

Or even just pseudo-code / ideas will be appreciated.

Also, before someone says it, this isn't for brute forcing or anything like that. I'm an artist, albeit somewhat unknown and obscure with my concepts.

Answer 1

The word "permutation" usually means that each letter appears exactly once, so it would be impossible to generate any permutation with more than 26 letters. Anyway, since the number of generated strings is too big, you can use random strings instead (the following is C code):

char s[30];
int p;
for (;;) // repeat forever: you cannot use a realistic iteration limit anyway
{
    for (p = 0; p < 29; ++p)
        s[p] = 'a' + rand() % 26;
    s[29] = '\0';
    puts(s);
}

Answer 2

void out_perms(std::string word) {
    std::vector<int> indexes(word.size());
    for (size_t i = 0; i < indexes.size(); ++i)
        indexes[i] = i;
    do {
        for (size_t i = 0; i < indexes.size(); ++i)
            std::cout << word[indexes[i]];
        std::cout << std::endl;
    } while (std::next_permutation(indexes.begin(), indexes.end()));
}

int main(int, char**) {
    out_perms("asdfg");
}

See http://codepad.org/6lQTPQrG for example output

Answer 3

Obviously, the outer for loop is for the number of characters in your word. Then, you just create strings with that length. For length 5, you start with "AAAAA", then "AAAAB", "AAAAC".

Once you hit "Z", you go back and move the character to your left one up, i.e. "AAAAZ" becomes "AAABA", and "AAAZZ" becomes "AABAA". Once you hit "ZZZZZ", you're done with the inner loop, and the outer loop will then start with "AAAAAA".

Answer 4

Here is a simple untested program in C++ that creates the words by counting in Base 26:

#include <string>
#include <iostream>

int main(void)
{
    //----------------------------------------------------------
    //  Print permuations of strings of letters up to length 5.
    //  Use base 26 arithmetic.
    //----------------------------------------------------------
    const unsigned int MAX_ITERATIONS = 26 * 26 * 26 * 26 * 26;

    std::string word = "A";
    for (unsigned int i = 0; i < MAX_ITERATIONS; ++i)
    {
        //------------------------------------------------------
        //  Print the word
        //------------------------------------------------------
        std::cout << word << std::endl;

        //------------------------------------------------------
        //  Increment the word, using base 26 arithmetic.
        //  A, B, C, ..., Z.
        //  AA, BA, CA, ..., ZA, AB, BB, CB, DB, ..., ZZ.
        //  AAA, BAA, CAA, ..., ZAA, ABA, BBA, CBA, DBA, ..., ZZZ.
        //------------------------------------------------------
        bool            carry_generated = false;
        unsigned int    digit = 0;
        do
        {
            carry_generated = false;
            if (word[digit] < 'Z')
            {
                ++word[digit];
                break;
            }
            word[digit++] = 'A';
            if (word.length() == digit)
            {
                word += "A";
                break;
            }
            carry_generated = true;
        } while (carry_generated && (digit < 5));
    }

    return 0;
}

The number of words printed can be reduced by checking a word list (a.k.a. dictionary) before printing. If the word is in the word list, print it.

The biggest issue with a word length of 29 is representing the quantity. The quantity overflows the range of the standard C++ unsigned integers. A Big Int library would need to be used. The next issue is the time required to process every combination. Multiply the quantity by 1 microsecond per iteration (a kind of worse case) and reduce down to days, hours, minutes and seconds. Perhaps years may be required.

Answer 5

Using PHP's Perl-style character incrementing.

set_time_limit(0);

$perm = 'A';
$endTest = str_repeat('Z',28).'A';
while ($perm != $endTest) {
    echo $perm++,"\n";
}

Run the script from the command line so you don't hit a webserver timeout; then sit back and wait a few years for it to complete

Answer 6

function p($length, $partial)
{
      if ($length == 0) return $partial;
      $ans = array();
      foreach (range('a', 'z') as $i)
      {
          $ans[] = p($length -1, $partial . $i);
      }
      return $ans;  
}

$top = 3;
//$f = fopen('out.txt');
for ($l = 1; $l < $top+1; $l++)
{
     print_r(p($l), '');
     //fwrite($p($l), '');
}

If you want to set $top to 29 and give it a try go ahead. I'm not going to.

EDIT - print_r(p($l), ''); ---> print_r(p($l, ''));

PHP keeps impressing me with its tolerance for mistakes. Missing a 'required' argument to my p? no problem itll just be empty string somehow (or zero, or false, situation depending). Second '' argument to print_r? no difference, gets treated like the default false anyway

EDIT

I don't know what the hell I was doing here. The different return types of p are quite odd, and will return a compound array with a weird structure.

This is a far better solution anyway

$lengthDesired = 29;
for($i='a'; $i != str_pad('',$lengthDesired+1,'a'); $i++)
    echo $i .', ';

Answer 7

public class hii {  

public static void main(String[] args){

    String[] database = {"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"};

    for(int i=1; i<=database.length; i++){
        String[] result = getAllLists(database, i);
        for(int j=0; j<result.length; j++){
            System.out.println(result[j]);
        }
    }



}


    public static String[] getAllLists(String[] elements, int lengthOfList)
    {
        //initialize our returned list with the number of elements calculated above
        String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];

        //lists of length 1 are just the original elements
        if(lengthOfList == 1) return elements; 
        else {
            //the recursion--get all lists of length 3, length 2, all the way up to 1
            String[] allSublists = getAllLists(elements, lengthOfList - 1);

            //append the sublists to each element
            int arrayIndex = 0;

            for(int i = 0; i < elements.length; i++){
                for(int j = 0; j < allSublists.length; j++){
                    //add the newly appended combination to the list
                    allLists[arrayIndex] = elements[i] + allSublists[j];
                    arrayIndex++;
                }
            }
            return allLists;
        }
    }






}

Answer 8

Here is a permutation generator written in java http://www.merriampark.com/perm.htm.

However as he mentions

  //-----------------------------------------------------------
  // Constructor. WARNING: Don't make n too large.
  // Recall that the number of permutations is n!
  // which can be very large, even when n is as small as 20 --
  // 20! = 2,432,902,008,176,640,000 and
  // 21! is too big to fit into a Java long, which is
  // why we use BigInteger instead.
  //----------------------------------------------------------

Since your n is 29, you will be waiting a long, long time. It is too large, as EboMike is trying to tell you in his comments.

Answer 9

just off the top of my head (PHP).

$index = 0;

while(1) {
   $output_string = '';
   $base_26 = (string)base_convert($index, 10, 26);
   if (strlen($base_26) > 29) break;
   for ($i = 0; $i < strlen($base_26); $i++) {
      $output_string .= chr(65 + base_convert($base_26[$i], 26, 10));
   }
   $index++;
   echo $output_string;
}

Answer 10

This is what I would do:

#include <iostream>

void printWords(std::string& word, int index, int last)
{
    std::cout << word << "\n";
    if (index != last)
    {
        for(char loop = 'a'; loop <= 'z'; ++loop)
        {
            word[index] = loop;
            printWords(word, index+1, last);
        }
        word[index] = ' ';
    }
}

int main()
{
    std::string word("                             "); // 29 space

    printWords(word,0,word.length());
}

Answer 11

A Java solution that should do the trick:

public void characterPermutations(int length, LinkedList<String> permutations) {
    if(length > 1) {
        characterPermutations(length - 1, permutations);

        ListIterator<String> iterator = permutations.listIterator();
        while(iterator.hasNext()) {
            String permutation = iterator.next();
            for(char c = 'a'; c <= 'z'; c++) {
                iterator.add(c + permutation);
            }
        }

    } else {
        for(char c = 'a'; c <= 'z'; c++) {
            permutations.add(c + "");
        }
    }
}

Answer 12

The easiest way I can think of to get every permutation from 1 char to 29 chars in pseudo-code:

loop from i = 1 to 26^29 or 27^29 if you want to include spaces
{
   convert i to base 26 or 27;
   translate each number to the corresponding letter;
}

Answer 13

Even if you could store this on disk, like thirydot pointed out, you'd run out of time doing this.

Just generating (and not storing) all the 6-letter possiblilies took 24 seconds on my computer:

$ time perl letters.pl

real    0m24.837s
user    0m24.765s
sys     0m0.030s

Which is 7.7X10^-8s per word, That means it would take 8.4x10^33s or 2.6x10^26 years to do this.

You need to think more about your algorithm.