计算不进行排列的“X”排列

Question

因此，根据 Chat-GPT 4，当您对数字进行任何排列时，可以通过使用因子表示来了解/计算特定的排列结果。唯一的问题是 Chat-GPT 4 的解释不够好，我无法理解。问题是这样的：

号码排列：333366699

我们想要计算“x”（假设第 27 个）排列是什么。

因子表示最终为 937431210，Chat-GPT 4 表示这意味着 369336699 是第 27 个排列！我的问题是如何？如果可能的话，我想编写一些代码，这样我就可以跳过排列过程，只通过知道它们最终的排列来排列数字。

Answer 1

您可以递归地将其视为排列中第一个值的索引，该索引被可以与其余值形成的子排列的数量所抵消。将第一个值在其余值中的偏移量添加到该偏移量（依此类推）以获得给定排列的索引。

从索引到实际排列是以相反的顺序做同样的事情，方法是找出第一个值需要哪个索引基，并与其余值一起递归地获取下一个值。

这适用于不排除输入中重复值产生的重复的排列。我不确定 CHAT-GPT 是否清楚地说明了这一区别是否与您的目标相关。但是，如果是这样，方法将相似，但计算需要略有不同。

请注意，为了保持一致，您的输入应始终进行排序。

from math import factorial
def nthPerm(values,n):
    if len(values) < 2: return values
    subCount = factorial(len(values)-1) # number of permutations for each first value
    index    = n // subCount            # base index of first value 
    rest     = list(values)              
    first    = rest.pop(index)          # extract the 1st value from that index
    return [first] + nthPerm(rest,n-index*subCount) # recurse with the rest

示例：

from itertools import permutations
V= [3,4,5]
for i,p in enumerate(permutations(V)):
    print(i,p)

# 0 (3, 4, 5)
# 1 (3, 5, 4)
# 2 (4, 3, 5)
# 3 (4, 5, 3)
# 4 (5, 3, 4)
# 5 (5, 4, 3)


print(0,":",nthPerm(V,0)) # 0 : [3,4,5]
print(4,":",nthPerm(V,4)) # 4 : [5,3,4]