我有n个元素。为了一个例子，比方说，7元，1234567我知道有7！ = 5040排列可能这7个要素。

I have n elements. For the sake of an example, let's say, 7 elements, 1234567. I know there are 7! = 5040 permutations possible of these 7 elements.

我希望有一个快速算法，包括两种功能：

I want a fast algorithm comprising two functions:

F（号）之间的数字0和5039映射到一个唯一的置换，以及

f(number) maps a number between 0 and 5039 to a unique permutation, and

F'（置换）映射置换回它被从所生成的数

f'(permutation) maps the permutation back to the number that it was generated from.

我不关心数量和排列之间的对应关系，为每个排列有它自己唯一的编号。

I don't care about the correspondence between number and permutation, providing each permutation has its own unique number.

所以，举例来说，我可能具备的功能，其中

So, for instance, I might have functions where

f(0) = '1234567'
f'('1234567') = 0

最快的算法想到的是枚举所有排列在两个方向上建立一个查找表，这样一来，一旦创建了表，F（0）是O（1）和f（'1234567'）将一根绳子查找。然而，这是记忆饿了，尤其是当n变大。

The fastest algorithm that comes to mind is to enumerate all permutations and create a lookup table in both directions, so that, once the tables are created, f(0) would be O(1) and f('1234567') would be a lookup on a string. However, this is memory hungry, particularly when n becomes large.

任何人都可以提出另一种算法，将工作迅速，没有内存不足？

Can anyone propose another algorithm that would work quickly and without the memory disadvantage?

推荐答案

要描述n个元素的一个排列，你看到的是，第一个元素最终在这个位置，你有n个可能性，这样你就可以形容这与一个介于0和n-1。对于下一个元素最终在这个位置，你有N-1剩下的可能性，这样你就可以形容这一个介于0和n-2。照片 等等，直到你有n个数。

To describe a permutation of n elements, you see that for the position that the first element ends up at, you have n possibilities, so you can describe this with a number between 0 and n-1. For the position that the next element ends up at, you have n-1 remaining possibilities, so you can describe this with a number between 0 and n-2. Et cetera until you have n numbers.

对于N = 5为例，考虑到所带来的置换 ABCDE 到 caebd 。

As an example for n = 5, consider the permutation that brings abcde to caebd.

A ，第一个元素，最终在第二个位置，所以我们给它分配指数 1 B 结束在第四位，这将是指数3，但它的第三剩余的，所以我们给它的 2 。 C 结束的第一剩余位置，这是永远的 0 。 D 结束了在最后剩下的位置，这（出仅剩下的两个位置）是 1 电子结束了在仅存的位置，在索引的 0 a, the first element, ends up at the second position, so we assign it index 1. b ends up at the fourth position, which would be index 3, but it's the third remaining one, so we assign it 2. c ends up at the first remaining position, which is always 0. d ends up at the last remaining position, which (out of only two remaining positions) is 1. e ends up at the only remaining position, indexed at 0.

因此​​，我们必须在索引序列的 {1，2，0，1，0}

So we have the index sequence {1, 2, 0, 1, 0}.

现在你知道，例如在二进制数，XYZ是指Z + 2Y + 4倍。对于一个十进制数， 它的Z + 10 + 100倍。每个数字是由一些重量相乘，并将结果相加。在权重的明显的模式是当然的重量为w = B ^ K，用b的数目的基部和k的位的索引。 （我会永远指望从右边的数字，并从索引0开始对右边的数字。同样，当我谈到第一个数字我指的是最右边的。）

Now you know that for instance in a binary number, 'xyz' means z + 2y + 4x. For a decimal number, it's z + 10y + 100x. Each digit is multiplied by some weight, and the results are summed. The obvious pattern in the weight is of course that the weight is w = b^k, with b the base of the number and k the index of the digit. (I will always count digits from the right and starting at index 0 for the rightmost digit. Likewise when I talk about the 'first' digit I mean the rightmost.)

在的原因的为什么权重数字遵循这个模式是可以重新通过从数字0至K psented $ P $的最高数目必须比最低数量正好是1比可以只用数字K + 1 psented重新$ P $。在二进制，0111必须大于1000的十进制较低的一个，099999必须比100000较低的一个。

The reason why the weights for digits follow this pattern is that the highest number that can be represented by the digits from 0 to k must be exactly 1 lower than the lowest number that can be represented by only using digit k+1. In binary, 0111 must be one lower than 1000. In decimal, 099999 must be one lower than 100000.

编码为可变基 随后的数确切地说是1之间的间距是重要的规则。意识到这一点，我们可以通过的可变基数重新present我们的索引序列的。基座每个数字是该数字不同的可能性的量。对于十进制每位数有10的可能性，我们的系统最右边的数字将有1可能性，最左边将有n个可能性。但由于最右边的数字（在我们的序列中的最后一位数字）始终为0，我们离开它。这意味着我们留下了基地2到n。在一般情况下，第k数位将具有基材b [K] = K + 2允许位数K时最高值设为h [k]的= B [k]的 - 1 = K + 1

