将排名排列索引到其他排名排列中

Question

我正在按字典顺序考虑0,…,n-1的所有排列。我有两个排名，i和j，并被要求找到从第i个排列应用到第j个排列得出的排列的排名。

n=3的几个例子： p(3) = [1, 2, 0], p(4) = [2, 0, 1], result = [0, 1, 2], rank = 0

给定i=j=4，我们得到[2, 0, 1]作用于自己是[1, 2, 0]，排名为3。

目前为止我想到的是：我通过Lehmer代码将排名转换为它们各自的排列，计算所需的排列，再通过Lehmer代码将其转换回排名。

有没有人能建议一种方法来从其他两个排名中获取所需排列的排名，而无需实际计算排列？存储n！x n！数组不是一个选择。

-编辑-请注意，如果其他排序方式能够实现这一点，则我不必遵循字典顺序。

-编辑-n=3和n=4的n! x n！网格，以字典顺序排名。第i行索引到第j列以获得输出。请注意，n=3网格与n=4网格的左上角完全相同。

00|01|02|03|04|05|
01|00|03|02|05|04|
02|04|00|05|01|03|
03|05|01|04|00|02|
04|02|05|00|03|01|
05|03|04|01|02|00|

00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|20|21|22|23|
01|00|03|02|05|04|07|06|09|08|11|10|13|12|15|14|17|16|19|18|21|20|23|22|
02|04|00|05|01|03|08|10|06|11|07|09|14|16|12|17|13|15|20|22|18|23|19|21|
03|05|01|04|00|02|09|11|07|10|06|08|15|17|13|16|12|14|21|23|19|22|18|20|
04|02|05|00|03|01|10|08|11|06|09|07|16|14|17|12|15|13|22|20|23|18|21|19|
05|03|04|01|02|00|11|09|10|07|08|06|17|15|16|13|14|12|23|21|22|19|20|18|
06|07|12|13|18|19|00|01|14|15|20|21|02|03|08|09|22|23|04|05|10|11|16|17|
07|06|13|12|19|18|01|00|15|14|21|20|03|02|09|08|23|22|05|04|11|10|17|16|
08|10|14|16|20|22|02|04|12|17|18|23|00|05|06|11|19|21|01|03|07|09|13|15|
09|11|15|17|21|23|03|05|13|16|19|22|01|04|07|10|18|20|00|02|06|08|12|14|
10|08|16|14|22|20|04|02|17|12|23|18|05|00|11|06|21|19|03|01|09|07|15|13|
11|09|17|15|23|21|05|03|16|13|22|19|04|01|10|07|20|18|02|00|08|06|14|12|
12|18|06|19|07|13|14|20|00|21|01|15|08|22|02|23|03|09|10|16|04|17|05|11|
13|19|07|18|06|12|15|21|01|20|00|14|09|23|03|22|02|08|11|17|05|16|04|10|
14|20|08|22|10|16|12|18|02|23|04|17|06|19|00|21|05|11|07|13|01|15|03|09|
15|21|09|23|11|17|13|19|03|22|05|16|07|18|01|20|04|10|06|12|00|14|02|08|
16|22|10|20|08|14|17|23|04|18|02|12|11|21|05|19|00|06|09|15|03|13|01|07|
17|23|11|21|09|15|16|22|05|19|03|13|10|20|04|18|01|07|08|14|02|12|00|06|
18|12|19|06|13|07|20|14|21|00|15|01|22|08|23|02|09|03|16|10|17|04|11|05|
19|13|18|07|12|06|21|15|20|01|14|00|23|09|22|03|08|02|17|11|16|05|10|04|
20|14|22|08|16|10|18|12|23|02|17|04|19|06|21|00|11|05|13|07|15|01|09|03|
21|15|23|09|17|11|19|13|22|03|16|05|18|07|20|01|10|04|12|06|14|00|08|02|
22|16|20|10|14|08|23|17|18|04|12|02|21|11|19|05|06|00|15|09|13|03|07|01|
23|17|21|11|15|09|22|16|19|05|13|03|20|10|18|04|07|01|14|08|12|02|06|00|

以下是 n=4 的因子阶乘。为了精简，我省略了最后一位数字，该数字始终为零。

