排列不规则 [英] Permutations unrank

问题描述

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

I know of an algorithm (it can be found online) to rank a permutation, i.e. given a permutation return the integer index into the list of lexicographically-sorted permutations, but I don't know any unrank algorithm that does the opposite: given an index i, return the i-th permutation in that lexicographic order.

由于我找不到任何东西，有人可以请问一下吗?

Since I couldn't find any, can somebody please shed some light?

推荐答案

假设您要对字母(a，b，c)进行排列.

Let's say you are permutating the letters (a, b, c).

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

There are 3×2×1=6 permutations. Out of these, a third starts with a and lexicographically precedes another third starting with b, preceding the last third starting with c.

对于这三分之二的每一部分，都有两半，一个以选择第一个字母后剩下的第一个字母开头，另一个是第二个字母.

For each of these thirds there are two halves, one starting with the first letter left after choosing the first, and the other with the second.

这些半部中的每半部都只有一个元素(最后一个字母).

Each of these halves has only one element (the last letter).

因此，给定一组三个元素，并且索引在零到五个之间(假设 3 )，我们可以除以(提醒一下)每个第三"的大小，以获得第一个信件.现在:

So, given a set of three elements and an index between zero and five (let's say 3), we can divide (with reminder) by the size of each "third" to get the first letter. Now:

• 集合的大小为n = 3
• 有n！= 6个排列
• 从n个元素中的每一个开始有n = 3个置换组
• 每个组的大小为n！/n =(n-1)！= 6/3 = 2个元素

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

To determine the index of the first element, we divide by 2 with remainder:

3÷ 2 = 1雷姆1

3÷2 = 1 rem 1

由于我们的集合是(a，b，c)，所以这告诉我们第一个字母是 b .

Since our set is (a,b,c), this tells us that the first letter is b.

现在，我们可以从集合中删除字母b，并将提醒用作新索引.我们得到集合(a，c)和索引1.重新应用算法，

Now, we can remove the letter b from the set, and use the reminder as the new index. We get the set (a, c) and index 1. Re-applying the algorithm,

• 集合的大小为n = 2
• 有n！= 2个排列
• 从n个元素中的每一个开始有n = 2个置换组
• 每个组的大小为n！/n =(n-1)！= 2/2 = 1个元素

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

To determine the index of the first element, we divide by 1 with remainder:

1÷ 1 = 1雷姆0

1÷1 = 1 rem 0

由于我们的集合是(a，c)，所以这告诉我们第一个第二个字母是 c .

Since our set is (a,c), this tells us that the first second letter is c.

第三组简化为单例 a ，这是我们的第三个字母.

The third set is reduced to the singleton a and that's our third letter.

索引为3的排列是b，c，a.

The permutation with index 3 is b,c,a.

让我们检查一下:

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

因此，将其放入真实算法并进行概括:

So, putting this in a real algorithm and generalizing:

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;
}

这篇关于排列不规则的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！