Как разработать алгоритм для определения всех возможных перестановок элементов?

В соответствии с просьбой, вот решение, которое я придумал после нескольких часов возни. Он состоит из трех основных частей: основного класса, выполняющего работу, класса Word и класса помощи словаря. (Есть также загрузчик для чтения списка слов из файла.)

Загрузчик:

public class Loader {

    public List<String> load(String fileName) throws IOException {
        List<String> wordList = new ArrayList<>();
        InputStream is = getClass().getClassLoader().getResourceAsStream(fileName);
        BufferedReader br = new BufferedReader(new InputStreamReader(is));

        String currentLine = br.readLine();
        while (currentLine != null) {
            if (!"".equals(currentLine)) {
                for (String word : currentLine.split(" ")) {
                    wordList.add(word);
                }
            }
            currentLine = br.readLine();
        }

        br.close();

        return wordList;
    }
}

Слово:

public class Word {
    private final String word;
    private final Character[] characters;

    public Word(String word) {
        this.word = word;
        characters = new Character[3];
        characters[0] = word.charAt(0);
        characters[1] = word.charAt(1);
        characters[2] = word.charAt(2);
    }

    public String getWord() {
        return word;
    }

    public Character getCharacter(int index) {
        return characters[index];
    }

    @Override
    public String toString() {
        return getWord();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Word word1 = (Word) o;

        if (word != null ? !word.equals(word1.word) : word1.word != null) return false;
        // Probably incorrect - comparing Object[] arrays with Arrays.equals
        return Arrays.equals(characters, word1.characters);
    }

    @Override
    public int hashCode() {
        int result = word != null ? word.hashCode() : 0;
        result = 31 * result + Arrays.hashCode(characters);
        return result;
    }
}

Основной причиной для класса Word является предварительное вычисление составляющих символов.

Словарь:

public class Dictionary {
    private final List<Word> wordList;
    private final Set<Word> wordSet;
    private final Map<Character, List<Word>> firstLetterMap;
    private final Map<Character, Word[]> firstLetterArrayMap;


    public Dictionary(List<String> wordList) {
        this.wordList = wordList.stream().map(Word::new).collect(toList());
        this.wordSet = new HashSet<>();
        wordSet.addAll(this.wordList);

        this.firstLetterMap = this.wordList.stream()
                .collect(groupingBy(
                        w -> w.getCharacter(0)
                ));
        this.firstLetterArrayMap = new ConcurrentHashMap<>();
        for (Map.Entry<Character, List<Word>> entry : firstLetterMap.entrySet()) {
            Word[] ws = new Word[entry.getValue().size()];
            entry.getValue().toArray(ws);
            firstLetterArrayMap.put(entry.getKey(), ws);
        }
    }

    public List<Word> getWords() {
        return new ArrayList<>(wordList);
    }

    public Word[] getWordsArray(Character c) {
        return Optional.ofNullable(firstLetterArrayMap.get(c)).orElseGet(() -> new Word[0]);
    }

    public boolean isValidWord(Word word) {
        return wordSet.contains(word);
    }
}

Здесь особо нечего объяснять. Он содержит список слов и карту для поиска слов по их первой букве. Он также имеет метод для проверки слова.

Основная программа:

public class Tester {

    private final Loader loader;

    public Tester() {
        loader = new Loader();
    }

    public static void main(String[] args) {
        new Tester().run2();
    }

