要描述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²）。如果需要多次应用置换，请首先将其转换为通用表示形式。