java如何设计算法来计算所有可能的元素排列？

Question

我正在尝试建立一个用字母而不是数字的数独游戏。将有一个空框，如下所示：

每一个小盒子都会填满一个字母，这样所有水平和垂直的字母都会形成单词。为了帮助用户，我会给他们6个字，这将工作，但他们必须找出如何安排这6个字。正确完成的方框示例：

对于这个为拼字游戏玩家制作的数独版本，oxo是一个有效的单词（我使用一个txt文件来列出有效的单词）

我的问题是：程序如何计算出水平和垂直组合在一起的所有3个字母单词？（我将从这个子集中选择6个单词输出给用户）

txt文件存储在一个集合中，因此每个单词都是一个字符串元素。我想循环遍历集合中的所有单词，并将每个单词分解成一个字符数组。但这似乎不太可能。你对如何产生所有可能的解决方案有什么想法吗

Answer 1

按照要求，这是我经过几个小时的修补后提出的解决方案。它由三个主要部分组成，一个主要的工作类，一个单词类和一个字典帮助类。（还有一个用于从文件中读取单词列表的加载程序。）

加载器：

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

编辑

找到所有解决方案需要时间，但找到一些解决方案可以很快完成。它需要另外两行代码

在字典构造器中，在映射主单词列表后，在其上添加一个shuffle：

// ....
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
                    }

它是一个返回而不是其他中断的原因是因为我们在lambda中（外部循环是Stream.forEach（）），所以这将退出lambda表达式

我的期望是找到一（1）个具有此更改的有效板，然而，由于某种原因，我最终得到了大约1310个（确切数字不同）结果。似乎它会在停止前完成一次完整的外循环

节日快乐