python - 如何直接获取序列的第个排列的第个元素(没有任何递归性)？

Question

假设我们有一个字符串“ABCD”，我们想要从该字符串的第 n 次排列中检索第 i 个位置的字母。

在这个例子中，我知道有 Factorial(4) = 24 种排列，并且可以使用 itertools.permutations 轻松检索列表，这将给出:

['ABCD', 'ABDC', 'ACBD', 'ACDB', 'ADBC', 'ADCB', 'BACD', 'BADC', 'BCAD', 'BCDA', 'BDAC', 'BDCA', 'CABD', 'CADB', 'CBAD', 'CBDA', 'CDAB', 'CDBA', 'DABC', 'DACB', 'DBAC', 'DBCA', 'DCAB', 'DCBA']

所以我正在寻找的函数 f 应该返回:

f(0, n) == ['A', 'A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'B', 'B', 'C', 'C', 'C', 'C', 'C', 'C', 'D', 'D', 'D', 'D', 'D', 'D'][n]

f(1, n) == ['B', 'B', 'C', 'C', 'D', 'D', 'A', 'A', 'C', 'C', 'D', 'D', 'A', 'A', 'B', 'B', 'D', 'D', 'A', 'A', 'B', 'B', 'C', 'C'][n]

f(2, n) == ['C', 'D', 'B', 'D', 'B', 'C', 'C', 'D', 'A', 'D', 'A', 'C', 'B', 'D', 'A', 'D', 'A', 'B', 'B', 'C', 'A', 'C', 'A', 'B'][n]

f(3, n) == ['D', 'C', 'D', 'B', 'C', 'B', 'D', 'C', 'D', 'A', 'C', 'A', 'D', 'B', 'D', 'A', 'B', 'A', 'C', 'B', 'C', 'A', 'B', 'A'][n]

对于 i == 0 来说非常容易，我们有 f(0, n) == "ABCD"[n//6] 但当 i 增加时找到模式变得越来越复杂。

我根本不关心排列的顺序，因此也许可以轻松找到 i 的每个值的通用模式...

我计划将其与一组 256 个元素和阶乘 (256) 排列一起使用，因此计算排列不是一个选项。

编辑:我已经有一个用于此目的的函数，但它太慢了，我想知道是否可以使用例如按位运算的简单公式找到一些等效的结果...

Edit-2:这是当前最好的解决方案，感谢 @rici:

f = [factorial(i) for i in range(256)]
    
def _getElt(k, i):
    """
    Returns the <i>th element of the <k>th permutation of 0..255
    """
    table = list(range(256))

    for j in range(255, 254-i, -1):
        r, k = divmod(k, f[j])
        perm[j], perm[r] = perm[r], perm[j] 
    return perm[255 - i]

Edit-3:这是另一种使用多项式近似来重新创建排列的方法，因此问题的不同表述可能是“如何为第 n 个排列重新创建多项式的第 i 个系数？”。

这是 N=4 时的 n、排列、多项式系数(最后是根据多项式系数重建的排列)的列表:

0 [0, 1, 2, 3] [Fraction(0, 1), Fraction(1, 1), Fraction(0, 1), Fraction(0, 1)] [0, 1, 2, 3]

1 [0, 1, 3, 2] [Fraction(0, 1), Fraction(-3, 4), Fraction(5, 2), Fraction(-2, 3)] [0, 1, 3, 2]

2 [0, 2, 1, 3] [Fraction(0, 1), Fraction(11, 2), Fraction(-9, 2), Fraction(1, 1)] [0, 2, 1, 3]

3 [0, 2, 3, 1] [Fraction(0, 1), Fraction(7, 4), Fraction(1, 2), Fraction(-1, 3)] [0, 2, 3, 1]

4 [0, 3, 1, 2] [Fraction(0, 1), Fraction(33, 4), Fraction(-13, 2), Fraction(4, 3)] [0, 3, 1, 2]

5 [0, 3, 2, 1] [Fraction(0, 1), Fraction(19, 3), Fraction(-4, 1), Fraction(2, 3)] [0, 3, 2, 1]

6 [1, 0, 2, 3] [Fraction(1, 1), Fraction(-15, 4), Fraction(7, 2), Fraction(-2, 3)] [1, 0, 2, 3]

7 [1, 0, 3, 2] [Fraction(1, 1), Fraction(-17, 3), Fraction(6, 1), Fraction(-4, 3)] [1, 0, 3, 2]

8 [1, 2, 0, 3] [Fraction(1, 1), Fraction(21, 4), Fraction(-11, 2), Fraction(4, 3)] [1, 2, 0, 3]

9 [1, 2, 3, 0] [Fraction(1, 1), Fraction(-1, 3), Fraction(2, 1), Fraction(-2, 3)] [1, 2, 3, 0]

10 [1, 3, 0, 2] [Fraction(1, 1), Fraction(31, 4), Fraction(-15, 2), Fraction(5, 3)] [1, 3, 0, 2]

11 [1, 3, 2, 0] [Fraction(1, 1), Fraction(17, 4), Fraction(-5, 2), Fraction(1, 3)] [1, 3, 2, 0]

12 [2, 0, 1, 3] [Fraction(2, 1), Fraction(-17, 4), Fraction(5, 2), Fraction(-1, 3)] [2, 0, 1, 3]

13 [2, 0, 3, 1] [Fraction(2, 1), Fraction(-31, 4), Fraction(15, 2), Fraction(-5, 3)] [2, 0, 3, 1]

14 [2, 1, 0, 3] [Fraction(2, 1), Fraction(1, 3), Fraction(-2, 1), Fraction(2, 3)] [2, 1, 0, 3]

15 [2, 1, 3, 0] [Fraction(2, 1), Fraction(-21, 4), Fraction(11, 2), Fraction(-4, 3)] [2, 1, 3, 0]

16 [2, 3, 0, 1] [Fraction(2, 1), Fraction(17, 3), Fraction(-6, 1), Fraction(4, 3)] [2, 3, 0, 1]

17 [2, 3, 1, 0] [Fraction(2, 1), Fraction(15, 4), Fraction(-7, 2), Fraction(2, 3)] [2, 3, 1, 0]

18 [3, 0, 1, 2] [Fraction(3, 1), Fraction(-19, 3), Fraction(4, 1), Fraction(-2, 3)] [3, 0, 1, 2]

19 [3, 0, 2, 1] [Fraction(3, 1), Fraction(-33, 4), Fraction(13, 2), Fraction(-4, 3)] [3, 0, 2, 1]

20 [3, 1, 0, 2] [Fraction(3, 1), Fraction(-7, 4), Fraction(-1, 2), Fraction(1, 3)] [3, 1, 0, 2]

21 [3, 1, 2, 0] [Fraction(3, 1), Fraction(-11, 2), Fraction(9, 2), Fraction(-1, 1)] [3, 1, 2, 0]

22 [3, 2, 0, 1] [Fraction(3, 1), Fraction(3, 4), Fraction(-5, 2), Fraction(2, 3)] [3, 2, 0, 1]

23 [3, 2, 1, 0] [Fraction(3, 1), Fraction(-1, 1), Fraction(0, 1), Fraction(0, 1)] [3, 2, 1, 0]

我们可以清楚地看到存在对称性: coefs[i] = [3 - coefs[23-i][0]] + [-c for c in coefs[23-i][1:]] 所以这是一种探索的方式，但我不知道这是可能的。

Answer 1

您可以通过重复进行欧几里得除法(商和余数，又名 divmod)并跟踪您选择的字母来找到第 n 个排列。然后，您可以从该排列中选择第 i 个字母。

令 S 为初始字符串的副本，L 为该字符串的长度，P 为排列数 ( L!)。 T 将是 S 的第 n 排列，逐步构建。
示例:S = "ABCD"、L = 4 和 P = 24。我们以n = 15 为例。 T 末尾应为 "CBDA"。

设置P = P/L。计算 divmod(n, P)，令 q 为商 (n/P)，r 为余数(n%P)。从 S 中删除第 q 个字母并将其附加到 T 中。设置n = r，递减L，然后重复直到L = 0。
示例:
1) P = 24/4 = 6、q = 15/6 = 2、r = 15%6 = 3、 S = "ABD"、T = "C"、n = r = 3、L = 3。
2) P = 6/3 = 2、q = 3/2 = 1、r = 3%2 = 1、 S = "AD"、T = "CB"、n = r = 1、L = 2。
3) P = 2/2 = 1、q = 1/1 = 1、r = 1%1 = 0、 S = "A"、T = "CBD"、n = r = 0、L = 1。
4) P = 1/1 = 1、q = 0/1 = 0、r = 0%1 = 0、 S =“”、T =“CBDA”、n = r = 0、L = 0。

由于您只想要第 i 个字母，因此只要 T 的长度等于 i+1 就可以停止并取最后一个字母信。

我不会尝试用Python编写这个代码，因为我已经很久没有接触Python了，但是here is a demo in C++ .