创建高效节省时间的算法以查找大于与小于组合的差异

Question

我想写一个Python脚本，里面有一个包含14个数字的列表。我需要找到一个特定组合形成的整数，并且要求比这个整数小的组合数量要比大于这个整数的组合数量多出5617961个。 这是我目前的想法。这个方法应该可以工作，但明显的问题是速度慢且效率低。所以我需要帮助来想出一个更好的算法。

我的代码是：

from itertools import permutations

def generate_combinations(lst, length):
    for combo in permutations(lst, length):
        yield ''.join(map(str, combo))

# List setup
lst = [2, 2, 2, 2, 4, 4, 5, 5, 5, 6, 6, 6, 8, 8]
length = 14
FiveLst = []


for combination in generate_combinations(lst, length):
    arv = [int(x) for x in str(combination)]
    if arv[0] == 5 and arv[1] == 8:
        print(combination)
        FiveLst.append(combination)
for Fiveno in FiveLst:
    difmin = 0
    difplus = 0
    for combination in generate_combinations(lst, length):
        if combination > Fiveno:
            difplus += 1
        else:
            difmin += 1
    difference = difmin-difplus
    if difference == 5617961:
        print(f"Combination found!: {combination}")
        break

print("Process complete!")
exit()

Answer 1

因为这个问题其实挺有趣的，我写了一个算法，它不是通过先生成所有可能的排列再去计数，而是通过数学方法直接计算排列的数量；count_permutations_beginning_with 这个函数的名字就说明了它的功能，而 build_x 函数则是通过递归的方式来构建第 rank 个组合。

from collections import Counter

lst = [2, 2, 2, 2, 4, 4, 5, 5, 5, 6, 6, 6, 8, 8]
expected_diff = 5_617_961

initial_digits = Counter(str(d) for d in sorted(lst))


def fac(n):
    return n * fac(n-1) if n else 1


def count_permutations_beginning_with(n):
    digits = initial_digits.copy()
    digits.subtract(n)
    prod = 1
    for c in digits.values():
        prod *= fac(c)
    return fac(digits.total()) // prod


def build_x(rank, root='', remaining_digits=None):
    if remaining_digits is None:
        remaining_digits = initial_digits.copy()
    print (rank, root, remaining_digits)
    if not remaining_digits.total():
        return root
    for d in remaining_digits:
        if not remaining_digits[d]:
            continue
        if (d_quantity := count_permutations_beginning_with(root + d)) < rank:
            rank -= d_quantity
        else:
            break
    remaining_digits.subtract(d)
    return build_x(rank, root + d, remaining_digits)


x_rank = (count_permutations_beginning_with('') + 1 + expected_diff) // 2

print(build_x(x_rank))
# '58225522644668'