从大量符号中不重复获得第 N 个组合的最快方法

Question

64个符号有64个！排列。如何从其 index/rank 中获取这些排列之一以及如何在 Java 或 Python 或 C# 中以最快的方式获取这些排列之一的 index/rank?
这些排列没有重复，每个排列的长度等于给函数的符号个数。

Answer 1

第N次排列

iea就是你select第一个位置的数字，剩下的是（n-1）个元素的排列，所以select到第一个位置的数字是floor(idx / (n-1)!)。递归地应用它，你就有了你想要的排列。

from functools import lru_cache
@lru_cache
def factorial(n):
    if n <= 1: return 1
    else: return n * factorial(n-1);

def nth_permutation(idx, length, alphabet=None, prefix=()):
    if alphabet is None:
        alphabet = [i for i in range(length)]
    if length == 0:
        return prefix
    else:
        branch_count = factorial(length-1)
        for d in alphabet:
            if d not in prefix:
                if branch_count <= idx:
                    idx -= branch_count;
                else:
                    return nth_permutation(idx, 
                              length-1, alphabet, prefix + (d,))

这将 return 表示所请求排列的元组，如果您愿意，可以传递自定义字母表。

例子

nth_permutation(1, 10)
# (0, 1, 2, 3, 4, 5, 6, 7, 9, 8)
nth_permutation(1000, 10)
# (0, 1, 2, 4, 6, 5, 8, 9, 3, 7)
1000
nth_permutation(3628799, 10)
# (9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
nth_permutation(10**89, 64)
# [[50 27 40 11 60 12 10 49]
# [63 29 41  0  2 48 43 47]
# [57  6 59 56 17 58 52 39]
# [13 51 25 23 45 24 26  7]
# [46 20 36 62 14 55 31  3]
# [ 4  5 53 15  8 28 16 21]
# [32 30 35 18 19 37 61 44]
# [38 42 54  9 33 34  1 22]]

排列指数

给定排列的索引是第一个元素的 index 乘以 (n-1)! 加上其余项排列的等级。

def permutation_index(item, alphabet=None):
    if alphabet is None:
        alphabet = sorted(item)
    n = len(item)
    r = 0
    for i, v in enumerate(item):
        # for every (item[j] > item[i]) we have to increase (n - i)!
        # the factorials are computed recursively
        # grouped in r
        r = sum(1 for u in item[i+1:] 
                if alphabet.index(u) < alphabet.index(v)) + r * (n - i)
    return r;

一致性检查

permutation_index(nth_permutation(1234567890, 16))

从大量符号中不重复获得第 N 个组合的最快方法

Fastest way to get Nth combination without repetition from a larg number of symbols

permutation

第N次排列

排列指数