Encoding to variable-base The spacing between subsequent numbers being exactly 1 is the important rule. Realising this, we can represent our index sequence by a variable-base number. The base for each digit is the amount of different possibilities for that digit. For decimal each digit has 10 possibilities, for our system the rightmost digit would have 1 possibility and the leftmost will have n possibilities. But since the rightmost digit (the last number in our sequence) is always 0, we leave it out. That means we're left with bases 2 to n. In general, the k'th digit will have base b[k] = k + 2. The highest value allowed for digit k is h[k] = b[k] - 1 = k + 1.

我们的关于数字的权重w [k]的规则要求h的总和[I] *瓦特[I]，其中i从i = 0至i = k时，等于1 *瓦特[K + 1。表示循环地，瓦特[K + 1] = W [K] + H [k]的*瓦特[K] = W [k]的*（H [K] + 1）。所述第一权重w [0]应该总是1.从那里开始，我们有以下的值：

Our rule about the weights w[k] of digits requires that the sum of h[i] * w[i], where i goes from i = 0 to i = k, is equal to 1 * w[k+1]. Stated recurrently, w[k+1] = w[k] + h[k] * w[k] = w[k]*(h[k] + 1). The first weight w[0] should always be 1. Starting from there, we have the following values:

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！很容易被归纳证明。）

(The general relation w[k-1] = k! is easily proved by induction.)

我们从我们的变换序列随后将第[k]的总和*瓦特[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

The number we get from converting our sequence will then be the sum of s[k] * w[k], with k running from 0 to n-1. Here s[k] is the k'th (rightmost, starting at 0) element of the sequence. As an example, take our {1, 2, 0, 1, 0}, with the rightmost element stripped off as mentioned before: {1, 2, 0, 1}. Our sum is 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37.

请注意，如果我们采取了最大位置的各项指标，我们不得不{4，3，2，1，0}，并转换为119。因为在我们的数字编码的权重选择，让我们不要T跳过任何数字，所有数字0到119是有效的。有precisely 120这些，这是N！对于n = 5在我们的例子中，precisely不同的排列数。所以，你可以看到我们的EN codeD编号完整地指定所有可能的排列。

Note that if we take the maximum position for every index, we'd have {4, 3, 2, 1, 0}, and that converts to 119. Since the weights in our number encoding were chosen so that we don't skip any numbers, all numbers 0 to 119 are valid. There are precisely 120 of these, which is n! for n = 5 in our example, precisely the number of different permutations. So you can see our encoded numbers completely specify all possible permutations.

从变数基解码 解码类似，转换为二进制或十进制。常见算法是这样的：

Decoding from variable-base Decoding is similar to converting to binary or decimal. The common algorithm is this:

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
}

这正确去codeS我们37回{1，2，0，1}（序将 {1，0 ，2，1} 在此code的例子，但无论...只要你适当的指标）。我们只需要添加0右端（记得最后一个元素始终只有一个可能性，新的位置）来讨回我们的原始序列{1，2，0，1，0}。

This correctly decodes our 37 back to {1, 2, 0, 1} (sequence would be {1, 0, 2, 1} in this code example, but whatever ... as long as you index appropriately). We just need to add 0 at the right end (remember the last element always has only one possibility for its new position) to get back our original sequence {1, 2, 0, 1, 0}.

置换使用索引序列列表 - 可以使用以下算法来重排，根据一个特定的索引序列的列表。这是一个O（N²）算法，很遗憾。

Permuting a list using an index sequence You can use the below algorithm to permute a list according to a specific index sequence. It's an O(n²) algorithm, unfortunately.

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;
}

通用再$ P $排列的psentation 一般不要重新present置换为unintuitively作为我们所做的，而是简单地通过置换后的各元素的绝对位置被应用。我们的例子{1，2，0，1，0}为 ABCDE 到 caebd 通常重新presented由{1，3,0，4,2}。从0至4的每个索引（或在一般情况下，0到n-1）出现一次在这个重新presentation

Common representation of permutations Normally you would not represent a permutation as unintuitively as we've done, but simply by the absolute position of each element after the permutation is applied. Our example {1, 2, 0, 1, 0} for abcde to caebd is normally represented by {1, 3, 0, 4, 2}. Each index from 0 to 4 (or in general, 0 to n-1) occurs exactly once in this representation.

在这种形式应用的置换很简单：

Applying a permutation in this form is easy:

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];
}

反转是非常相似的：

Inverting it is very similar:

for (int i = 0; i < n; i++)
{
    list[i] = permuted[permutation[i]];
}

我们再presentation转换为普通重presentation 需要注意的是，如果我们把我们的算法重排列表，用我们的索引序列，并将其应用到身份置换{0，1，2，...，N-1}，我们得到的逆的置换，重新presented的常见形式。 （ {2,0，4,1，3} 在我们的例子）。

Converting from our representation to the common representation Note that if we take our algorithm to permute a list using our index sequence, and apply it to the identity permutation {0, 1, 2, ..., n-1}, we get the inverse permutation, represented in the common form. ({2, 0, 4, 1, 3} in our example).

要获得非反相premutation，我们应用置换算法我只是表明：

To get the non-inverted premutation, we apply the permutation algorithm I just showed:

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];
}

，或者你可以直接申请置换，通过使用逆置换算法：

Or you can just apply the permutation directly, by using the inverse permutation algorithm:

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²）。如果您需要申请置换几次，先将其转换为通用再presentation。

Note that all the algorithms for dealing with permutations in the common form are O(n), while applying a permutation in our form is O(n²). If you need to apply a permutation several times, first convert it to the common representation.