创建高效且省时的算法来查找大于和小于组合之间的差异

Question

我想创建一个python脚本，其中我有一个len 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 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'