置换：快速实现和允许多线程的新索引算法
5.00/5 (23投票s)
置换算法的快速实现
引言
本文是SimpleVar在StackOverflow上提出的问题“最有效地生成集合的排列”的延续。它展示了许多快速的排列算法实现。还有一项贡献是提供了一种独特的排列索引方法，可以根据字典序获取特定的排列。
目录
- 许多排列算法实现
- 一种能够索引字典序排列的新算法
- 一种多线程算法实现，它是两种算法的混合：
SaniSinghHuttunen和OuelletIndexed - 包含基准测试和所有提出的算法实现的 कोड
- 关于排列和多线程的一些额外一般信息
背景
排列的定义
根据维基百科
在数学中，排列的概念涉及将集合的所有元素按某种序列或顺序排列，或者如果集合已经有序，则重新排列（重排）其元素，这个过程称为置换。这与组合不同，组合是集合中不考虑顺序的选择。例如，用元组表示，集合 {1,2,3} 有六种排列：(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) 和 (3,2,1)。这些是这个三元素集合所有可能的顺序。再举个例子，一个字母全部不同的单词的变位词，就是其字母的排列。在这个例子中，字母已经在原始单词中排序，变位词是字母的重排。对有限集的排列的研究是组合学领域的一个主题。
排列与组合
有些人可能会混淆排列和组合。在排列中，项的数量始终相同，而组合则不是。
3个项目（a,b,c）的排列和组合示例
| 排列 数量 = n! | 组合 数量 = 2n |
| a, b, c | <空> |
| a, c, b | a |
| b, a, c | b |
| b, c, a | c |
| c, a, b | a, b |
| c, b, a | b, c |
| c, a | |
| a, b, c |
附加信息
一个包含x个元素的集合的可能唯一排列的数量是x!（x的阶乘）。也就是1 * 2 * 3 * …* x。可能性数量增长得非常快。
有些用途需要按字典序（排序）获取排列，而其他用途只需要任意顺序的所有排列。
排列算法/实现
许多实际的算法实现基于当前结果来查找下一个。
在测试代码时，测试一个可能性集合的所有排列可能很有用。要做到这一点，可以使用一个枚举所有可能值集合的排列的算法。由于可能的排列数量以阶乘顺序增长，因此通常会选择最快的算法，以最大限度地节省时间来完成有用的工作，而不仅仅是查找排列。
单线程算法能够以字典序提供排列，而多线程算法则不能保证以任何特定顺序得到结果，因为否则它会因排序机制而减慢速度，并失去其主要的并发优势。
| 作者 | 基准测试中的算法名称 | 基于算法 | Lex1 | Threadable2 | 注释 (安全代码/LINQ/Threadable/等等) | ||||
| Ouellet | OuelletHeap | Heap | 否 | 否 | 最快的ST整体 | ||||
| Sani Huttunen | SaniSinghHuttunen | Knuths | 是 | 否 | 最快的ST字典序 | ||||
| Erez Robinson | Erez Robinson | ? QuickPerm | 否 | 否 | |||||
| SimpleVar | SimpleVarUnsafe | ? | 否 | 否 | 不安全代码 | ||||
| SimpleVar | SimpleVarLex | ? | 是 | 否 | |||||
| Sam | Sam | ? | 是 | 否 | |||||
| Ziezi | Ziezi | ? | 否 | 否 | EO：我稍微修改了代码，使其能够与基准测试一起工作。 | ||||
| Ouellet | Ouellet Indexed | Ouellet | 是 | 是 | 详见最快的算法/实现细节部分 | ||||
| |||||||||
表1：在StackOverflow“最有效地生成集合的排列”（2018-06-5）上获得2个或更多赞的C#算法列表
基准测试结果
接下来的三个基准测试显示了提供的基准测试结果。每个结果表都附有图表，以方便观察算法实现之间的速度差异。
第一张图是所有实现的全局视图。但第二张和第三张图的算法实现越来越少，以便只显示重要的、速度相近的算法。
比率是实现所花费的时间除以最快实现的时间。这就是为什么最快的一个的比率总是“1”。
所有测试都在具有超线程CPU的机器上进行，该CPU有6个真实线程=12个线程。
并行化（使用所有线程）带来了约5倍的速度提升，在我使用的机器上。
11项（11! = 39,916,800 个排列）所有算法的基准测试结果
| 算法 | 8! | 8! 比率 | 9! | 9! 比率 | 10! | 10! 比率 | 11! | 11! 比率 |
| OuelletHuttunen MT (MT，非字典序) | 1 | 1 | 3 | 1 | 25 | 1 | 292 | 1 |
| OuelletHeap Heap (ST，非字典序) | 2 | 2 | 15 | 5 | 150 | 6 | 1659 | 5,68 |
| OuelletHuttunen (ST，字典序) | 2 | 2 | 15 | 5 | 158 | 6,32 | 1741 | 5,96 |
| Huttunen (ST, 字典序) | 2 | 2 | 16 | 5,33 | 161 | 6,44 | 1778 | 6,08 |
| SimpleVarLex (ST, 字典序) | 2 | 2 | 18 | 6 | 179 | 7,16 | 1966 | 6,73 |
| Ziezi -(改编，ST，非字典序) | 2 | 2 | 18 | 6 | 180 | 7,2 | 2004 | 6,86 |
| Sam (ST, 字典序) | 4 | 4 | 31 | 10,33 | 326 | 13,04 | 3474 | 11,89 |
| SimpleVarUnsafe (不安全，ST，非字典序) | 5 | 5 | 32 | 10,66 | 320 | 12,8 | 3696 | 12,65 |
| OuelletIndexed3 MT (MT，非字典序) | 7 | 7 | 34 | 11,33 | 341 | 13,64 | 4606 | 15,77 |
| Robinson (非字典序) | 7 | 7 | 49 | 16,33 | 525 | 21 | 6151 | 21,06 |
| OuelletIndexed1 MT (MT，非字典序) | 32 | 32 | 55 | 18,33 | 582 | 23,28 | 6893 | 23,60 |
| OuelletIndexed3 (ST，非字典序) | 21 | 21 | 208 | 69,33 | 2338 | 93,52 | 28328 | 97,01 |
| OuelletIndexed1 (ST，非字典序) | 31 | 31 | 299 | 99,66 | 3069 | 122,76 | 37518 | 128,48 |
| OuelletIndexed2 (ST，非字典序) | 40 | 40 | 332 | 110,66 | 3433 | 137,32 | 41965 | 143,71 |
| Pengyang - LINQ (非常慢，ST，字典序) | 317 | 317 | 3626 | 1208,66 | 46543 | 1861,72 | 636744 | 2180,63 |
13项（13! = 6,227,020,800 个排列）高效算法的基准测试结果
| 算法 | 8! | 8! 比率 | 9! | 9! 比率 | 10! | 10! 比率 | 11! | 11! 比率 | 12! | 12! 比率 | 13! | 13! 比率 |
| OuelletHuttunen MT (MT，非字典序) | 4 | 4 | 15 | 1 | 33 | 1 | 326 | 1 | 3967 | 1 | 44517 | 1 |
| OuelletHeap Heap (ST，非字典序) | 1 | 1 | 15 | 1 | 149 | 4,51 | 1641 | 5,03 | 19727 | 4,97 | 257105 | 5,77 |
| Huttunen (ST，字典序) | 1 | 1 | 15 | 1 | 162 | 4,90 | 1873 | 5,74 | 21179 | 5,33 | 275596 | 6,19 |
| OuelletHuttunen (ST，字典序) | 2 | 2 | 15 | 1 | 157 | 4,75 | 1736 | 5,32 | 20806 | 5,24 | 275854 | 6,19 |
| SimpleVarLex (ST，字典序) | 2 | 2 | 18 | 1,2 | 178 | 5,39 | 1975 | 6,05 | 23594 | 5,94 | 310474 | 6,97 |
| Ziezi(改编， ST，非字典序) | 1 | 1 | 17 | 1,13 | 180 | 5,45 | 1963 | 6,02 | 23577 | 5,94 | 312943 | 7,02 |
16项（16! = 20,922,789,888,000 个排列）前4名算法的基准测试结果
| 算法 | 11! | 11! 比率 | 12! | 12! 比率 | 13! | 13! 比率 | 14! | 14! 比率 | 15! | 15! 比率 | 16! | 16! 比率 |
| OuelletHuttunen MT (MT，非字典序) | 81 | 1 | 1047 | 1 | 13025 | 1 | 165949 | 1 | 2439328 | 1 | 36169342 | 1 |
| OuelletHeap Heap (ST，非字典序) | 334 | 4,12 | 4202 | 4,01 | 52733 | 4,048 | 715050 | 4,30 | 10740155 | 4,40 | 1.8E+08 | 4,98 |
| OuelletHuttunen (ST，字典序) | 410 | 5,06 | 5415 | 5,17 | 62251 | 4,77 | 851321 | 5,13 | 12787225 | 5,24 | 2.03E+08 | 5,61 |
| Huttunen (ST，字典序) | 401 | 4,95 | 4826 | 4,60 | 64608 | 4,96 | 869725 | 5,24 | 13089221 | 5,36 | 2.08E+08 | 5,73 |
最快的算法/实现细节
Sani Huttunen
Sanis 的算法实现是测试过的最快的字典序算法。
Ouellet Heap
这是维基百科上的“堆”算法的一个简单实现。算法的速度之所以快，是因为它每次只交换2个值，不多。没有递归。为了最大化速度，外部调用次数已最小化。内存占用非常小。
根据基准测试，它是最快的单线程算法。但它不容易多线程（并行化），因为无法从任何位置（索引）开始。此外，由于输出不是按字典序的，这为并行化增加了另一个复杂层。
Ouellet Indexed
排列的索引可以获取特定的排列。每个排列都有自己唯一的索引。该算法能够仅根据其字典序索引生成排列。它不依赖于任何先前的排列或任何其他状态。我创建该算法是为了能够并行化排列算法。能够从索引获取排列具有
优点
- 排列的索引使该算法易于并行化。它还使任何具有以下两个特征的排列算法能够并行化：1-排列的生成按字典序进行，2-下一个排列依赖于当前排列。
- 它可以直接获取任何一组排列，以便使用该特定集合而无需查找所有先前的排列。在开发/测试我的Ouellet Convex Hull Algorithm时，这将会非常有用。
缺点
- 该算法非常慢。即使在并行化该算法之后，它的性能仍然很慢。为了使并行化有用，它应该与另一个快速算法一起使用，其中
OuelletIndexed仅用于查找长序列的第一个排列。
注意：由于实际实现索引参数基于“long”类型。支持的最大项数为20。这是因为- 20! < 2^63（带符号long的63位）
- 21! > 2^64（无符号long的64位）
还在算法类中添加了一个辅助函数来获取给定排列的索引，可以在需要时随时调用。
在该算法的开发过程中引入了许多修改。其中大部分是为了提高速度。实际存在三个版本，它们在版本1、2和3之间基本上是相同的算法。
| OuelletIndexed的版本 | 描述 |
| 1 | 从左到右查找排列的第一个工作迭代。 |
| 2 | 尝试通过删除阶乘计算来提高版本1的性能。 |
| 3 | 将leftValues列表从值的“List”替换为布尔值数组，指示该值是否已使用。与其删除“List”中的值，不如将要删除的值标记为在相应的布尔数组中使用。 |
| 4 | 尝试从右到左查找排列。但未成功。 |
尽管版本3比版本1快得多，但即使是其多线程版本，它仍然非常慢。
算法如何工作
| permutationIndex | 排列（colIndex：3 =最左，0 =最右） |
| 0 | abcd |
| 1 | abdc |
| 2 | acbd |
| 3 | acdb |
| 4 | adbc |
| 5 | adcb |
| 6 | bacd |
| 7 | badc |
| 8 | bcad |
| 9 | bcda |
| 10 | bdac |
| 11 | bdca |
| 12 | cabd |
| … | … |
表2：4个值的前几个排列列表（4! = 24）
请注意表2中值的列表重复。如果我们认为列0是最右边，列3是最左边，那么前6项将包含“a”。我们可以观察到
- 第3列的条目重复6次。
- 第2列的条目重复2次。
- 如果我们有第4列，我们将有24项重复24次。
列索引条目的重复性取决于阶乘。该算法使用特殊的数据结构来管理可用值。开始时，每个值都放在一个列表中，最左边的索引为：0，最右边的索引为：（值的数量 - 1）。该列表称为leftValues列表。它是要作为当前计算的排列插入的潜在值的列表。
对于我们的例子，算法开始时，值按此顺序放入LeftValues列表中
valueIndex = 0 : avalueIndex = 1 : bvalueIndex = 2 : cvalueIndex = 3: d
观察表格中的重复，我们可以看到每列重复条目的数量与列索引的阶乘函数有关。如果我们使用colIndex作为列索引，valueIndex作为值索引，则可以将值索引表示为排列索引和列索引的函数。公式为
valueIndex = permutationIndex / colIndex! **
前面的公式适用于最左边的列。但由于以下问题，不能将其应用于所有其他列
- 使用该公式会导致值被先前使用过。例如，对于排列索引
0。公式将给出：aaaa。 - 对于最左边一列以外的任何列，很快就会得到大于可能
valueIndex的值索引。例如，对于前面的4个值输入：当permutationIndex = 8且排列为“bcad”时，计算columnIndex=2的valueIndex为8/2! = 4。但是valueIndex为4大于最大值索引，该索引应介于0和3之间（含）。
问题1可以通过使用leftValue列表（所有潜在值）并删除每个选定的值来轻松解决，当我们将其分配给列索引时。从leftValues列表中删除一个值会改变该索引与其值以及之后列表中所有值的对应关系。但这正是应该发生的。该值索引的新值将代表该索引处应使用的内容。对于所有后续值（如果有），也同样如此。
问题2可以通过应用另一个计算来轻松修复permutationIndex，以将其转换为一个范围，在该范围内，前面的公式**将变得有效。为此，我们只需获取permutationIndex除以(colIndex + 1)的阶乘的模数。
获取相对于排列索引和列索引的valueIndex的最终公式是
valueIndex = PermutationIndex % (columnIndex+1)! / columnIndex!
这给出了leftValues列表中（尚未使用的值）的相对索引。每次我们选择一个值时，它都会从leftValues列表中删除。我们应该从左到右处理列。处理最后一列时，列表中应该只剩下一个值，而这个值应该是该列的正确值。
此算法非常慢。如果需要，可以使用它来查找所有排列。要获取所有排列，我们可以遍历所有可能的排列索引，即：对于n个值，0 < permutationIndex < (n!-1)。但这样做比使用更有效的算法花费的时间要多得多。尽管非常慢，但它比大多数算法有一个很大的优点：它可以检索特定的索引排列。这个优点是并行化其他字典序排列算法所必需的关键。许多算法依赖于实际值来查找下一个。要并行化这些算法，我们需要从特定索引开始排列序列。为了实现这一点，需要使用排列索引器。这就是为什么这个算法如此有用的原因。
OuelletHuttunen
OuelletHuttunen是一种算法，可以查找从任何索引开始的任意数量的排列序列。第一个索引加上选择的排列数量的总和应小于可能排列的总数。
仅使用OuelletIndexed可以完成工作，但速度非常慢。这是因为OuelletIndexed非常慢。为了提高性能，我们仅在没有其他解决方案时使用OuelletIndexed。OuelletIndexed仅用于查找序列的第一个排列，然后我们使用另一种算法来迭代该排列序列。
保留的算法实现是将OuelletIndexed与Sani Huttunen的实现结合使用，因为它是按字典序排列的最快实现。
最终的算法OuelletHuttunen由两种不同的算法组成，以实现最佳性能
OuelletIndexed用于第一个排列SaniSinghHuttunen用于该序列的所有其他排列
注意：尽管OuelletHeap更快，但我们选择SaniSinghHuttunen算法而不是OuelletHeap。这是因为OuelletIndexed的索引基于字典序，而OuelletHeap算法不提供字典序的排列。这两种算法应该同步，因此应该使用相同的排列顺序。SaniSinghHuttunen的性能非常接近OuelletHeap，并且其结果是字典序的。
最终的算法很容易并行化，就像在基准测试中所做的那样。
对于项目数量在8个或更少时，可以观察到一个现象。因为大约“8！”时，排列的数量非常少，启动/初始化线程所需的时间比查找排列本身的时间还要多。
重要的多线程注意事项
在基准测试中，在测试算法期间，有一个全局变量用于计算迭代次数。该计数用于确保排列数量正确：permutationCount = valueCount!。
使用简单的全局变量来计算排列数量对于多线程实现来说不是一个有效的选择。由于线程并发，变量的递增不是在每次排列时发生的。添加锁定机制，使用SpinLock或Interlocked类，可以解决该问题。但它会增加大量的延迟。移除锁定机制，让全局变量单独存在，大大加快了速度（尽管计数错误），但性能远远低于预期。过了一会儿，我才意识到问题的根源在于同一个变量被不同线程访问，每个线程都在修改该值。这导致了已知的“虚假共享”问题。这是由于处理器架构及其线程缓存。这与我用Interlocked（或SpinLock）类修复的问题非常相似，但它发生在CPU层面，而不是代码层面。为了获得每个算法更现实的耗时，我设置了一个什么都不做的测试。这样，算法记录的时间纯粹是查找排列的时间，仅此而已。
我认为，为了在并行化算法时获得最佳性能，一个好的经验法则是，尽可能避免线程之间的任何共享读/写变量。只读变量不应产生相同的延迟效应。
基准代码
所有代码都在GitHub上提供，地址为https://github.com/EricOuellet2/Permutations
代码是用C#编写的，GUI是WPF。
基准测试中使用的算法是C#编写的，来自对Stack Overflow问题：最有效地生成集合的排列的回答。为了适应基准测试，可能进行了一些小的调整。
结论
感谢SimpleVar在StackOverflow上提出问题最有效地生成集合的排列。尝试找到最佳答案既有挑战性又有趣。我学到了一些很棒的东西。
希望您喜欢这篇文章，并且您也学到了一些东西或使用了其中的代码。
历史
- 2018年7月3日：初稿
- 2018年7月14日：小修正和补充，增加了历史记录
- 2018年7月20日：小修正（语法修正，项目符号定位）