如何设计一个算法来计算所有可能的元素排列?

ubof19bj  于 2021-06-29  发布在  Java
关注(0)|答案(1)|浏览(282)

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

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

对于这个为拼字游戏玩家设计的数独版本,oxo是一个有效的单词(我使用一个txt文件作为有效单词的列表)。
我遇到的问题是:程序如何计算出水平和垂直组合在一起的所有3个字母单词(我将从这个子集中选择6个单词输出给用户)。
txt文件存储在一个集合中,因此每个单词都是一个字符串元素。我想循环遍历集合中的所有单词,并将每个单词分解成一个字符数组。但这似乎不太可能。你对如何产生所有可能的解决方案有什么想法吗?

aurhwmvo

aurhwmvo1#

按照要求,这是我经过几个小时的修改后提出的解决方案。它由三个主要部分组成:做作业的主类、单词类和词典帮助类(还有一个用于从文件中读取单词列表的加载程序。)
装载机:

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

单词类的主要原因是预先计算组成字符。
词典:

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

这里没什么好解释的。它包含单词列表和一个根据单词的第一个字母查找单词的Map。它还有一个验证单词的方法。
主程序:

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个唯一的单词。任何有效的组合都会保存为一个集合,在Map中。该集合应使任何重复项被覆盖,并且Map是并发所必需的。
最后一步是写入文件。这似乎不是很好的工作,所以我会考虑改变这一点。
在循环中,我们跟踪使用了哪些单词w。如果w1和w相同,我们跳过它。这是因为6个单词的每个(有效)组合有两种可能的形式。

A A A
B B B
C C C

与相同

A B C
A B C
A B C

编辑
找到所有的解决方案需要时间,但找到一些解决方案可以很快完成。它需要另外两行代码。
在字典构造函数中,在Map主单词列表后,在其上添加无序排列:

// ....
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(确切数字不同)的结果,而不是。似乎它会在停止前完成一次完整的外环。
节日快乐!

相关问题