排列未排序

Question

我知道一种算法（可以在网上找到）对排列进行排序，即给定一个排列 return 整数索引到字典顺序排序的排列列表中，但我不知道unrank 算法做相反的事情：给定索引 i，return 该字典顺序中的第 i 个排列。

因为我找不到任何东西，有人可以解释一下吗？

Answer 1

假设您要排列字母 (a, b, c)。

有3×2×1=6种排列。其中，第三个以 a 开头，按字典顺序排在另一个以 b 开头的三分之一之前，在最后一个以 c 开头的三分之一之前。

这三分之二的每一个都有两半，一部分从选择第一个字母后剩下的第一个字母开始，另一半从第二个字母开始。

每一半只有一个元素（最后一个字母）。

因此，给定一组三个元素和一个介于 0 和 5 之间的索引（假设 3），我们可以（提醒）除以每个 "third" 的大小以获得第一个字母。现在：

集合的大小为 n=3
有n!=6个排列
有 n=3 组排列，每个排列都以 n 个元素开始
每组大小为n!/n = (n-1)! = 6/3 = 2 个元素

要确定第一个元素的索引，我们除以2余数：

3÷2 = 1 雷姆 1

因为我们的集合是 (a,b,c)，这告诉我们第一个字母是 b。

现在，我们可以从集合中删除字母b，并使用提醒作为新的索引。我们得到集合 (a, c) 和索引 1。Re-applying 算法，

集合的大小为 n=2
有n!=2个排列
有 n=2 组排列，以 n 个元素中的每一个开始
每组大小为n!/n = (n-1)! = 2/2 = 1 个元素

要确定第一个元素的索引，我们除以1余数：

1÷1 = 1 雷姆 0

因为我们的集合是 (a,c)，这告诉我们 ~~第一个~~ 第二个字母是 c.

第三组缩减为单例a也就是我们的第三封信。

索引为 3 的排列是 b,c,a。

让我们检查一下：

0 abc
1 acb
2 bac
3 bca <-- correct!
4 cab 
5 cba

因此，将其放入实际算法中并进行概括：

public string NthPerm(string set, int n)
{
    var res = "";
    while (set.Length > 0)
    {
        var setSize = Math.Factorial(set.Length-1);
        var index = n/setSize;

        res.Concat(set[index]);

        set = index > 0 ? set.Substring(0, index) : "" +
              index < set.Length-1 ? set.Substring(index+1) : "";

        n = n % setSize;
    }
    return res;
}

排列未排序

Permutations unrank

language-agnostic

algorithm

permutation