要描述n个元素的排列，您会看到对于第一个元素结束的位置，您有n种可能性，因此可以用0到n-1之间的数字来描述。对于下一个元素所处的位置，您还有n-1个剩余的可能性，因此可以用0到n-2之间的数字来描述。
等等直到您拥有n个数字。
作为对于n = 5的示例中，考虑使置换
abcde到
caebd。
a
（第一个元素）在第二个位置结束，因此我们将其分配为索引 1 。b
结束于第四个位置，该位置将是索引3，但它是剩余的第三个位置，因此我们将其分配为 2 。c
结束于第一个剩余位置，该位置始终为 0 。d
结束于最后一个剩余位置，该位置（仅在两个剩余位置中）为 1 。e
结束于唯一的剩余位置，索引为 0 。
因此，我们有了索引序列 {1,2,0,1,0} 。
现在您知道，例如在二进制数中，“ xyz”表示z + 2y + 4x。对于十进制数字，
它是z + 10y + 100x。每个数字乘以一定的权重，然后将结果相加。权重的明显模式当然是权重为w = b ^
k，其中b为数字的底数，k为数字的索引。（我将始终从右边开始计算数字，并从索引0开始为最右边的数字。同样，当我谈论“第一个”数字时，我指的是最右边的数字。）
的 理由 为什么数字的权重遵循此模式是可以通过从0到k中的数字来表示的最高数目必须正好1比，可以仅通过使用数字K +
1来表示的最低数目更低。二进制格式的0111必须比1000小1。十进制格式的099999必须比100000小1。
编码为可变基数
重要的规则是后续数字之间的间隔恰好为1。意识到这一点，我们可以用一个 可变基数
来表示索引序列。每个数字的基数是该数字的不同可能性的数量。对于十进制，每个数字都有10种可能性，对于我们的系统，最右边的数字将具有1种可能性，而最左边的数字将具有n种可能性。但是，由于最右边的数字（序列中的最后一个数字）始终为0，因此我们将其省略。这意味着我们剩下的底数是2到n。通常，第k个数字的底数为b
[k] = k +2。数字k所允许的最大值为h [k] = b [k]-1 = k + 1。
我们关于数字权重w [k]的规则要求h [i] * w [i]的总和（其中i从i = 0到i = k）等于1 * w [k + 1]。循环地说，w [k +
1] = w [k] + h [k] * w [k] = w [k] *（h [k] + 1）。第一个权重w [0]应该始终为1。从那里开始，我们有以下值：
k h[k] w[k]0 1 1 1 2 2 2 3 6 3 4 24 ... ... ...n-1 n n!
（一般关系w [k-1] = k！很容易通过归纳证明。）
转换序列得到的数字将是s [k] * w [k]的和，其中k从0到n-1。这里s
[k]是序列的第k个元素（最右边，从0开始）。例如，以我们的{1,2,0,1,0}为例，最右边的元素如前所述被去除： { 1,2,0,1 }
。我们的总和是1 * 1 + 0 * 2 + 2 * 6 +1 * 24 = 37 。
请注意，如果我们为每个索引取最大位置，我们将得到{4，3，2，1，0}，并转换为119。由于选择了数字编码中的权重，因此我们不会跳过任何数字，从0到119的所有数字均有效。恰好有120个，即n！在我们的示例中，对于n
= 5，恰好是不同排列的数量。因此，您可以看到我们的编码数字完全指定了所有可能的排列。
从基于变量的
解码解码类似于转换为二进制或十进制。常见的算法是这样的：
int number = 42;int base = 2;int[] bits = new int[n];for (int k = 0; k < bits.Length; k++){ bits[k] = number % base; number = number / base;}对于我们的可变基数：
int n = 5;int number = 37;int[] sequence = new int[n - 1];int base = 2;for (int k = 0; k < sequence.Length; k++){ sequence[k] = number % base; number = number / base; base++; // b[k+1] = b[k] + 1}这正确解码我们37回{1，2，0,1}（
sequence将
{1, 0, 2,1}在此代码示例，但无论......只要你适当的指数）。我们只需要在右端添加0（请记住最后一个元素对其新位置始终只有一种可能性）即可返回原始序列{1、2、0、1、0}。使用索引序列
排列列表您可以使用以下算法根据特定的索引序列排列列表。不幸的是，它是一个O（n²）算法。
int n = 5;int[] sequence = new int[] { 1, 2, 0, 1, 0 };char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };char[] permuted = new char[n];bool[] set = new bool[n];for (int i = 0; i < n; i++){ int s = sequence[i]; int remainingPosition = 0; int index; // Find the s'th position in the permuted list that has not been set yet. for (index = 0; index < n; index++) { if (!set[index]) { if (remainingPosition == s) break; remainingPosition++; } } permuted[index] = list[i]; set[index] = true;}排列的通用表示
通常，您不会像我们所做的那样直观地表示排列，而只是通过应用排列后每个元素的绝对位置来表示。我们的
abcdeto的示例{1、2、0、1、0}
caebd通常用{1、3、0、4、2}表示。从0到4（或通常从0到n-1）的每个索引在此表示形式中仅出现一次。
以这种形式应用排列很容易：
int[] permutation = new int[] { 1, 3, 0, 4, 2 };char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };char[] permuted = new char[n];for (int i = 0; i < n; i++){ permuted[permutation[i]] = list[i];}反转非常相似：
for (int i = 0; i < n; i++){ list[i] = permuted[permutation[i]];}从我们的表示转换为通用表示
请注意，如果我们采用算法使用索引序列对列表进行置换，并将其应用于标识置换{0，1，2，…，n-1}，我们将得到 逆
排列，以通用形式表示。（在我们的示例中为 {2，0，4，1，3} ）。
为了获得不可逆的预置换，我们应用了我刚刚展示的置换算法：
int[] identity = new int[] { 0, 1, 2, 3, 4 };int[] inverted = { 2, 0, 4, 1, 3 };int[] normal = new int[n];for (int i = 0; i < n; i++){ normal[identity[i]] = list[i];}或者，您也可以使用逆排列算法直接应用排列：
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };char[] permuted = new char[n];int[] inverted = { 2, 0, 4, 1, 3 };for (int i = 0; i < n; i++){ permuted[i] = list[inverted[i]];}请注意，所有以通用形式处理置换的算法均为O（n），而以我们的形式应用置换的算法为O（n²）。如果需要多次应用置换，请首先将其转换为通用表示形式。
