Все возможные слова

Question

Я хочу создать все возможные 5-буквенные слова, используя a-z. Пожалуйста, предложите любые хорошие и быстрые алгоритмы.

Я пытался создать его, и это выглядит примерно так ...

     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

Вот пример генерации всех последовательностей для любого набора символов любой длины:

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);
        }
    }
}

На моем компьютере требуется около 250 мсек, чтобы пройти все 11 881 376 последовательностей.

Обратите внимание, что новый char[len] создается только один раз в начале и повторно используется как сборка для построения перестановок. Первый вызов iterate() начинается с pos из 0. Перейдите к циклу for, где он проходит через каждый из символов. Первый символ сборки установлен на это, и затем мы рекурсивно вызываем тот же метод, чтобы установить следующий на pos + 1. После того, как это произошло 5 раз, позиция будет на len. Это когда pos == len начинается в верхней части метода. Тогда он просто строит String из того, что собрано в build, и вот ваше слово.

Answer 2

Это можно сделать легко и без рекурсии (здесь, в 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);
}

или вы можете сделать это с переносом:

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;
}  

Вот версия кода antti.huima для Java 7.

Answer 4

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++;

}

Вот ваш алгоритм

Answer 5

Вот алгоритм, который вы можете попробовать в псевдокоде:

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

Вы должны быть в состоянии легко перевести этот псевдокод в правильный код Java. Единственный сложный бит - генерация случайной строки. Вы можете взять массив букв, выбрать случайное значение от 1 до 26, а затем использовать его для буквы. Повторите это пять раз, и у вас будет пятибуквенная строка!

Является ли это "хорошим" или "быстрым" алгоритмом, зависит от вас. Вы не определили, что значит «хорошо» или «быстро», поэтому я не могу судить. У вас могут быть другие критерии, чем у меня.

Обратите внимание, что при этом будут сгенерированы все строки с пятью буквами. Вероятно, это не будут слова. Судя по вашему примеру кода, вы хотите, чтобы все строки имели пять букв, а не слова с пятью буквами.