每天早上醒来时，您需要执行一组任务，然后才能上班或做其他您喜欢的事情。你有没有想过每一个可能的任务顺序，你可以开始新的一天？
使用 排列， 您可以尝试输入集的所有组合。正如您将在本文中了解到的那样，即使对于少量编号的集合，组合的数量也是惊人的。例如，如果您只有十件物品，您可以以超过三百万种方式组合它们！
在本文中，我们将构建一个名为 Permutations 的小型 Java 8 支持类，可用于单元测试、游戏策略评估、问题解决以及许多其他强大的应用程序。
数学
您不必阅读本章即可理解这篇文章。但是，它有帮助。所以，在跳到下一章之前，尽量坚持下去。
术语 排列 涉及按顺序排列集合的所有成员的过程，或者，如果集合已经排序，则重新排列（或从数学上讲 排列 ）集合的顺序。例如，如果我们有一个集合 {1, 2, 3}，我们可以用六种不同的方式排列该集合； {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}。
一个集合中 n 个不同对象的排列数称为 n 阶乘 ，数学上写为 n!。 n的价值！可以计算为 1 乘以所有小于或等于 n 的正整数。因此，如果我们采用之前的集合 {1, 2, 3}，我们将看到它具有三个不同的成员。这样，就会有3个！ = 1*1*2*3 = 6 种独特的组合。令人鼓舞的是，这与上面的例子一致，我们在上面列出了所有六种组合。细心的读者现在得出结论，可以忽略 1 的序列因数，因为 1 是 乘法恒等式 ，即对于任何数字 a，1*a = a 为真。在纯英语中，这意味着您可以跳过与 1 的乘法，因为无论如何您都会得到相同的结果。儿子！实际上是 1 乘以 2*3*....*n。
现在，如果我们生成一个集合中不同成员数量的列表并计算相应的 n 阶乘 ，我们将得到下表：
0！ 1（根据定义，1 不乘以任何东西）
1！ 1（显然你只能用一种方式排列单个项目）
2！ 2个
3！ 6（如上例）
4！ 24
5！ 120（一个字节可以容纳的最大 n 阶乘值（最大 2^7 = 127））
6！ 720
7！ 5040（可放入空头的最大 n 阶乘值（最大 2^15 = 32768））
8！ 40320
9！ 362880
10！ 3628800
11！ 39916800
12！ 479001600（可以放入 int 的最大 n 阶乘值（最大 2^31 = 2147483647））
13！ 6227020800
14！ 87178291200
15！ 1307674368000
16！ 20922789888000
17！ 355687428096000
18！ 6402373705728000
19！ 121645100408832000
20！ 2432902008176640000（可以放入 long 的最大 n 阶乘值（最大 2^63））
21！ 51090942171709440000
...
42！ 1405006117752879898543142606244511569936384000000000（~地球上的原子数）
如您所见，在代码中应用排列时必须小心，因为即使是少量项目，您也可能会遇到极长的执行时间。例如，如果您可以在 1 毫秒内评估任何给定的组合并且您有 16 个项目，则单个线程的挂钟时间将为 16!/1000 秒 > 600 年！
排列类
有许多方法可以用编程语言实现置换器。在这篇文章中，我的目标是为 Java 8 中的置换器提供尽可能短的代码，因此如果您能想出更短的代码，请在下面发表评论。因此，我选择了简单性而不是性能。
其次，我想使用 Java 8 Streams，允许与可用的强大 Stream 函数集成。
执行
我们需要的第一个方法是 n 阶乘 函数，它计算不同集合的唯一组合的数量。我之前写过一篇关于此的文章，您可以 在此处 阅读详细信息。这是它的样子：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
请注意，该函数将仅处理 0 <= n <= 20 的输入范围，因为 0 是为 n 阶乘 定义的最低输入值，而 20 对应于 long 可以容纳的最大返回值。
接下来我们需要的是一种返回任何给定输入列表的编号排列的方法。因此，例如，如果我们有一个包含两个项目“A”和“B”的列表，则第一个排列 (0) 是 {A, B}，第二个排列 (1) 是 {B, A}。如果我们有一个包含树项 {A, B, C} 的列表，那么我们有以下排列：
不。排列
-- --------------
0 {A, B, C}
1 {A, C, B}
2 {B, A, C}
3 {乙，丙，甲}
4 {C, A, B}
5 {C, B, A}
在我要利用的模式变得明显之前，我们需要制作另一个列表表。列表 {A, B, C, D} 的完整排列如下所示：
不。排列
-- --------------
0 {A, B, C, D}
1 {A, B, D, C}
2 {A, C, B, D}
3 {A, C, D, B}
4 {A, D, B, C}
5 {A, D, C, B}
6 {乙、甲、丙、丁}
7 {B, A, D, C}
8 {乙、丙、甲、丁}
9 {B, C, D, A}
10 {B, D, A, C}
11 {B, D, C, A}
12 {C, A, B, D}
13 {C, A, D, B}
14 {C, B, A, D}
15 {C, B, D, A}（在下面的示例中使用）
16 {C, D, A, B}
17 {C, D, B, A}
18 {D, A, B, C}
19 {D, A, C, B}
20 {D, B, A, C}
21 {D, B, C, A}
22 {D, C, A, B}
23 {D, C, B, A}
查看每行中的第一项，您会发现它按照输入列表的顺序变化。令 n 为输入列表中的项目数 (n = 4)，subFactorial 为 (n-1)！ (subFactorial = (4-1)!= 3!= 6) 那么列表中的第一项排列编号位于索引 no/subFactorial。在上面的示例中，排列 15 的第一项位于索引 no/subFactorial = 15/6 = 2，对应于“C”（请记住，“A”位于索引 0，“B”位于索引 1，因此向前）。
这意味着对于任何输入列表，我们可以通过根据上述算法选择第一个项目来减少问题，然后再次递归调用相同的方法，但现在输入列表中的项目数量减少了。经典的分而治之的方法。这是它的样子：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
这个辅助方法采用排列数 no，一个输入列表 in 和初始排序的项目，然后一个 out 列表用于在递归过程中构建结果。
正如常见的递归实践所指示的那样，我们从 基本情况 开始，在这种情况下我们处理递归将停止的微不足道的情况。如果 in List 为空，那么我们就准备好了，只需返回现在完成的 out 列表。
如果in List不为空，那么我们先计算前面提到的subFactorial是(in.size()-1)！如上所述。该值随后会在该方法中使用。
下一行实际上是方法中的所有逻辑。我们首先计算我们想要放在最前面的项目在 out List 中的索引。该项目的索引是 (int)(no/subFactorial)，我们将其从列表中删除。由于remove方法方便返回我们刚刚删除的item，我们可以直接使用remove的返回值，一步到位到out List的末尾即可。
现在我们已经将问题从 n 减少到 n-1，我们需要以适当的方式递归。我们调用我们的 permutationHelper() 方法，使用我们作为输入参数获得的相同输入和输出列表，但排列数 no 现在是前一个除法的 余数 。这是合乎逻辑的，因为我们之前只处理了除法的相应整体部分。因此，我们使用 no%subFactorial 调用，这是剩下的要处理的部分。
这真的是所有要做的。根据您的输入，这五行无辜的行可以在不到 1 毫秒或 2000 多年内执行。
辅助方法只是用来帮助我们编写我们在类中公开的真实置换器。这是暴露的包装：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
我们提供排列数 no 和我们想要用作方法输入的列表，我们只需创建输入和输出列表并调用辅助方法。简单的。
所以现在我们可以计算给定列表的任何排列。但是 Stream 支持仍然存在，它可以为我们提供排列列表流。既然我们有了 permutation() 方法，提供这样一个方法真的很简单。这是可以做到的：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
所有艰苦的工作都由免费支持惰性、并行性等的 LongStream 完成，我们只将长 Stream 映射到我们想要的内容。长流提供输入 longs 0, 1, 2, ..., (items.lenght)！然后我们将这些多头映射到相应的排列。这真的很简单。
请注意，我选择返回一个 Stream of Stream 而不是一个 Stream of List 或类似的东西。如果你想要一个列表流，你只需更改返回类型和映射。
现在我们已经完成了所需的一切，在开始使用一些示例之前，我将提供整个 Permutations 类：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
例子
我们首先使用以下代码片段测试我们的 factorial() 方法：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
这将打印出：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
这看起来令人鼓舞。从上一章我们知道，可以用六种方式组合三个不同的对象。所以现在我们想看看桌面上的事实：这些组合是什么？查看它们的一种方法是使用我们的 permutation() 方法。如果我们将以下代码添加到现有代码段中：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
我们将得到以下输出：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
哇！有用。它看起来与上一章中的表格完全相同。现在让我们使用 Permutaions.of() 方法进行如下旋转：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
Permutations.of() 方法将提供 {A, B, C} 的所有排列，然后我们将这些排列收集到列表中，然后像这样打印列表：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
有时我们只想在所有可能的顺序中生成一个序列，这也可以通过类似的方式轻松完成：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
这将产生：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
平行度
正如我提到的，我们从 Permutations.of() 获得的 Stream 支持并行性，如果您有大量的排列并且您想使用所有 CPU：s，这很好。为了能够检查哪些线程正在执行什么，我们将使用一个小的支持方法：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
现在，让我们通过运行以下行来检查正在使用哪些线程：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
我们会看到这样的东西：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
这是合乎逻辑的。我们所有的排列都由同一个线程处理（因为我们没有要求并行流）。现在，让我们修改测试线，使其看起来像这样：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
这将产生类似的东西；
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
显然，在我的计算机上，两个组合继续在主线程上执行，因为有两个其他线程（不均匀地）共享其余的工作。
懒惰
应该注意的是，Permutations.of() 中的 Stream 懒惰地生成组合序列（或根据需要使用其他词）。因此，如果我们设置了大量的组合，但只需要一个，流将只产生一个也是唯一的组合。举个例子，输入项有16个，对应的排列数非常多，堪比国家部：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
该行将立即完成并返回 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]，不出所料，这是第一个组合。
测试
排列非常适合测试！您问过自己多少次：“我是否尝试了所有可能的组合”。使用排列，您现在可以确定您已经测试了每个输入组合，就像在这个简单的大纲中一样（显然，您需要用更有用的东西替换 System.out.println）：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
早晨
那么，最佳的早晨是什么样的呢？好吧，如果你一个人在家，你的一天可能会以许多不同的方式开始，也许是这样的：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
所以现在你可以从中选择你最喜欢的：
public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
通过一些准备，即使是最后的组合也确实可行......
结论
排列是一个值得掌握的强大工具。
在这篇文章中，我设计了一个非常简短但相当高效的 Java 8 置换支持类的实现。
如果您正在编写单元测试，您绝对应该知道如何使用排列。
小心，不要撞到“渐近墙”并限制生成排列时使用的项目数量。
生活就是做出正确的选择，不是吗？
