java - 创建一个给定单词的所有字谜的惰性流

Question

我正在尝试编写代码来创建一个包含给定单词的所有字谜的惰性流。我最初使用的是这段代码:

public static Stream<WordSequence> anagram(Stream<WordSequence> data, Object[] parameters) {
    return data.unordered().flatMap(WordSequence.forEachWord(Functions::allAnagrams)).distinct();
}

private static Stream<Word> allAnagrams(Word data) {
    if (data.length() <= 1)
        return Stream.of(data);
    Stream<Word> ret = Stream.empty();
    for (int i = 0; i < data.length(); i++) {
        char ch = data.charAt(i);
        String rest = new StringBuilder(data).deleteCharAt(i).toString();
        ret = Stream.concat(ret, allAnagrams(new Word(rest)).map(word -> new Word(ch + word.toString()))).unordered();
    }
    return ret;
}

(我正在使用我自己的 WordSequence 和 Word 类。)

我意识到这不是很有效，因为它只是连接了一堆空的单元素流，而且它还在返回流之前计算了所有的字谜。我在 Core Java 的某个地方发现了这个很棒的算法:

StringBuilder b = new StringBuilder(word);
for (int i = b.length() - 1; i > 0; i--)
    if (b.charAt(i - 1) < b.charAt(i)) {
        int j = b.length() - 1;
        while (b.charAt(i - 1) > b.charAt(j))
            j--;
        swap(b, i - 1, j);
        reverse(b, i);
        return new Word(b.toString());
    }
return new Word(b.reverse().toString());

如果你用一个词调用它，它会返回该词所有字谜序列中的下一个词。

我是这样实现的:

public static Stream<WordSequence> anagram(Stream<WordSequence> data, Object[] parameters) {
    class AnagramIterator implements Iterator<Word> {
        private final Word start;
        private Word current;
        private boolean done;

        AnagramIterator(Word start) {
            current = this.start = start;
        }

        @Override
        public boolean hasNext() {
            return !done;
        }

        @Override
        public Word next() {
            if (done)
                throw new NoSuchElementException();
            StringBuilder b = new StringBuilder(current);
            for (int i = b.length() - 1; i > 0; i--)
                if (b.charAt(i - 1) < b.charAt(i)) {
                    int j = b.length() - 1;
                    while (b.charAt(i - 1) > b.charAt(j))
                        j--;
                    swap(b, i - 1, j);
                    reverse(b, i);
                    current = new Word(b.toString());
                    done = current.equals(start);
                    return current;
                }
            current = new Word(b.reverse().toString());
            done = current.equals(start);
            return current;
        }

        private void swap(StringBuilder b, int i, int j) {
            char tmp = b.charAt(i);
            b.setCharAt(i, b.charAt(j));
            b.setCharAt(j, tmp);
        }

        private void reverse(StringBuilder b, int i) {
            int j = b.length() - 1;
            while (i < j) {
                swap(b, i, j);
                i++;
                j--;
            }
        }
    }
    return data.flatMap(WordSequence.forEachWord(w -> StreamSupport.stream(
            Spliterators.spliteratorUnknownSize(
                    new AnagramIterator(w),
                    Spliterator.DISTINCT + Spliterator.IMMUTABLE + Spliterator.NONNULL),
            false)));
}

但是，该算法存在问题。如果你给它一个以双字母结尾的单词，然后是另一个字母，其中双字母值在数值上小于单个字母，例如“ees”，你会得到这个变位词序列:

ees
ese
ees
and that repeats infinitely

该序列不包含“see”。

我该怎么做？

我的密码是on GitHub .

Answer 1

我想了想算法在做什么，灵光一闪。给定字符串“ese”，这就是算法的作用:

• 找到 i，在本例中它指向 s。
• 找到指向e的j。
• 交换 i - 1 和 j，交换两个 e。
• 从 i 开始反转字符串，交换 s 和 e。

我们希望它做的是让 j 也指向 s，这将使它交换第一个 e 和 s。那么我们如何修改算法来实现这一目标呢？

好吧，下面是查找 j 的操作:

• 首先将 j 指向最后一个 e。
• i - 1，即一个e，不大于j，即另一个e，所以j指向最后一个。

这是我的灵光一现:将比较从“大于”更改为“大于或等于”。我更改了它，它似乎奏效了!