All possible words

Question

I want to create all possible 5 letter words using a-z.Please suggest any good and fast algorithms.

I have tried creating one and it looks something like this...

     byte[] allchar=new byte[] {'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'};
 int lengthOfAllChar=allchar.length;
         System.out.println(lengthOfAllChar);
        for (int i = 0; i < lengthOfAllChar; i++){
            for(int j = 0; i < lengthOfAllChar; j++){
                StringBuffer finalWordBuffer = new StringBuffer();
                finalWordBuffer.append((char)allchar[i]);
                finalWordBuffer.append((char)allchar[j]);
            }
        }

Answer 1

Here's an example of generating all sequences for any set of characters at any length:

public class WordPermutations {
    public static void main(String[] args) {
        char[] chars = "abcdefghijklmnopqrstuvwxyz".toCharArray();
        int len = 5;
        iterate(chars, len, new char[len], 0);
    }

    public static void iterate(char[] chars, int len, char[] build, int pos) {
        if (pos == len) {
            String word = new String(build);
            // do what you need with each word here
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            build[pos] = chars[i];
            iterate(chars, len, build, pos + 1);
        }
    }
}

This takes about 250ms on my machine to iterate through all 11,881,376 sequences.

Note that a new char[len] is only created once at the beginning and reused as build for building the permutations. The first call to iterate() starts with a pos of 0. Skip down to the for loop where it loops through each of chars. The first char of build is set to that and then we recursively call the same method to set the next one at pos + 1. Once this has happened 5 times the pos will be at len. This is when the pos == len kicks in at the top of the method. Then it just builds a String from what's built up in build and there's your word.

Answer 2

This can be done easily also without recursion (here in C)

int i, k, n;
char tmp[6]; tmp[5] = 0;
for (i=0;i<26*26*26*26*26;i++) {
   n = i;
   for (k=4;k>=0;k--){
      tmp[k] = 'a' + (n % 26); 
      n /= 26;
   }
   output_string(tmp);
}

or you can do it with carry:

char tmp[6]; int i, k;
strcpy(tmp, "aaaaa");
for (i=0;i<26*26*26*26*26;i++) {
   output_string(tmp);
   tmp[4]++;
   k = 4;
   while (k > 0 && tmp[k] == 'z') { tmp[k] = 'a'; k--; tmp[k]++; }
}

Answer 3

public static List<String> getAll(int length) {
    final char[] chars = "0123456789".toCharArray();
    final double NUMBER_OF_PERMUTATIONS = Math.pow(chars.length, length);

    List<String> words = new ArrayList<>(Double.valueOf(
            NUMBER_OF_PERMUTATIONS).intValue());

    char[] temp = new char[length];
    Arrays.fill(temp, '0');

    for (int i = 0; i < NUMBER_OF_PERMUTATIONS; i++) {
        int n = i;
        for (int k = 0; k < length; k++) {
            temp[k] = chars[n % chars.length];
            n /= chars.length;
        }
        words.add(String.valueOf(temp));
    }
    return words;
}  

Here is the Java 7 version of antti.huima's code.

Answer 4

Here's an algorithm for you to try out, in pseudocode:

array seenWords;
while size of seenWords[] < 26^5:
  generate random string of length 5 letters
  is string in seenWords?
  yes:
    go back to while
  no:
    push string onto end of seenWords[]
done while

You should be able to easily translate this pseudocode into proper Java code. The only tricky bit is generating the random string. You could take your array of letters, pick a random value between 1 and 26, then use that for a letter. Repeat that five times and you have a five-letter string!

Whether or not this is a "good" or "fast" algorithm is up to you. You haven't defined what "good" or "fast" mean, so I'm unable to judge. You may have different criteria than I do.

Note that this will generate all strings that have five letters in them. These will probably not be words. Judging from your sample code you want all strings that have five letters in them, not words that have five letters in them.

Answer 5

public void wordCreator(int length){
    Random rnd=new Random();
    String word;
    do{
        word="";
        for(int j=0; j<length; j++){
            int index=rnd.nextInt(data.length);   //data is a String array letter of the alpabet
            word+=data[index];
        }
    }while(wordMap.containsValue(word));
    wordMap.put(i, word);
    i++;

}

Here is your algorithm