面向对象的排列生成
4.86/5 (10投票s)
面向对象地生成排列的教程文章。
摘要
从一个生成字符串所有排列的通用算法开始，我展示了典型的简单过程式版本，然后是面向对象版本。注意到该算法在返回给调用者之前生成所有排列，然后我展示了两个迭代器风格的版本，让调用者控制排列的生成。其中一个是“内向外”版本，另一个使用线程通过一个简单的协程机制。那个版本最后发现不支持在完成之前停止迭代，所以我纠正了它。
可下载的代码包含了这些程序变体。整个过程中使用的编程语言是Java，但也有一个C#示例和一个Haskell示例，供参考。
目录
引言
一个经典的面试编程问题是——或者至少曾经是——编写一个程序来生成字符串的所有排列。
我过去喜欢这个问题，因为它有一个简单优雅的递归解决方案，在白板上写起来很容易。在面试中想出一个好的递归解决方案过去能给面试官留下深刻印象，尤其是如果你能以“数学归纳法”的方式很好地解释它。
最近，我对那个简单的解决方案有了两个额外的想法。第一个是，递归解决方案可以说是过程式编程的缩影，但它的面向对象变体是什么样的呢？在白板上正确地写出来会同样容易吗？
第二个想法更有趣：假设你实际上需要在程序中使用一个排列生成器（我从来没有用过），那么你可能根本不想要递归解决方案，它会在返回给调用者之前生成所有排列——并处理它们。相反，你想要一个面向需求的、即迭代器风格的解决方案，你可以在需要时从中获取解决方案。这种解决方案在过程式语言中可能更难表达，而且你无法轻易地将递归解决方案改为面向需求的解决方案，但面向对象的解决方案可能更容易适应。而且你仍然可以在白板上做到吗？
下面我将使用我最不喜欢的面向对象编程语言Java，来简单探讨这些问题。（不是我最不喜欢的可以进行面向对象编程的语言：那会是Perl。）它是我最不喜欢的，因为由于它的历史，它是一门非常简单的语言，尽管它确实是面向对象的，但它并没有真正的语法来真正地表达，因此你的代码会变得非常冗长。但尽管如此，它如今仍然是普遍的教学语言，也是这类讨论的通用语。
过程式排列：简单的递归解决方案
（如果你已经知道生成排列的简单递归方法，请跳至面向对象方法 这里。）
我首先要说的是（在白板上），我希望抽象出实际如何处理生成的排列。所以我会快速定义一个标准的“动作”接口
public interface Action {
void next(String s);
}
然后，一个实现Action的类，我会先写主过程。Permute将是生成排列的过程
public final class RecursivePermute {
public static void main(String... args) {
final String p = args.length > 0 && args[0].length() < 0 ? args[0] : "abcd";
Permute(new Action() {
public void next(String s) {
System.out.println(s);
}
}, p);
}
...
在任何给定的递归级别，该过程接受当前排列和尚未包含在排列字符串中的字符“尾部”。它取出该尾部的第一个字符，并创建当前排列的所有变体，将该字符插入其中——包括在当前字符串之前和之后。它当然是一个接一个地这样做，每次递归调用剩余的尾部，以便下一级别的所有排列都将被生成。
实际生成排列的递归过程将接受一个额外的参数，除了要排列的字符串之外：尾部。我们将从最外层级别开始，使用一个0长度的字符串，然后下一个内层递归级别将有一个1长度的字符串，然后下一个级别将处理长度为2的字符串，依此类推。
因为我们必须在递归中传递尾部——而且Java没有默认参数——我们实际上必须编写两个过程：用户将调用的一个，和一个2个参数的辅助函数。
public static void Permute(Action a, String p) {
// (Argument validation elided for clarity)
if (p.length() > 0) {
Permute(a, p, "");
}
}
private static void Permute(Action a, String tail, String p) {
assert a != null && p != null && tail != null && tail.length() > 0;
for (int i = 0; i < p.length()+1; i++) {
String nextp = p.substring(0, i) + tail.charAt(0) + p.substring(i);
if (tail.length() > 1) {
Permute(a, nextp, tail.substring(1)); // recursive step here
} else {
a.next(nextp); // break the recursion here
}
}
}
这就是递归解决方案，在最后一个框里。
但实际上，你已经可以看到，对于一个完整的可运行解决方案，Java要求所有过程都必须是某个类的方法，并且没有其他语言中缩短代码的语法糖（如默认参数），所以它相当冗长。如果面试官能大致解释一下如何将它放入一个类中，我自己就不会要求面试者写所有样板代码了。
（实际上，如果我跳过Action部分，直接在递归结束时进行System.out.println()，这个例子会稍微短一些。但我稍后需要动作抽象，当我将其转换为“拉式”过程时。）
函数式排列：单行代码
哦，我猜你可能会认为我只是在抱怨Java需要我多打多少字。为了好玩，以Haskell编写的这个完全可运行的程序会是什么样子？
import Data.List
permute [] = [[]]
permute (x:xs) = [ pre ++ [x] ++ post | ys <- permute xs,
let ss = splits ys, (pre,post) <- ss ] where
splits a = zip (inits a) (tails a)
哦。这是完全可执行的代码。而且这甚至不是你能做到的最好的。看看Sebastian Sylvan提供的这个替代方案：
perms xs = [ x:ps | x <- xs, ps <- perms (xs\\[x]) ]
好吧，我不会解释这两个程序。第一个，我写的那个，我花了大约5分钟使用Haskell Platform编写和完全测试，之所以花了这么长时间，只是因为我不确定在哪里能找到inits和tails函数。
函数式编程可以让你非常简洁地表达算法，一旦你习惯了，就会非常清晰。但它需要一种不同于过程式或面向对象编程的思维方式。我鼓励你去了解它；你可以在网上通过教程和论文，或者通过书籍来学习，但需要一些学习才能变得有效。但这是值得的！一旦你能从函数式角度看待问题，即使在使用过程式或面向对象语言时，也能极大地提高思考清晰度。
面向对象排列：排列步骤的链式处理
那么面向对象的版本是什么样的呢？不是一个递归过程，其中每一层递归将排列好的字符串传递给下一层，后者插入一个字符，而是我们将有一系列对象，每个对象将排列好的字符串传递给链中的下一个对象，后者插入一个字符。
链中将有一个对象对应于初始字符串中要排列的每个字符；它们都将是同一个类的实例，该类实现Action，这将把它们链接在一起。链中还将有一个最终对象，它是调用者想要的Action。
有了这个想法，代码几乎会自己写出来。main方法（和Action接口）与我们之前的一样，所以我们只编写新代码，我们首先创建作为排列链链接的类。每个实例都保存其要插入的字符，通过其自己的next()接收新的要排列的字符串，并将插入的字符串传递给它持有的Action。
private static final class PermuteStep implements Action {
private final Action a;
private final char c;
private PermuteStep(char c, Action a) {
this.c = c;
this.a = a;
}
public void next(String s) {
for (int i = 0; i <= s.length(); i++) {
String n = s.substring(0, i) + c + s.substring(i, s.length());
a.next(n);
}
}
}
这样，构建排列步骤链然后运行它来生成所有排列就很容易了。
public static void Permute(Action a, String p) {
// (Argument validation elided for clarity)
Action as = a;
for (char c : p.toCharArray()) {
as = new PermuteStep(c, as);
}
as.next("");
}
所以，面向对象版本几乎没有增加多少代码，甚至可能更容易理解。它绝对是简单白板解决方案的一个有力的竞争者。
面向对象版本的性能与递归版本相比如何？
首先，必须认识到在大多数情况下，这几乎无关紧要。生成单个排列的代码在两个版本中都包含的不仅仅是几次字符串连接和一次过程调用。几乎任何排列生成器的实际使用都会比生成它本身花费更多代码来处理每个排列字符串。即使是这个例子中简单的out.println(s)，处理每个排列的代码量也远大于生成它的成本。
但是可能存在一些例子，其中使用每个排列的成本很低，例如，如果你因为某种原因生成了所有排列，但立即通过某种廉价测试过滤掉了大多数。在这种情况下，我们可以研究生成单个排列的成本。
为此，我们发现只有三个实际差异。首先，面向对象解决方案创建固定数量的对象来形成链：每个对象对应初始字符串中的一个字符。递归实现不这样做，但它确实在每个级别创建“尾部”并将其传递下去。事实上，它最终会创建比面向对象版本更多的字符串，并且通常比面向对象版本创建的固定数量的排列步骤对象更多的对象。
其次，递归实现通过堆栈传递（至少）两个参数（暂时忽略Action）。在过程式语言中，这两个字符串将是传递到堆栈的唯一参数。面向对象版本只在堆栈上传递一个字符串，但还必须传递接收对象。无论哪种方式，两种方法之间的堆栈使用量似乎都会非常相似。
最后，在这两种情况下，字符串或对象都将通过指针间接访问，但编译器或JIT编译器将确保常用值（例如，要插入的字符）被保留在机器寄存器中以便快速访问。
我猜测（未经测量）在生成排列的成本方面，递归实现和面向对象版本将非常相似，如果它确实很重要的话。
迭代器风格：按需生成每个排列
现在是时候看看“按需”或迭代器风格的排列生成了。
如前所述，递归风格的排列生成器的缺陷在于它一次性生成所有排列，然后才返回给调用者。那是一种用例，但我认为更常见的是希望排列按需一次生成一个。
面向对象语言通常为此提供抽象，通常称为迭代器。这通常由一个小接口体现，当一个类实现它时，该类的实例就可以在迭代器上下文中使用，例如在“for each”循环中。实例封装了迭代的当前状态。
使用迭代器很容易。但是如果没有语言支持来编写迭代器的实现，你可能需要更改算法，或者忍受将代码“内向外”转换的痛苦。也就是说，你必须将生成器变成一个状态机，并提供方法从中退出然后跳回算法的中间。
事实上，这正是C#通过迭代器块和yield return语句提供的支持。使用这些构造，可以非常简单地编写迭代器，编译器负责将其转换为状态机。（细节实际上很复杂，涉及编译器生成的类和方法。网上有很多文章解释C#如何实现迭代器块。）
下面是一个例子，说明在C#中将我们的递归算法转换为迭代器风格排列生成器有多么容易。注意，立即调用的next和递归调用的Permutations都在yield return语句中，这些语句实现了协程机制。同时还要注意返回类型是IEnumerable<>接口——正是这种返回类型加上yield return语句告诉编译器将此方法转换为迭代器。
static IEnumerable<string> Permutations(string p, string tail)
{
Debug.Assert( tail.Length > 0 );
for (int i = 0; i < p.Length+1; i++)
{
string nextp = p.Substring( 0, i ) + tail[ 0 ] + p.Substring( i );
if (tail.Length > 1)
{
foreach (string s in Permutations(nextp, tail.Substring(1)))
{
yield return s;
}
}
else
{
yield return nextp;
}
}
}
下面是一个C#主过程，它使用标准的foreach语句迭代字符串的所有排列。
static void Main( string[] args )
{
string p = args.Length > 1 ? args[ 0 ] : "abcd";
foreach (string s in Permutations("", p))
{
Console.Out.WriteLine("{1}", s);
}
}
迭代器风格：内向外生成排列
Java没有像C#那样的好方法让编译器为你构建协程。所以我们必须自己来。我们第一次尝试将排列链算法“内向外”转换。
在Java中，迭代器实现了java.util.Iterator接口，该接口是泛型的，类型为T，它迭代的对象。Iterator<T>有三个方法：boolean hasNext()、T next()和void remove()。hasNext和next是迭代器中的真正工作者（但我们已经看到了另一个Java的烦恼：我们必须实现remove，即使我们无意使用它——它在我们的迭代器上下文中没有意义，主要适用于集合）。
为了方便起见，我们还将实现java.lang.Iterable，这是一个接口，在某些上下文中（例如，在for语句中）用于类实例以获取迭代器。Iterable只有一个方法，iterator()，它返回一个迭代器。
无论如何，我们要构建与之前相同的对象链，链中的每个对象对应于排列中要包含的每个字符。但对象有所不同。首先，我们不是通过Action接口进行链接，该接口将排列好的字符串“推”到链中，而是通过“拉”排列的Iterator接口进行链接。
其次，我们将在链的末尾放置一个特殊对象，而不是调用者的Action，该对象仅返回一个零长度的字符串，并且只返回一次。
正如你所见，这个链相对于我们之前构建的面向对象链是“向后”操作的。
让我们从链的末尾开始。我们需要一个对象，它将是一个迭代器，并且在被迭代时，它将返回一个单一的0长度字符串。我们将从这里开始，因为它最简单，并且还将向我们展示Iterator接口的方法。
private static final class PermuteChainEnd implements
Iterator<String>,
Iterable<String> {
// Iterable<string />
@Override
public Iterator<String> iterator() {
return this;
}
// Iterator<String>
private boolean once = true;
@Override
public boolean hasNext() {
return once;
}
@Override
public String next() {
if (once) {
once = false;
return "";
} else {
throw new NoSuchElementException();
}
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
这是一个相当简单的迭代器。
现在我们将处理普通的PermuteStep，它构成了排列链。记住，我们将一次只从当前排列的字符串中返回一个插入的字符串。所以我们需要记住当前排列字符串中的位置。
此外，当我们到达当前字符串的末尾，并且没有更多位置可以插入我们的字符时，我们必须调用下一个链对象的迭代器来获取下一个要插入的字符串。
我们已经需要分割我们正在持有的字符串以便插入字符。所以我们将保留这两个分割，前缀和后缀，并将其作为我们的状态，以跟踪我们接下来需要做什么。
稍微思考一下，我们可以确定以下不变式：如果后缀没有字符，那么我们就完成了当前字符串的处理，并且是时候从链中的下一个对象获取新字符串了。然后，在这种情况下，我们将以当前排列作为该字符与之前的前缀连接的字符串返回。另一方面，如果后缀有字符，那么我们将后缀的第一个字符移到前缀的末尾，并将连接后的前缀、字符和后缀作为当前排列返回。
考虑到这个不变式，我们可以看到如何初始化我们的链实例，以及如何确定是否还有剩余的排列。
这是代码。首先是类的样板代码和Iterable接口。我们必须保留的状态由四部分组成：我们的字符c，下一个链对象，我们有一个迭代器a，以及当前我们正在处理的排列的前缀和后缀字符串。
private static final class PermuteStep implements
Iterator<String>,
Iterable<String> {
private final Iterator<String> a;
private final char c;
private String suff;
private String pre;
private PermuteStep(char c, Iterator<String> a) {
this.c = c;
this.a = a;
this.pre = "";
this.suff = "";
}
@Override
public Iterator<String> iterator() {
return this;
}
根据上述不变式，我们看到如果我们的后缀仍有字符，则还有更多排列，或者如果没有字符了，则如果链中的下一个对象仍有排列可提供，则还有更多排列。
@Override
public boolean hasNext() {
return suff.length() > 0 || a.hasNext();
}
要实际返回下一个排列，我们需要从后缀中移出一个字符到前缀，或者从链中的下一个对象获取一个新后缀。
@Override
public String next() {
if (suff.length() > 0) {
this.pre += this.suff.charAt(0);
this.suff = this.suff.substring(1);
} else {
this.pre = "";
this.suff = a.next();
}
return this.pre + this.c + this.suff;
}
不要忘记为remove()提供实现，但我在这里跳过它。这就是PermuteStep类的全部内容，所以它不算太糟糕。
现在，我们必须构建排列链。我们将在包含PermuteStep和PermuteChainEnd的类中完成此操作。它与上面的面向对象解决方案没有太大区别。
public static Iterable<String> Permute(String p) {
// (Argument validation elided for clarity)
Iterable<String> a = new PermuteChainEnd();
for (char c : p.toCharArray()) {
a = new PermuteStep(c, a.iterator());
}
return a;
}
最后，让我们使用这个迭代器风格的排列生成链。它确实很简单：我们使用Java打算与迭代器一起使用的构造：for语句。
public static void main(String... args) {
final String p = args.length > 0 && args[0].length() < 0 ? args[0] : "abcd";
for (String s : Permute(p)) {
System.out.println(s);
}
}
好吧，完成了。但是，需要编写的代码比你想象的要多，尽管它更多的是迭代器方法的繁琐而不是其他任何事情。最棘手的部分是PermuteStep类中迭代器状态的表示。我很有信心我可以在白板上正确地做到这一点，但话又说回来，这是一个相当简单的算法。如果需要将更复杂的东西“内向外”转换怎么办？有没有其他方法可以从面向对象的算法获得迭代器风格的算法？
迭代器风格：通过线程生成排列
是的，有。而且它似乎会更简单。
正如上面提到的，我们真正想要的是一个Java缺乏的协程系统。但Java有线程，所以我们可以用线程来实现协程。即使这种实现比真正的协程“更重”，也不会太糟，而且对于某些用途来说，完全可以接受。
我们将把整个原始的面向对象排列生成链放入一个线程中（过程式递归例程同样适用），并让它一次一个地将生成的排列发送给主线程。主线程将做任何它想做的事情，并且每当需要下一个排列时，它就会等待它。
Java有一个非常好的类用于在两个线程之间传输对象，即java.util.concurrent.Exchanger。交换器为两个线程提供了一个同步点，它们合作使用它。第一个调用exchange()方法的线程提供一个对象。第二个线程调用它时，对象被交换，两个线程都继续——每个线程都获得了对方提供的对象。
我们将只在一个方向上使用交换器：将排列好的字符串从排列链提供给调用线程。因此，调用线程将用null替换对象。
我们将像以前一样使用Iterator接口，用于按需排列生成器。这意味着链的最后一个链接将是一个Action，它将新生成的排列与调用线程交换。调用线程将拥有迭代器对象。迭代器将创建排列链并在线程中启动它。然后，每当需要下一个对象时，它将使用交换器获取它。
现在，出现了一个并发症，因为Iterator接口。要使用迭代器，首先要调用它的hasNext方法来查看是否有下一个项，然后调用它的next方法来获取下一项。（另外，你可以在调用next之前多次调用hasNext，当然，如果你这样做，它也不能“消耗”下一项。）这意味着我们将不得不有一个单项前瞻缓存。我们将在hasNext调用时（如果可能）填充它，并在next调用时使用它。（当然，你实际上不必调用hasNext……——我们必须考虑这一点。）
我们新的排列生成类是一个迭代器（也是一个iterable），并且因为它还将运行排列链，所以它也是一个可运行的。
import java.util.Iterator;
import java.util.concurrent.Exchanger;
public final class CoPermute implements
Runnable,
Iterator<String>,
Iterable<String> {
private final Exchanger<String> exchanger = new Exchanger<String>();
那里是我们的交换器对象，它将在调用线程（持有迭代器）和排列生成线程之间共享。
PermuteStep类完全相同：这就是重点——面向对象排列生成器没有改变，我们只是用一个协程包装了它。
但是，链的末尾有所不同，因为那是我们将与主线程同步并将新排列字符串传递给它的地方。
private static class PermuteStart implements Action {
private final Exchanger<String> exchanger;
private PermuteStart(Exchanger<String> exchanger) {
// (Argument validation elided for clarity)
this.exchanger = exchanger;
}
@Override
public void next(String s) {
try {
exchanger.exchange(s);
} catch (InterruptedException e) {
}
}
}
唯一有趣的一行是我们将新排列传递给调用线程exchanger.exchange(s)。但我们必须处理InterruptedException异常，它可能由exchanger.exchange抛出，并且不是运行时异常。
我们不希望我们的线程被中断，所以我们只会吞掉这个异常。但不得不捕捉它只是为了让我们的代码能够编译，这很烦人。
下一步是启动排列生成器。构建排列链就像以前一样。要运行它，我们将启动我们自己（记住，我们是Runnable），在我们的run方法中，我们将启动生成器。最后，我们将处理一个细节：迭代器如何知道没有更多排列字符串了？答案是：我们将一个null从生成器线程交换到迭代器线程，这将是信号。
private Action a;
private CoPermute(String s) {
// (Argument validation elided for clarity)
a = new PermuteStart(exchanger);
for (char c : s.toCharArray()) {
a = new PermuteStep(c, a);
}
new Thread(this).start();
}
@Override
public void run() {
// Generate all permutations
a.next("");
// Signal end of permutations by exchanging a null reference
try {
exchanger.exchange(null);
} catch (InterruptedException e) {
}
}
这很容易。再次，我们不得不吞掉一个InterruptedException，但除此之外，代码相当干净。
现在，是时候实现迭代器了，它接收来自生成线程的排列。我们已经讨论过我们必须有一个单项前瞻，并且这是我们实现它的地方。
private String peek = null;
private boolean peeked = false;
private String lookAhead() {
if (!peeked) {
try {
peek = exchanger.exchange(null);
} catch (InterruptedException e) {
}
peeked = true;
}
return peek;
}
@Override
public Iterator<string /> iterator() {
return this;
}
@Override
public boolean hasNext() {
// If the peeked object is null,
// then there are no more permutations coming
return lookAhead() != null;
}
@Override
public String next() {
String p = lookAhead();
peeked = false;
if (p == null) {
throw new NoSuchElementException();
}
return p;
}
（不要忘记实现remove！还有那个该死的InterruptedException又来了！）
同样的类被用作迭代器和排列生成器运行者，这可能看起来有点奇怪。但没有必要将功能分成两个不同的类，并且功能在迭代器线程中Iterator接口的实现和排列生成线程的Runnable接口的实现之间平均分配。
至此，我们完成了，并且可以将其与面向对象实现和内向外迭代器实现进行比较。
这个版本是迭代器风格的版本，意味着它按需生成排列，我们认为这比原始的排列链版本更有用，后者在返回给调用者之前生成所有排列。
但就代码的复杂性而言，与面向对象实现相比，它多了很多。排列生成算法完全相同。所有新代码都用于从生成线程到迭代器线程的通信，创建生成线程以及实现迭代器。当然，我们需要代码来实现迭代器，但在这个版本中它更复杂。与内向外迭代器版本相比，我们发现原始算法没有改变——这是一个很大的优点！——并且所有增加的复杂性都被隔离了，而在内向外算法中，复杂性被添加到原始算法中（如果任务比排列生成更困难，“内向外”状态机可能会非常复杂）。
不过，所有这些线程和线程间通信的设置代码都是“一次性”成本，与生成被迭代对象的算法的大小和复杂性无关。你可以想象，如果那个算法本身更复杂，这些设置代码就不会更大或更复杂，所以它的复杂性和成本是固定的。我们已经超出了在面试中能正确完成的阶段，但作为家庭作业 Assignments 也不算太糟糕。
就运行时成本而言，这个版本肯定比面向对象版本或内向外迭代器版本更昂贵。首先，需要创建和运行一个线程。其次，每个生成的排列都需要两个线程同步，这本身就相当昂贵。
如果迭代器（在单独线程中）封装的算法足够复杂，这些额外成本可能并不显著。但也有其他方法可以摊销成本。例如，可以通过减少同步频率来降低同步成本。这可以通过一次返回多个对象，或者使用队列来解耦排列的生成和消费来实现，从而需要更少的同步（和更少的上下文切换）。java.util.concurrent.BlockingQueue可能是合适的选择。
嗯，我们的协程实现有问题？
那么，现在我们完成了？不完全是……事实上，我们的迭代器风格实现，通过一个充当协程的线程，存在一个重大缺陷。
如果我们不想生成所有排列怎么办？也许我们只是在寻找第一个满足条件的排列，然后我们就跳出循环。
我们来试试
public static void BrokenPermute(Action a, String p) {
for (String s : new CoPermute("abcde")) {
a.next(s);
if (s.charAt(0) == 'e') {
// There are still some permutations left!
break;
}
}
}
编译并正常运行。等等……它没有终止！事实上，如果你在main方法的末尾添加out.println("exiting!")，你会发现消息被打印出来了，但程序没有终止！
原因在于，排列生成线程已经生成了下一个排列，并在交换器中耐心地等待迭代器去获取它。所以线程仍然是活动的（挂起的，不是运行的）。
当控制离开for循环时，迭代器不再需要了。主线程不再有对它的引用。但它不是垃圾：它的run方法还没有返回。它卡在交换器里。
for循环不知道要通知线程它不再需要了。这几乎就像它在等待被中断……
哦。也许它确实需要被中断！也许这就是为什么InterruptedException不是运行时异常的原因：Java框架希望你知道，你经常需要计划让你的线程被中断，以便在必要时能够优雅地退出它们。
所以首先要了解的是，Java线程有一个机制，称为中断，当你需要一个线程优雅地退出时，就可以使用它。调用线程的interrupt方法会设置一个标志，线程本身可以并且应该不时地检查它。如果线程挂起在某种Java同步机制中，如wait、join或sleep，那么JVM在该线程中抛出InterruptedException。无论哪种情况，你都知道是时候退出了。
第二件事要知道的是，当for循环提前退出而没有耗尽迭代器时，它无法“通知”迭代器它不再需要了。你可能会认为，如果他们花了精力定义了一个很少需要的方法remove（如果你在遍历一个集合并想支持在遍历时删除项），那么他们可能会继续定义一个done方法，以便for语句可以告诉迭代器它将不再被使用，但没有，这并没有发生。
那么，我们该如何通知迭代器它不再需要了，以便它可以中断排列生成线程，并让它退出呢？
我们将使用令人恐惧的终结器。
请注意，网上有很多关于终结器的糟糕说法。很容易找到电子邮件和帖子，说终结器是邪恶的，而程序员即使在考虑使用终结器时也应该开枪自尽，从而提高整体编程质量。这有点夸张了。终结器确实是一个大而丑陋的疣，而且很容易误用（特别是如果你认为它们是构造函数的“反义词”——你也可以在网上找到很多文章这样说！），而且它们的性能永远不会特别好，但有些情况下你可以安全地使用它，并且需要它。这种情况就是其中之一。
终结器的两个主要问题是，你无法知道它们何时会运行，而且它们可能根本不运行。这意味着它们通常对于“清理”你持有的任何Java环境之外的资源都无济于事。例如，你不能依赖终结器将数据刷新到文件并确保它被写入磁盘，然后你的程序退出。它不必运行。你不能依赖终结器在完成使用持有它的对象后关闭数据库连接，因为它不会立即运行，而且在你完成之前，你可能会最终拥有太多对象持有太多打开的数据库连接，而无法创建你真正需要的连接。
终结器还有其他问题。大多数都与“自愈”对象有关。也就是说，你在一个正在被垃圾回收的对象的一个终结器中，而不是很好地消失，你将对自己的引用放在一些非垃圾对象中。从而让自己存活下来。在这些情况下，我认为，也许那些希望你开枪自尽的人是对的。另一个问题是，当你处于终结器中时，你持有的任何对象引用都可能指向已经被垃圾回收的对象！这使得编写终结器变得困难，可以肯定的是。
但在本例中，我们将在语言内部进行，并且我们只会使用终结器来中断我们的线程。此外，我们知道我们正在谈论的线程还没有被垃圾回收，因为——嗯，因为这就是问题所在。它仍然在交换器中等待。所以这种终结器的使用是安全和恰当的，如果你仍然想写一封侮辱我父亲母亲的恶毒邮件，不用费心，直接踢你的猫就好。
迭代器风格：通过线程生成排列，正确地
因此，继续上一节的讨论，我们将解决无法停止生成排列直到所有都生成完毕的问题。我们将通过给迭代器添加一个终结器来中断排列生成线程，然后我们将修改排列生成线程，使其检查是否被中断。
我们首先要做的就是确保迭代器是与运行排列生成线程的对象分开的对象。以前没有理由这样做，所以我们没有。但现在，我们绝对希望迭代器被垃圾回收，并且我们知道问题是线程没有被垃圾回收，所以我们必须将它们分开。
我们必须做的第二件事是处理InterruptedException异常。但我们不想直接处理它，因为如果我们这样做了，我们必须将它“通过管道”传回排列生成算法到线程运行者，而我们的目标是保持它不变。相反，我们将声明我们自己的运行时异常，并在InterruptedException出现时替换它。作为运行时异常，我们可以在更高层次（在调用树中）捕获它，而无需在沿途的每个方法上声明它。
这大致解释了，所以现在我将在不进一步评论的情况下提供代码。
首先，容器类，以及异常类REInterruptedException，我们将用它来通信排列链的关闭；与本地InterruptedException不同，这个类是一个运行时异常，不需要算法本身声明或处理。
package com.bakinsbits.interview;
import java.util.Iterator;
import java.util.concurrent.Exchanger;
/**
* This class simply holds the initial string to permute, until it is asked
* to cough up an iterator over all the permutations. It is at that time
* that the permutation chain is built, the thread started, and the iterator
* begun.
*/
public final class InterruptableCoPermute implements
Iterable<String> {
/**
* This is the runtime exception we'll throw from the end of the chain up
* to the beginning of the chain, to signal an interrupt.
*/
private static class REInterruptedException extends RuntimeException {
public REInterruptedException(Throwable cause) {
super(cause);
}
}
现在我们有了排列链的末尾，在那里完成的当前排列与迭代器线程交换。与之前相同，除了它将中断的异常转换为我上面解释的异常。
/**
* This class is the end of the permutation chain and is responsible for
* communicating, as a coroutine, with the caller. It takes the given
* string and waits to exchange it with the caller. (The return from the
* exchange is not used.)
*/
private static class PermuteStart implements Action {
private final Exchanger<String> exchanger;
private PermuteStart(Exchanger<String> exchanger) {
// (Argument validation elided for clarity)
this.exchanger = exchanger;
}
@Override
public void next(String s) {
try {
exchanger.exchange(s);
} catch (InterruptedException e) {
throw new REInterruptedException(e);
}
}
}
这是PermuteStep类，与之前完全相同，在我们将整个算法转换为迭代器风格的基于协程的实现过程中没有改变。
/**
* One step in the permutation chain, exactly as in OOPermute.
*/
private static class PermuteStep implements Action {
private final Action a;
private final char c;
private PermuteStep(char c, Action a) {
this.c = c;
this.a = a;
}
@Override
public void next(String s) {
for (int i = 0; i <= s.length(); i++) {
String n = s.substring(0, i) + c + s.substring(i, s.length());
a.next(n);
}
}
}
现在介绍容器类的构造函数。它所做的就是将要排列的字符串保存起来，以便在调用者请求迭代器时可用。
private final String stringToPermute;
/**
* Hold the string to permute until the iterator is requested.
*/
private InterruptableCoPermute(String s) {
if (s == null) {
throw new NullPointerException("s");
}
stringToPermute = s;
}
在看过组成排列链的步骤类及其末尾之后，这里是实现链头部的类。它负责启动链，并处理REInterruptedException，以便在不再需要线程时干净地终止它。
/**
* This is the head of the chain of permutation steps. It runs the entire
* chain, then signals the end of all permutations. And, it catches any
* InterruptedException or REInterruptedException because that means we
* no longer need any more permutations and we want this thread to exit
* quietly.
*/
private static class InterruptableCoPermuteChainHead implements Runnable {
private Action a;
private final Exchanger<String> exchanger;
public InterruptableCoPermuteChainHead(Action a, Exchanger<String> exchanger) {
this.a = a;
this.exchanger = exchanger;
}
@Override
public void run() {
try {
// Generate all permutations
a.next("");
// Signal end of permutations by exchanging a null reference
exchanger.exchange(null);
} catch (InterruptedException e) {
// eat this exception: we're done
} catch (REInterruptedException e) {
// eat this exception: we're done
}
}
}
现在是迭代器类。每次请求下一个项目时，它都会去交换器获取它来自排列线程链。这和以前一样。但这次，它有一个终结器。当此迭代器被发现为垃圾时，将调用终结器，它所做的就是中断排列线程。这样，这个迭代器就消失了。
/**
* This class is the iterator for the permutations. Each time the next
* permutation is requested via the iterator it syncronizes with the
* permutation chain and gets back the next result. It also implements
* a finalize method which interrupts the permutation chain, this is so
* that, if this iterator is abandoned before it has provided all
* permuations, then the permutation chain thread exits quietly.
*/
private static class InterruptableCoPermuteIterator implements
Iterator<String> {
private final Thread chain;
private final Exchanger<String> exchanger;
private String peek = null;
private boolean peeked = false;
public InterruptableCoPermuteIterator(Thread chain, Exchanger<String> exchanger) {
// (Argument validation elided for clarity)
this.chain = chain;
this.exchanger = exchanger;
}
/**
* A nice safe finalizer that does nothing but interrupt the permuation
* chain thread.
*/
@Override
protected void finalize() {
chain.interrupt();
}
/**
* Lookahead one permutation: Go ahead and exchange for the next generated
* permutation string, and save the result. But only do this if you haven't
* already.
*/
private String lookAhead() {
if (!peeked) {
try {
peek = exchanger.exchange(null);
} catch (InterruptedException e) {
throw new REInterruptedException(e);
}
peeked = true;
}
return peek;
}
@Override
public boolean hasNext() {
return lookAhead() != null;
}
@Override
public String next() {
String p = lookAhead();
peeked = false;
resetLookAhead();
return p;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
这是iterator()方法，它启动整个过程。它创建一个排列链，将其放在一个单独的线程中，创建一个迭代器实例，并将所有内容连接起来。
/**
* When the iterator is requested we set the whole thing up: Here we
* create the exchanger and the permutation chain. We put the permutation
* chain, with the exchanger, in its thread, and start it. Then we return
* an iterator that uses the same exchanger.
*/
@Override
public Iterator<String> iterator() {
final Exchanger<String> exchanger = new Exchanger<String>();
Action a = new PermuteStart(exchanger);
for (char c : stringToPermute.toCharArray()) {
a = new PermuteStep(c, a);
}
Thread chain = new Thread(new InterruptableCoPermuteChainHead(a, exchanger));
chain.setDaemon(true);
chain.start();
return new InterruptableCoPermuteIterator(chain, exchanger);
}
以及测试整个程序的main程序
public static void main(String... args) {
final String p = args.length >= 1 && args[0].length() > 0 ? args[0] : "abcd";
Permute(new Action() {
public void next(String s) {
System.out.println(s);
}
}, p);
// Now, let's try an iterator where we don't consume all permutations
System.out.println("");
BrokenPermute(new Action() {
public void next(String s) {
System.out.println(s);
}
}, p);
}
/**
* Generate all permutations of the given string, calling the given Action
* on each one.
*/
public static void Permute(Action a, String p) {
if (a == null) {
throw new NullPointerException("a");
} else if (p == null) {
throw new NullPointerException("p");
}
for (String s : new InterruptableCoPermute(p)) {
a.next(s);
}
}
public static void BrokenPermute(Action a, String p) {
if (a == null) {
throw new NullPointerException("a");
} else if (p == null) {
throw new NullPointerException("p");
}
// This exits normally!!?!
System.out.println("BrokenPermute iterating with for statement");
for (String s : new InterruptableCoPermute("abcde")) {
a.next(s);
if (s.charAt(0) == 'e') {
break;
}
}
// There are still some left!
}
}
这个程序会退出！与之前的版本不同。但是——这是一个重要的细节——它只有在iterator()方法中创建排列链线程时调用setDaemon()才会退出。
Java VM的规范规定，有两种线程：守护线程和非守护线程，并且VM将一直运行直到所有已启动的非守护线程都退出。其目的是让执行有用的工作的线程保持VM运行；这些是非守护线程。其他线程没有做有用的工作，大多数都在等待某个同步发生。它们是空闲的工人线程，或者在等待可能永远不会发生的网络输入，或者其他原因。在我们的例子中，排列链线程大部分时间都没有做有用的工作。大部分时间它只是在交换器中等待处理最后一个排列。如果没有人会调用它，因为主线程将退出，那么它就没有存在的理由。所以，我们将它变成一个守护线程，通过调用setDaemon，这样我们就可以退出程序，而不管垃圾回收是否已经处理并销毁了持有线程的迭代器。
我也不妨在此指出，尽管这个解决方案有效，并且如你所见，可以相当封装，但它的性能仍然不是最好的。在迭代器成为垃圾后的第一次垃圾回收运行时，终结器将运行并中断排列生成线程。排列生成线程将退出，它和整个排列链也将成为垃圾。但直到下一次垃圾回收运行，它们都不会被处理。我们只能接受。
总结
在本教程中，我描述了一种面向对象的方法来生成字符串的排列。这个问题并不复杂，但我觉得有趣的是，我创建的面向对象管道和递归解决方案一样简单易写和易于描述；也许有些人甚至觉得它更容易理解。虽然我确信这种解决方案不是我独有的，但我个人以前从未遇到过；当然，从未在面试中遇到过。尽管在过去20年中，人们对面向对象编程非常关注，但似乎许多程序员首先想到的是标准的面向过程解决方案。
此外，我指出原始解决方案（或解决方案）一次性生成所有排列然后返回给调用者，实际上并不太适合面向对象模型。迭代器更适合。所以，我展示了两种将基本算法转换为迭代器模型的方法。对于这个简单的排列方案，“内向外”转换算法并不算太糟糕，但对于更复杂的算法来说会很糟糕。将算法转换为协程的优点是它根本没有改变算法，所以它仍然能正常工作。但它需要大量的代码来组织，并且也有运行时成本。选择权在你。
文章修订历史
- 2011年3月23日：原始文章。