algorithm - 快速排列 -> 数字 -> 排列映射算法

Question

我有 n 个元素。举个例子，假设有 7 个元素，1234567。我知道有 7 个! = 这 7 个元素可能有 5040 个排列。

我想要一个包含两个函数的快速算法:

f(number) 将 0 到 5039 之间的数字映射到唯一的排列，并且

f'(permutation) 将置换映射回生成它的数字。

我不关心数字和排列之间的对应关系，只要每个排列都有自己的唯一编号。

所以，例如，我可能有函数，其中

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

想到的最快算法是枚举所有排列并在两个方向上创建一个查找表，这样，一旦创建了表，f(0) 将是 O(1) 而 f('1234567') 将是一个在字符串上查找。但是，这会占用大量内存，尤其是当 n 变大时。

任何人都可以提出另一种可以快速运行且没有内存缺点的算法吗？

Answer 1

要描述 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 的数字可以表示的最高数字必须比仅使用数字 k+1 可以表示的最低数字小 1。在二进制中，0111 必须比 1000 小 1。在十进制中，099999 必须比 100000 小 1。

编码到可 rebase
后续数字之间的间距恰好为 1 是重要规则。意识到这一点，我们可以用可 rebase 数来表示我们的索引序列。每个数字的基数是该数字的不同可能性的数量。对于十进制，每个数字有 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;
}

对于我们的可 rebase 数:

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

排列的常见表示
通常，您不会像我们所做的那样不直观地表示排列，而只是通过应用排列后每个元素的绝对位置来表示。我们的示例 {1, 2, 0, 1, 0} 用于 abcde至 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²)。如果您需要多次应用一个排列，首先将其转换为通用表示。