快速排列 ->数量 ->置换映射算法 [英] Fast permutation -> number -> permutation mapping algorithms
问题描述
我有 n 个元素.举个例子，假设有 7 个元素，1234567.我知道有 7 个！= 这 7 个元素可能有 5040 个排列.
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(number) 将 0 到 5039 之间的数字映射到唯一排列，并且
f(number) maps a number between 0 and 5039 to a unique permutation, and
f'(permutation) 将置换映射回生成它的数字.
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.e结束于唯一剩余的位置，索引为 0.
a, the first element, ends up at the second position, so we assign it index 1.bends up at the fourth position, which would be index 3, but it's the third remaining one, so we assign it 2.cends up at the first remaining position, which is always 0.dends up at the last remaining position, which (out of only two remaining positions) is 1.eends up at the only remaining position, indexed at 0.
所以我们有索引序列{1, 2, 0, 1, 0}.
现在您知道，例如在二进制数中，xyz"表示 z + 2y + 4x.对于十进制数，
它是 z + 10y + 100x.每个数字乘以一些权重，然后将结果相加.权重中明显的模式当然是权重是 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 的数字可以表示的最高数字必须比可以由以下数字表示的最低数字正好小 1仅使用数字 k+1.二进制中，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 是重要的规则.意识到这一点，我们可以用一个可变基数来表示我们的索引序列.每个数字的基数是该数字的不同可能性的数量.对于十进制，每个数字有 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] * 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.从那里开始，我们有以下值:
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.)
我们从转换序列中得到的数字将是 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.
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.由于我们选择了数字编码中的权重，因此我们不需要'不要跳过任何数字，所有数字 0 到 119 都是有效的.其中正好有 120 个，即 n！对于我们示例中的 n = 5，正是不同排列的数量.所以你可以看到我们编码的数字完全指定了所有可能的排列.
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
}
这正确地将我们的 37 解码回 {1, 2, 0, 1} (sequence 在此代码示例中将是 {1, 0, 2, 1}，但无论如何......只要你适当地索引).我们只需要在右端添加 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;
}
排列的常见表示
通常，您不会像我们所做的那样不直观地表示排列，而只是通过应用排列后每个元素的绝对位置来表示.abcde 到 caebd 的示例 {1, 2, 0, 1, 0} 通常由 {1, 3, 0, 4, 2} 表示.在这个表示中，从 0 到 4(或者一般来说，0 到 n-1)的每个索引都只出现一次.
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];
}
反转非常相似:
for (int i = 0; i < n; i++)
{
list[i] = permuted[permutation[i]];
}
从我们的表示转换为通用表示
请注意，如果我们使用我们的算法使用索引序列对列表进行置换，并将其应用于恒等置换 {0, 1, 2, ..., n-1}，我们会得到 逆排列，以普通形式表示.(在我们的示例中为 {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).
为了得到非反转的前置换，我们应用了我刚刚展示的置换算法:
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²).如果你需要多次应用一个排列，首先将其转换为通用表示.
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.
这篇关于快速排列 ->数量 ->置换映射算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
