如何计算第 n 个排列（或告诉给定排列的字典顺序）？
How can I calculate n-th permutation (or tell the lexicographic order of a given permutation)?
这个问题有两个部分，但由于我正在尝试完成 Prolog 实现，解决一个问题可能会立即导致另一个问题的解决方案。
- 给定一个整数列表
{1,2,...,N} 的排列，我如何知道该排列在字典序中的索引是什么？
- 给定一个数字
k，我如何计算数字 {1,2...,N} 的第 k 次排列？
我正在寻找一种算法，它可以比仅迭代 next permutation 函数 k 次更好地完成此操作。 Afaik 应该可以直接计算这两个。
到目前为止我想出的是，通过查看左边的数字，我可以知道在特定索引处每个数字之前有多少排列，然后以某种方式将它们组合起来，但我不太确定如果这导致正确的解决方案。
想想有多少排列以数字 1 开头，有多少排列以数字 2 开头，等等。假设 n = 5，则 24 个排列以 1 开头，24 个排列以 2 开头，依此类推。如果您正在寻找排列，比如 k = 53，则有 48 个以 1 或 2 开头的排列，因此 #53 是以 3 开头的排列中的第五个。
在以 3、6 开头的排列中，每个排列都以 31、32、34 或 35 开头。所以您正在寻找以 (3, 1) 开头的第五个排列。有两个排列，每个排列都以 312、314 和 315 开头。因此，您正在寻找以 315 开头的两个排列中的第一个。即 31524。
将其转化为代码应该很容易。
我将给出每个解决方案的概要：
Given a permutation of a list of integers {1,2,...,N}, how can I tell what is the index of that permutation in lexicographic ordering?
为此，问问自己有多少排列以 1 开头？有(N - 1)!。现在，让我们做一个例子：
3 1 2
有多少 1 2 3 以 1 或 2 开头的排列？ 2*2!。这个肯定在那些之后，所以它的索引至少是2*2! = 4。现在检查下一个元素。 1 2 有多少种排列以 0 开头？ None。大功告成，索引为 4。如果您想使用基于 1 的索引，您可以添加 1。
Given a number k, how can I calculate k-th permutation of numbers {1,2...,N}?
给定4，我们如何得到3 1 2？我们必须找到每个元素。
第一名能有什么？如果我们有 1，最大索引可以是 2! - 1 = 1（我使用的是从零开始的索引）。如果我们有2，最大可以是2*2! - 1 = 3。如果我们有3，最大值可以是5。所以我们必须有 3:
3
现在，我们已经将问题简化为找到 1 2 的第 4 - 2*2! = 0 次排列，即 1 2（您可以像上面那样递归推理）。
你也可以看看阶乘数系统，尤其是关于permutations的部分。对于给定的数字k，你首先应该找到它的阶乘表示，然后很容易给出所需的排列（实际上，(k+1)-st排列）。
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，所以 (k+1)-st (6th) 排列{1,2,3} 是 {3,2,1}。
尽管理解它需要一些时间，但它是一种非常高效的算法并且易于编程。反向映射类似。
这个问题有两个部分，但由于我正在尝试完成 Prolog 实现，解决一个问题可能会立即导致另一个问题的解决方案。
- 给定一个整数列表
{1,2,...,N}的排列，我如何知道该排列在字典序中的索引是什么？ - 给定一个数字
k，我如何计算数字{1,2...,N}的第k次排列？
我正在寻找一种算法，它可以比仅迭代 next permutation 函数 k 次更好地完成此操作。 Afaik 应该可以直接计算这两个。
到目前为止我想出的是，通过查看左边的数字，我可以知道在特定索引处每个数字之前有多少排列，然后以某种方式将它们组合起来，但我不太确定如果这导致正确的解决方案。
想想有多少排列以数字 1 开头，有多少排列以数字 2 开头，等等。假设 n = 5，则 24 个排列以 1 开头，24 个排列以 2 开头，依此类推。如果您正在寻找排列，比如 k = 53，则有 48 个以 1 或 2 开头的排列，因此 #53 是以 3 开头的排列中的第五个。
在以 3、6 开头的排列中，每个排列都以 31、32、34 或 35 开头。所以您正在寻找以 (3, 1) 开头的第五个排列。有两个排列，每个排列都以 312、314 和 315 开头。因此，您正在寻找以 315 开头的两个排列中的第一个。即 31524。
将其转化为代码应该很容易。
我将给出每个解决方案的概要：
Given a permutation of a list of integers {1,2,...,N}, how can I tell what is the index of that permutation in lexicographic ordering?
为此，问问自己有多少排列以 1 开头？有(N - 1)!。现在，让我们做一个例子：
3 1 2
有多少 1 2 3 以 1 或 2 开头的排列？ 2*2!。这个肯定在那些之后，所以它的索引至少是2*2! = 4。现在检查下一个元素。 1 2 有多少种排列以 0 开头？ None。大功告成，索引为 4。如果您想使用基于 1 的索引，您可以添加 1。
Given a number k, how can I calculate k-th permutation of numbers {1,2...,N}?
给定4，我们如何得到3 1 2？我们必须找到每个元素。
第一名能有什么？如果我们有 1，最大索引可以是 2! - 1 = 1（我使用的是从零开始的索引）。如果我们有2，最大可以是2*2! - 1 = 3。如果我们有3，最大值可以是5。所以我们必须有 3:
3
现在，我们已经将问题简化为找到 1 2 的第 4 - 2*2! = 0 次排列，即 1 2（您可以像上面那样递归推理）。
你也可以看看阶乘数系统，尤其是关于permutations的部分。对于给定的数字k，你首先应该找到它的阶乘表示，然后很容易给出所需的排列（实际上，(k+1)-st排列）。
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，所以 (k+1)-st (6th) 排列{1,2,3} 是 {3,2,1}。
尽管理解它需要一些时间，但它是一种非常高效的算法并且易于编程。反向映射类似。