algorithm - 排列未排序

Question

我知道一种算法(可以在网上找到)对排列进行排序，即给定一个排列，将整数索引返回到按字典顺序排序的排列列表中，但我不知道任何unrank 执行相反操作的算法:给定索引 i，返回该字典顺序中的第 i 个排列。

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

Answer 1

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

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

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

每一半只有一个元素(最后一个字母)。

因此，给定一组三个元素和一个介于 0 和 5 之间的索引(假设 3)，我们可以(提醒一下)除以每个“三分之一”的大小以获得第一个信。现在:

• 集合的大小为 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。重新应用算法，

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

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

1÷1 = 1 雷姆 0

因为我们的集合是 (a,c)，这告诉我们 first 第二个字母是 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;
}