c# - 将字符串分解并重新排列成所有可能的组合

Question

我想将一个字符串分解并重新排列成所有可能的组合

假设我有一个字符串:ABCDEF

我想把它分解并输出所有可能的组合

组合(6,6) = 1

ABCDEF

组合(6,5) = 6

BCDEF
ACDEF
ABDEF
ABCEF
ABCDF
ABCDE

组合(6,4) = 15

BCDE
ACDE
ABDE
ABCE
....
....
....
etc.

组合(6,3) = 20

BCD
ACD
...
etc.

组合(6,2) = 15 公元前 AB 等等

但是输出也必须按字母顺序排列。

我该怎么做？

谢谢!任何帮助将不胜感激!

Answer 1

您可以从 Knuth 第 4 卷，分册 3 中获得算法(实际上是其中的一些算法)，但您必须将其从他的数学符号转换为 C#。

更新:当我考虑更多时，Fascicle 2(生成排列)实际上更有帮助。您可以从 http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz 免费下载尽管您需要 gunzip 和 PostScript 预览器才能阅读它。生成字符串“ABCDE”的子集是比较容易的部分。将其转换为数组 {'A', 'B', 'C', 'D', 'E'}，运行从 0 到 2^N-1 的 for 循环，其中 N 是数组长度，并处理每个值作为您保留的元素的位掩码。因此 00001, 00010, 00011,... 给你 "A", "B", "AB",...

困难的部分是生成每个子集的所有排列，因此您会得到“ABC”、“BAC”、“CAB”等。蛮力算法(如其他答案之一)会起作用，但会得到如果字符串很长，速度会很慢。 Knuth 有一些快速算法，如果原始字符串首先被排序，其中一些算法将按字母顺序生成排列。