logo标签列表

排列重复元素的排名和反排列

c++algorithmpermutation
4
我正在阅读关于排列的内容，对排名/取消排名方法感兴趣。
从一篇论文的摘要中得知：
排列函数为n个符号上的排列分配一个唯一的整数，该整数在[0，n！- 1]范围内。相应的取消排名函数是其反函数：给定0到n！- 1之间的整数，函数的值是具有此排名的排列。
我使用next_permutation在C ++中制作了排名和取消排名函数。但是对于n> 8来说，这并不实用。我正在寻找一种更快的方法， factoradics似乎非常受欢迎。但是我不确定它是否也适用于重复项。那么，用重复项进行排名/取消排名的好方法是什么？
取决于你使用的排列方式是什么？我的意思是，原始集合和排名函数是什么？ - Yochai Timmer
它按字典顺序排列。因此，如果一个排列的等级为r，则下一个排列的等级为r+1。相同的排列应具有相同的等级（在重复的情况下）。 - Jasper
4个回答
3

我将在这个答案中回答你问题的一半——“unranking”。目标是高效地找到一个有序字符串 [abcd…] 的字典序第 'K' 个排列。

为此，我们需要了解阶乘数系统（factoradics）。阶乘数系统使用阶乘值而不是数字的幂（二进制系统使用2的幂，十进制系统使用10的幂）来表示位值（或基数）。

位值（基数）如下：

5!= 120    4!= 24    3!=6    2!= 2    1!=1    0!=1 etc..

第0位数字始终为0。第1位数字（基数=1时！）可以是0或1。第2位数字（基数=2时！）可以是0、1或2，以此类推。一般来说，第n位数字可以取0-n之间的任何值。

表示为阶乘进制的前几个数字-

0 -> 0 = 0*0!
1 -> 10 = 1*1! + 0*0!
2 -> 100 = 1*2! + 0*1! + 0*0!
3 -> 110 = 1*2! + 1*1! + 0*0!
4 -> 200 = 2*2! + 0*1! + 0*0!
5 -> 210 = 2*2! + 1*1! + 0*0!
6 -> 1000 = 1*3! + 0*2! + 0*1! + 0*0!
7 -> 1010 = 1*3! + 0*2! + 1*1! + 0*0!
8 -> 1100 = 1*3! + 1*2! + 0*1! + 0*0!
9 -> 1110
10-> 1200

字符串的第n个字典序排列与其底数分解表示之间存在直接关系。

例如，以下是字符串“abcd”的排列。

0  abcd       6  bacd        12  cabd       18  dabc
1  abdc       7  badc        13  cadb       19  dacb
2  acbd       8  bcad        14  cbad       20  dbac
3  acdb       9  bcda        15  cbda       21  dbca
4  adbc       10  bdac       16  cdab       22  dcab
5  adcb       11  bdca       17  cdba       23  dcba

我们可以仔细观察这个模式。第一个字母在每6个排列（3！）后发生改变。第二个字母在2个排列（2！）后发生改变。第三个字母在每个排列（1！）后发生改变，第四个字母在每个排列（0！）后发生改变。我们可以使用这个关系直接找到第n个排列。
一旦用factoradic表示法表示了n，我们考虑其中的每个数字，并从给定的字符串中加入一个字符到输出中。如果我们需要找到‘abcd’的第14个排列。14用factoradic表示 -> 2100。
从第一个数字开始 -> 2，字符串是‘abcd’。假设索引从0开始，在字符串中取位置为2的元素，并将其添加到输出中。
Output                    String
  c                         abd
  2                         012

下一个数字 -> 1。字符串现在是'abd'。再次取出位置为1的字符并将其添加到输出中。
Output                    String
 cb                         ad
 21                         01

下一个数字是0。字符串为'ad'。将位置1处的字符添加到输出中。
Output                   String
 cba                        d
 210                        0

下一个数字->0。字符串为‘d’。将位置0处的字符添加到输出中。
输出 字符串 cbad ''
2100
要将给定的数字转换为阶乘数系统，依次将该数字除以1、2、3、4、5等，直到商为零。每一步的余数形成了因子表示法。
例如，将349转换为因子表示法：
              Quotient        Reminder       Factorial Representation
349/1            349               0                             0
349/2            174               1                            10
174/3            58                0                           010
58/4             14                2                          2010
14/5             2                 4                         42010
2/6              0                 2                        242010

349的阶乘表示是242010。

2
2
链接的代码对于没有重复的排列是可以的（一旦修复了传递的li参数被改变的问题），但是当基本序列包含重复项时，它不会产生正确的排列。所以，我自己写了一个。;) - PM 2Ring
2

一种方法是通过对一组相等的数字进行排序和反排序来选择指数的顺序，例如：

def choose(n, k):
    c = 1
    for f in xrange(1, k + 1):
        c = (c * (n - f + 1)) // f
    return c

def rank_choice(S):
    k = len(S)
    r = 0
    j = k - 1
    for n in S:
        for i in xrange(j, n):
            r += choose(i, j)
        j -= 1
    return r

def unrank_choice(k, r):
    S = []
    for j in xrange(k - 1, -1, -1):
        n = j
        while r >= choose(n, j):
            r -= choose(n, j)
            n += 1
        S.append(n)
    return S

def rank_perm(P):
    P = list(P)
    r = 0
    for n in xrange(max(P), -1, -1):
        S = []
        for i, p in enumerate(P):
            if p == n:
                S.append(i)
        S.reverse()
        for i in S:
            del P[i]
        r *= choose(len(P) + len(S), len(S))
        r += rank_choice(S)
    return r

def unrank_perm(M, r):
    P = []
    for n, m in enumerate(M):
        S = unrank_choice(m, r % choose(len(P) + m, m))
        r //= choose(len(P) + m, m)
        S.reverse()
        for i in S:
            P.insert(i, n)
    return tuple(P)

if __name__ == '__main__':
    for i in xrange(60):
        print rank_perm(unrank_perm([2, 3, 1], i))
0

Java，来自https://github.com/timtiemens/permute/blob/master/src/main/java/permute/PermuteUtil.java（我的公共领域代码，减去错误检查）：

public class PermuteUtil {
 public <T> List<T> nthPermutation(List<T> original, final BigInteger permutationNumber)  {
        final int size = original.size();

        // the return list:
        List<T> ret = new ArrayList<>();
        // local mutable copy of the original list:
        List<T> numbers = new ArrayList<>(original);

        // Our input permutationNumber is [1,N!], but array indexes are [0,N!-1], so subtract one:
        BigInteger permNum = permutationNumber.subtract(BigInteger.ONE);

        for (int i = 1; i <= size; i++) {
            BigInteger factorialNminusI = factorial(size - i);

            // casting to integer is ok here, because even though permNum _could_ be big,
            //   the factorialNminusI is _always_ big
            int j = permNum.divide(factorialNminusI).intValue();

            permNum = permNum.mod(factorialNminusI);

            // remove item at index j, and put it in the return list at the end
            T item = numbers.remove(j);
            ret.add(item);
        }

        return ret;
  }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接