000|001|010|011|020|021|100|101|110|111|120|121|200|201|210|211|220|221|300|301|310|311|320|321|
001|000|011|010|021|020|101|100|111|110|121|120|201|200|211|210|221|220|301|300|311|310|321|320|
010|020|000|021|001|011|110|120|100|121|101|111|210|220|200|221|201|211|310|320|300|321|301|311|
011|021|001|020|000|010|111|121|101|120|100|110|211|221|201|220|200|210|311|321|301|320|300|310|
020|010|021|000|011|001|120|110|121|100|111|101|220|210|221|200|211|201|320|310|321|300|311|301|
021|011|020|001|010|000|121|111|120|101|110|100|221|211|220|201|210|200|321|311|320|301|310|300|
100|101|200|201|300|301|000|001|210|211|310|311|010|011|110|111|320|321|020|021|120|121|220|221|
101|100|201|200|301|300|001|000|211|210|311|310|011|010|111|110|321|320|021|020|121|120|221|220|
110|120|210|220|310|320|010|020|200|221|300|321|000|021|100|121|301|311|001|011|101|111|201|211|
111|121|211|221|311|321|011|021|201|220|301|320|001|020|101|120|300|310|000|010|100|110|200|210|
120|110|220|210|320|310|020|010|221|200|321|300|021|000|121|100|311|301|011|001|111|101|211|201|
121|111|221|211|321|311|021|011|220|201|320|301|020|001|120|101|310|300|010|000|110|100|210|200|
200|300|100|301|101|201|210|310|000|311|001|211|110|320|010|321|011|111|120|220|020|221|021|121|
201|301|101|300|100|200|211|311|001|310|000|210|111|321|011|320|010|110|121|221|021|220|020|120|
210|310|110|320|120|220|200|300|010|321|020|221|100|301|000|311|021|121|101|201|001|211|011|111|
211|311|111|321|121|221|201|301|011|320|021|220|101|300|001|310|020|120|100|200|000|210|010|110|
220|320|120|310|110|210|221|321|020|300|010|200|121|311|021|301|000|100|111|211|011|201|001|101|
221|321|121|311|111|211|220|320|021|301|011|201|120|310|020|300|001|101|110|210|010|200|000|100|
300|200|301|100|201|101|310|210|311|000|211|001|320|110|321|010|111|011|220|120|221|020|121|021|
301|201|300|101|200|100|311|211|310|001|210|000|321|111|320|011|110|010|221|121|220|021|120|020|
310|210|320|110|220|120|300|200|321|010|221|020|301|100|311|000|121|021|201|101|211|001|111|011|
311|211|321|111|221|121|301|201|320|011|220|021|300|101|310|001|120|020|200|100|210|000|110|010|
320|220|310|120|210|110|321|221|300|020|200|010|311|121|301|021|100|000|211|111|201|011|101|001|
321|221|311|121|211|111|320|220|301|021|201|011|310|120|300|020|101|001|210|110|200|010|100|000|

- Dave

---

如果您不坚持字典顺序，那么这是否类似于以一致的方式将两个小于“n”的值转换为一个小于“n”的值呢？ - גלעד ברקן

@גלעדברקן 我不这么认为。假设我们定义f(R, n, i, j)作为函数，它接受一些排列的秩序R（因此R是唯一排列的列表），n是排列的长度（元素0到n-1; |R|=n！），i和j是R中两个输入排列的索引，则f(R, n, i, j)是输出排列在R中的索引。我不在乎R是什么，但我认为这不是一个琐碎的问题。也许我误解了你的评论--你能澄清或举个例子吗？ - Dave

@גלעדברקן 是的，那就是目标。需要保持一致的特定方式是，当您使用R[i]的值作为索引进入R[j]时，得到的置换需要是R[f(R，n，i，j)]。对于R使用字典顺序很好，因为我们可以使用Lehmer编码相对快速地在排列和等级之间转换，这是我希望保留的功能，即使我对某些其他排名获得了很好的答案。 - Dave

你可以重新定义“排列” p 为 s 的意思，以表示 unrank(max(rank(s), rank(p)) - min(rank(s), rank(p)))。但这样计算排列需要对 s 和 p 进行排名。你能否提供更多关于如何实现该函数的上下文信息？ - גלעד ברקן

@גלעדברקן 不行，我不能重新定义排列。此外，当两个排列相同时（因此它们的秩相同），输出排列可能会有所不同。将上面的第二个示例与字典顺序中的i=j=0进行比较。在任何R下，这两个都将具有max-min = 0，但生成的排列不同。 - Dave

Answer 1

如果除了 R 之外，您也没有选择特定的 P，我们可以重新定义排列函数以便于可能的答案。下面的函数 newPerm 将按照与“索引到”排列函数相同的一致性方式对列表进行排列。

