0

我一直在研究一本书中的一个示例，该示例向您展示了如何将字符串排列为所有可能的组合，但是由于我在一般编程方面仍然是一个初学者，所以我实际上无法理解代码是如何工作的！

有人可以分析我提供的代码，并给我一个详尽的解释，说明一切的作用以及它是如何做到的吗？

非常感谢，

亚历克斯。

class PermuteString{
    String word;
    int index;
    PermuteString substringGenerator;
    public PermuteString(String s){
        word = s;
        index = 0;
        if(s.length() > 1){
              substringGenerator = new PermuteString(s.substring(1));
    }
}

public String nextPermutation(){
    if(word.length() == 1){
        ++index;
        return word;
    }
    else{
        String r = word.charAt(index) + substringGenerator.nextPermutation();
        if(!substringGenerator.morePermutations()){
            ++index;
            if(index < word.length()){
                String tailString = word.substring(0, index) + word.substring(index + 1);
                substringGenerator = new PermuteString(tailString);
            }
        }
        return r;
    }
}

public boolean morePermutations(){
    return index < word.length();
}

}

public class PermuteStringDemo {
public static void main(String[] args){
    PermuteString p = new PermuteString("opyn");
    while(p.morePermutations())
        System.out.println(p.nextPermutation());
}
}
4

2 回答 2

2

要生成排列，通常有两种方法

  1. 排名和取消排名
  2. 增量更改方法

此例程使用增量更改方法。基本上，它选择一些元素的顺序（与开始的顺序相同），然后通过打乱一个元素，然后递归地生成其下方所需的子排列，在选项树上上下移动。

permutation(everything) expands to

(select 1) + permutation(everything but 1)
(select 2) + permutation(everything but 2)
(select 3) + permutation(everything but 3)
...
(select n) + permutation(everything but n)

and

permuation(one item) expands to
(select item)

如果嵌套类morePermutations()中只有一个元素，这由which 返回 false 控制。PermuteString

如果 中有两个或多个字符PermuteString，index则跟踪所选项目，并在PermuteString移动索引时构造一个新的子。

当被问及下一个排列时，请求沿着嵌套PermuteString的 s 传播，直到一个字符串检测到它的孩子没有“下一个”排列，所以父级更新它的索引，并将它的前一个孩子换成一个新的，现在只是缺少“新”index字符。

（为了完整起见，排名和非排名的高级描述）

排名和取消排名的工作方式不同。人们知道特定大小的所有可能排列的计数，因此您创建一个排列映射到该大小内的“索引”。然后你创建一个从那个索引到一个值的反向映射。一个高级示例看起来像

the entire map for 3 items (6 permutations) would look like

(a, b, c) <=> 0
(a, c, b) <=> 1
(b, a, c) <=> 2
(b, c, a) <=> 3
(c, a, b) <=> 4
(c, b, a) <=> 5

(a, b, c) => 0
to find the next, just add one
0 + 1 => 1
1 => (a, c, b)

有一些正式的数学方法可以映射取消映射排列，而无需在内存中维护映射，但它们通常不被使用，因为索引增长得很快，通常会在数量超过 MAX_INT 时产生问题。

于 2013-08-06T16:01:57.573 回答
1

请记住，这不是置换字符串的最清晰或最简单的方法。事实上，就编程风格而言，它是说不出的猥琐。相反，它是一个说明递归形式的教科书示例。了解正在发生的事情的最简单方法是逐步进行。

从构造函数开始。它保存单词，将其索引设置为 0，然后（如有必要）从单词的第二个字符到最后一个字符创建一个新的 PermuteString 对象。完成后，您就拥有了一个 PermuteString 对象的链表：首先是“opyn”，然后是“pyn”、“yn”、“n”。很容易。

现在让我们看看迭代器。morePermutations() 相当于标准迭代器中的 next()；如果其索引仍小于其单词的长度，则返回 true。因此，您知道当 PermuteString 索引达到其单词的长度时，它就完成了。

最后，nextPermutation()。

  • 对于单字母单词，它返回它的单词并将其索引加 1。这意味着对 morePermutations() 的后续调用将从这里开始返回 false。这是有道理的：一个字母的单词只有一种排列方式——它本身。到目前为止，一切都很好。

  • N 个字母的单词呢，其中 N 是 2 或更多？在这里，考虑一下 PermuteString 对象的任务是：一个一个地返回其字母的每个排列，并在没有更多排列时通知其调用者。这样做的方法是将一个字母指定为“当前”字母，并使用子 PermuteString 生成其“其他”字母的所有可能排列。在每次迭代中，它首先返回一个由当前字母组成的字符串，然后是其他字母的某种组合。

  • 它实际上是如何做到这一点的，这是事情变得非常糟糕的地方。回想一下，在构造时，每个 PermuteString 对象都有一个指向其第一个字母的索引加上一个子 PermuteString 用于生成其第二个到最后一个字母的排列。因此，每次调用 nextPermutation()

    • 首先，它计算并将返回的下一个排列存储在“r”中。这只是当前索引字母加上其“其他”字母的下一个排列。很简单。

    • 然后，它会查看它的子 PermuteString 以查看它是否有更多的子串排列可以提供给我们。如果是这样，那么对 nextPermutation() 的调用基本上是完整的：它返回“r”并退出。

    • 但是，如果子 PermuteString 没有子弹，可以这么说，那么父级知道其当前起始字母的所有排列都已生成。它将索引前进到下一个字母。如果它已经到了它的词尾，那么它的所有排列都已经用尽了；请注意，对 morePermutations() 的所有后续调用现在都将返回 false。如果不是，那么对象就知道它必须开始用它的新起始字母生成排列。为此，它需要创建一个全新的子字符串生成器，其中包含所有其他原始单词中的字母——从位置 0 到刚刚结束的索引字母，加上从下一个字母到单词末尾的字母。这就是“tailString”（一个可怕的命名变量）计算的内容，下一行为这些其他字母创建 PermuteString 置换器。

这是自修改递归对象的一个​​很好的例子。为什么这个糟糕的实字代码？谢，有很多原因。它的变量命名非常倾斜。它在（递归）循环的中间更改 substringGenerator 的值，该循环的 if 条件检查是否完成。到达结束后调用 nextPermutation() 将导致随机越界异常，而不是有意义的异常。等等等等。但是，递归本身是合乎逻辑的，非常值得理解它是如何工作的。干杯!

于 2013-08-06T18:52:03.527 回答