Create a lazy stream of all anagrams of a given word
我正在尝试编写代码来创建给定单词的所有字谜的惰性流。我最初使用的是这段代码:
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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) { |
(我正在使用我自己的
我意识到这不是很有效,因为它只是连接一堆空的和一个元素的流,它还在返回它们的流之前计算所有的字谜。我在某处的 Core Java 中找到了这个奇妙的算法:
1
2 3 4 5 6 7 8 9 10 11 |
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()); |
如果你用一个单词调用它,它将返回该单词所有字谜的序列中的下一个单词。
我是这样实现的:
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
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) { @Override @Override private void swap(StringBuilder b, int i, int j) { private void reverse(StringBuilder b, int i) { |
但是,该算法有问题。如果你给它一个以双字母结尾的单词,然后是另一个字母,其中双字母值在数字上小于单个字母,例如”ees”,你会得到这个字谜序列:
1
2 3 4 |
ees
ese ees and that repeats infinitely |
该序列不包括”看”。
我该怎么做?
我的代码在 GitHub 上。
我想到了算法在做什么,顿时灵光一现。给定字符串 “ese”,算法就是这样做的:
-
找到
i ,在本例中它指向 s。 -
找到指向 e 的
j 。 -
交换
i – 1 和j ,交换两个 e//’s。 -
从
i 开始反转字符串,交换 s 和 e。
我们希望它做的是让
好吧,这就是查找
的作用
-
首先将
j 指向最后一个 e。 -
i – 1 ,一个e,不大于j ,另一个e,所以j 指向最后一个e。
这是我的灵光一现:将比较从”大于”更改为”大于或等于”。我改变了它,它似乎奏效了!
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/267585.html