描述一个包含n个元素的排列时，可以看到第一个元素所在的位置有n个可能性，因此可以用0到n-1之间的一个数字来描述它。对于下一个元素结束的位置，您还有剩余的n-1个可能性，所以可以用0到n-2之间的一个数字来描述它。
类推直到你得到n个数字。
以n = 5为例，考虑将abcde带到caebd的排列。
a，即第一个元素，最终处于第二个位置，因此我们将其分配给索引1。b最终位于第四个位置，原本应该是第3个，但是现在只剩下2个，因此我们将其分配给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的数字表示的最大数字必须比只使用数字k+1表示的最小数字低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]的规则要求，在i从i = 0到i = k的情况下，h[i] * w[i]的总和应等于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都是有效的。在我们的例子中，n=5时有正好120个这些数字，这恰好是不同排列的数量。因此，您可以看到我们编码的数字完全指定了所有可能的排列。
从可变基数解码
解码类似于转换为二进制或十进制。常用的算法如下:
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++;
}
这样就能正确将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;
for (index = 0; index < n; index++)
{
if (!set[index])
{
if (remainingPosition == s)
break;
remainingPosition++;
}
}
permuted[index] = list[i];
set[index] = true;
}
排列的常见表示方式
通常情况下，你不会像我们做的那样使用难以理解的方式来表示一个排列，而是根据每个元素在应用排列后的绝对位置来表示。例如，对于abcde到caebd的排列{1，2，0，1，0}通常表示为{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
{
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²)。如果需要多次应用排列，请先将其转换为常规表示形式。
