如何计算第n个排列（或确定给定排列的词典序）？

Question

这个问题有两个部分，尽管我正在尝试编写一个Prolog实现，但解决其中一个问题可能会立即导致另一个问题的解决。

1. 给定整数列表的排列{1,2,...,N}，如何判断该排列在词典序中的索引？ 2. 给定数字k，如何计算数字{1,2...,N}的第k个排列？

我正在寻找一种比仅迭代“下一个排列”函数k次更好的算法。据我所知，应该可以直接计算这两个问题。

到目前为止，我想出来的方法是从左边看数字，在特定索引处告诉我之前有多少个排列，然后以某种方式将它们组合起来，但我不确定这是否会导致正确的解决方案。

- Jakub Arnold

---

这里有一个关于如何推导索引的答案：https://dev59.com/84Dba4cB1Zd3GeqPGqFX#24234429 - גלעד ברקן

Answer 1

考虑有多少种以数字1开头的排列方式，有多少种以数字2开头的排列方式，以此类推。假设n = 5，则24种排列方式以1开头，24种以2开头，以此类推。如果您想要查找排列方式k = 53，则48个以1或2开头的排列方式排除掉了，因此第53个是以3开头的排列方式中的第五个。

以数字3开头的排列方式中，每个数字开头为31、32、34或35的排列方式各有6种。因此，您正在寻找以（3,1）开头的第五个排列方式。每个以312、314和315开头的排列方式都有两种。因此，您正在寻找以315开头的两种排列方式中的第一种，即31524。

将这些内容转化为代码应该很容易。

- gnasher729

Answer 2

你还可以查看阶乘数系统，特别是有关排列的部分。 对于给定的数字k，您首先应该找到其阶乘表示，然后很容易地得到所需的排列（实际上是第(k+1)个排列）。

以k=5和数字{1,2,3}为例：

5 = 2*2! + 1*1! + 0*0! = (210)_!

因此，5的阶乘表示为210。现在让我们将该表示映射到排列中。我们从有序列表（1,2,3）开始。我们阶乘表示法中最左边的数字是2，因此我们要查找列表中索引为2的元素，即3（列表从零开始索引）。现在我们剩下列表（1,2）并继续进行该过程。在删除2后，我们阶乘表示法中最左边的数字是1，因此我们得到索引为1的元素，即2。最后，我们剩下1，因此{1,2,3}的第（k + 1）个（第6个）排列为{3,2,1}。

虽然需要一些时间来理解它，但它是一种相当有效的算法，并且易于编程。反向映射类似。

- Miljen Mikic

Answer 3

我将为您提供每个解决方案的概述:

给定一个整数列表 {1,2,...,N} 的排列，如何确定该排列在字典序排序中的索引？

要做到这一点，您需要问自己有多少个排列以 1 开头？答案是 (N - 1)!。现在，让我们来看一个例子：

3 1 2

有多少个由1 2 3组成的排列以1或2开头？答案是2*2!。这个问题排在前两个问题后面，因此它的索引至少为2*2!=4。现在检查下一个元素。有多少个由1 2组成的排列以0开头？没有。你完成了，索引是4。如果您想使用基于1的索引，可以添加1。

给定数字k，我如何计算数字{1,2 ...，N}的第k个排列？

给定4，我们如何得到3 1 2？我们必须找出每个元素。

第一个位置上可能有什么？如果我们有1，则最大索引可以是2！- 1 = 1（我使用从0开始计数）。如果我们有2，最大值可以是2 * 2！- 1 = 3。如果我们有3，最大值可以是5。所以我们必须有3：

3

现在，我们已经将问题简化为查找 1 2 的第 4 - 2*2! = 0 个排列，这是 1 2（您可以像上面那样进行递归推理）。

- IVlad