Creating an efficent and time-saving algorithm to find difference between greater than and lesser than combination

Question

I want to create a python script, where I have a list of 14 digits and have to find the integer formed by a specific combination of all digits, with the requirement that the number of such combinations that are smaller than this integer exceeds the number of combinations that are greater than the integer by 5617961. This is what i've come up with. It should work but the obvious negative side is it's slow and inefficent. So I need help with coming up with a better algorithm. Also my code:

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

Because it's actually a fun problem, I wrote an algorithm that doesn't rely on building then counting permutations, but rather on mathematically calculating them; the count_permutations_beginning_with function literally does what its name says, and the build_x function recursively builds the rank-th combination.

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'