    public void run2() {

        Map<Set<Word>, String> validBoards = new ConcurrentHashMap<>();
        try {
            List<String> words = loader.load("scrabble-3-letter.txt");
            Dictionary dictionary = new Dictionary(words);
            List<Word> allWords = dictionary.getWords();
            Map<Word, String> checked = new ConcurrentHashMap<>();


            System.out.println("Start search...");
            long start = System.currentTimeMillis();

            allWords.parallelStream().forEach(w -> {
                checked.put(w, "");
                Word[] list1 = dictionary.getWordsArray(w.getCharacter(0));
                Word[] list2 = dictionary.getWordsArray(w.getCharacter(1));
                Word[] list3 = dictionary.getWordsArray(w.getCharacter(2));
                for (int i = 0; i < list1.length; ++i) {
                    Word w1 = list1[i];
                    if (checked.get(w1) != null) {
                        continue;
                    }
                    for (int j = 0; j < list2.length; ++j) {
                        Word w2 = list2[j];
                        for (int k = 0; k < list3.length; ++k) {
                            Word w3 = list3[k];
                            if (evaluate(w1, w2, w3, dictionary)) {
                                validBoards.put(new HashSet<>(Arrays.asList(w1, w2, w3)), "");
                            }
                        }
                    }
                }
            });
            long end = System.currentTimeMillis();

            System.out.println("Found " + validBoards.size() + " unique boards in " + (end - start) + " ms");

            String forPrint = validBoards.keySet().stream()
                    .map(ArrayList::new)
                    .map(this::boardToString)
                    .collect(Collectors.joining("\n"));
            writeToFile(forPrint, ".\\scrabble-sudoku-output.txt");

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void writeToFile(String data, String fileName) throws IOException {
        BufferedWriter writer = new BufferedWriter(new FileWriter(fileName));
        writer.write(data);

        writer.close();

    }

    private boolean evaluate(Word first, Word second, Word third, Dictionary dictionary) {
        Word firstV = buildVerticalWord(first, second, third, 0);
        Word secondV = buildVerticalWord(first, second, third, 1);
        Word thirdV = buildVerticalWord(first, second, third, 2);

        return dictionary.isValidWord(first) && dictionary.isValidWord(second) && dictionary.isValidWord(third)
                && dictionary.isValidWord(firstV) && dictionary.isValidWord(secondV) && dictionary.isValidWord(thirdV)
                && boardUniqueness(first, second, third, firstV, secondV, thirdV);
    }

    private boolean boardUniqueness(Word w1, Word w2, Word w3, Word w4, Word w5, Word w6) {
        Set<Word> checkDup = new HashSet<>();
        checkDup.add(w1);
        checkDup.add(w2);
        checkDup.add(w3);
        checkDup.add(w4);
        checkDup.add(w5);
        checkDup.add(w6);
        return checkDup.size() == 6;
    }

    private static Word buildVerticalWord(Word first, Word second, Word third, int index) {
        return new Word("" + first.getCharacter(index) + second.getCharacter(index) + third.getCharacter(index));
    }

    private String boardToString(List<Word> board) {
        StringBuilder sb = new StringBuilder();
        List<Word> sortedWords = new ArrayList<>(board);
        sortedWords.add(buildVerticalWord(board.get(0), board.get(1), board.get(2), 0));
        sortedWords.add(buildVerticalWord(board.get(0), board.get(1), board.get(2), 1));
        sortedWords.add(buildVerticalWord(board.get(0), board.get(1), board.get(2), 2));
        sortedWords.sort(Comparator.comparing(Word::getWord));
        sb.append(sortedWords.stream().map(Word::getWord).collect(Collectors.joining(", ")));
        return sb.toString();
    }
}

Это вторая попытка (отсюда run2()). Первым был грубый перебор, выбирающий по одному слову в строке из полного списка и затем проверяющий, допустимы ли вертикальные слова. Излишне говорить, что такой подход был не очень эффективным. (Мой список содержит 1347 слов, так что нужно проверить 2474829630 комбинаций.)

Второй подход, направленный на сокращение количества комбинаций, заключается в проверке только тех комбинаций строк, которые имеют шанс быть действительными.

Вот как это работает: Мы перебираем полный список слов. В каждой итерации выбранное слово «w» является первым столбцом. Затем мы отфильтровываем три списка возможных строк на основе первой, второй и третьей буквы w.

Эти сокращенные списки намного меньше полного списка, и мы проводим исчерпывающий поиск по этим спискам. Для каждой из этих комбинаций первый столбец остается неизменным.

Оценка проверяет, что каждое из 6 слов допустимо и что действительно есть 6 уникальных слов. Любая допустимая комбинация сохраняется как набор на карте. Набор должен перезаписывать любые дубликаты, а карта необходима для параллелизма.

Последний шаг — запись в файл. Кажется, это не работает блестяще, поэтому я хотел бы изменить это.

В цикле мы отслеживаем, какие слова w мы использовали. Если w1 совпадает с w, мы пропускаем его. Это потому, что каждая (допустимая) комбинация из 6 слов имеет две возможные формы.

A A A
B B B
C C C

такой же как

A B C
A B C
A B C

РЕДАКТИРОВАТЬ

Поиск всех решений требует времени, но найти какое-то решение можно быстро. Это требует двух дополнительных строк кода.

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

// ....
public Dictionary(List<String> wordList) {
    this.wordList = wordList.stream().map(Word::new).collect(toList());
    Collections.shuffle(this.wordList); // Shuffle here
    this.wordSet = new HashSet<>();
    wordSet.addAll(this.wordList);
// ....

Это сделает все последующие списки слов и коллекции перетасованными, что сделает каждый новый прогон уникальным.

В основной цикл программы, в run2(), добавьте оператор return в самом внутреннем цикле при нахождении допустимой доски:

                    if (evaluate(w1, w2, w3, dictionary)) {
                        validBoards.put(new HashSet<>(Arrays.asList(w1, w2, w3)), "");
                        return; // Return here to end search
                    }

Причина, по которой это возврат, а не какой-то другой разрыв, заключается в том, что мы находимся внутри лямбда (внешний цикл - это Stream.forEach()), поэтому это приведет к выходу из лямбда-выражения.

Я ожидал найти одну (1) действующую доску с этим изменением, однако по какой-то причине вместо этого я получил около 1310 (точное число варьируется). Кажется, он завершит полный внешний цикл один раз перед остановкой.

Счастливых праздников!