以下示例未针对效率进行优化（例如，排名/取消排名可以在 O(n) 中完成）。输出的最后两行将重新定义的排列函数与“索引”排列函数进行比较 - 正如您所看到的，它们在映射到排列集时都生成相同数量的唯一排列。函数 f 将是问题的答案。

Haskell 代码：

import Data.List (sort,permutations)
import Data.Maybe (fromJust)

sortedPermutations = sort $ permutations [0,1,2,3,4,5,6]

rank p = fromJust (lookup p rs) where rs = zip sortedPermutations [0..]

unrank r = fromJust (lookup r ps) where ps = zip [0..] sortedPermutations

tradPerm p s = foldr (\a b -> s!!a : b) [] p

newPerm p s = unrank (f (rank p) (rank s))

f r1 r2 = let l = r1 - r2 in if l < 0 then length sortedPermutations + l else l

输出：

*Main Data.List> unrank 3
[0,1,2,3,5,6,4]

*Main Data.List> unrank 8
[0,1,2,4,5,3,6]

*Main Data.List> f 3 8
5035

*Main Data.List> newPerm [0,1,2,3,5,6,4] [0,1,2,4,5,3,6]
[6,5,4,3,0,2,1]

*Main Data.List> rank [6,5,4,3,0,2,1]
5035

*Main Data.List> length $ group $ sort $ map (tradPerm [1,2,5,0,4,3,6]) sortedPermutations
5040

*Main Data.List> length $ group $ sort $ map (newPerm [1,2,5,0,4,3,6]) sortedPermutations
5040

- גלעד ברקן

---

如果"f 3 8 = 5035"意味着使用第三个排列的元素索引到第八个排列，结果为第5035个排列，并且你的输出中描述的第三个和第八个排列是正确的话，那么我们应该有"unrank 5035 = [0,1,2,4,3,6,5]。也就是说，这似乎没有满足这样的性质：通过使用第一个排列的元素索引到第二个排列得到的排列的排名就是输出的排名。我只是根据你提供的输出进行推断，因为我不了解Haskell。 - Dave

关于Haskell的问题，你可以将代码理解为数学。rank和unrank只是在列表中查找索引或排列，tradPerm是传统的排列方式（通过“索引进入”）。 - גלעד ברקן

设n为任意正整数，R为0到n-1的所有排列的任意排名。设i和j为两个排名，I和J是在R下实现这些排名的排列。然后我们希望f(R,n,i,j)是在R下[J[I[0]]，J[I[1]]，J[I[2]]，J[I[3]]，...，J[I[n-1]]]的排名。也就是说，我们想使用第一个排列的元素作为第二个排列的索引。 - Dave

@DaveGalvin 是的，我理解你在问题中想要传统意义上的“排列”中的“排列”。我正在以不同的方式定义“置换”，以使您所需的函数变得微不足道。根据您希望如何实现整个过程，我的想法可能有用，也可能没有用。 - גלעד ברקן

@DaveGalvin 我理解。我之所以想到这个，是因为你说过你并没有对特定的 R 绑定。那么，我想，也许你对特定的 P 也没有绑定。Permuting 意味着将有序列表进行排序。我建议的函数会在与传统排列相同的一致性下将其重新排列。 - גלעד ברקן

Answer 2

我找到了一种算法，可以在线性时间内在排列和秩之间进行转换。虽然不完全符合我的要求，但可能已经足够好了。事实证明，我不关心字典序是很重要的。这个算法使用的排名很奇怪。我将提供两个函数，一个将秩转换为排列，另一个将排列转换为秩。

首先，要进行未排序（从秩到排列）。

Initialize:
n = length(permutation)
r = desired rank
p = identity permutation of n elements [0, 1, ..., n]

unrank(n, r, p)
  if n > 0 then
    swap(p[n-1], p[r mod n])
    unrank(n-1, floor(r/n), p)
  fi
end

接下来，进行排名：

Initialize:
p = input permutation
q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n)
n = length(p)

rank(n, p, q)
  if n=1 then return 0 fi
  s = p[n-1]
  swap(p[n-1], p[q[n-1]])
  swap(q[s], q[n-1])
  return s + n * rank(n-1, p, q)
end

这是伪代码。在我的项目中，我会小心地使用p的副本，以便在计算其排名时不会改变它。

这两个的运行时间都是O(n)。

有一篇很好的易读论文解释了为什么这样做：《线性时间排列和非排列》，作者是Myrvold & Ruskey，发表于2001年9月30日的《信息处理信函》第79卷第6期，281-284页。

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

- Dave