Как ускорить выполнение кода?

Question

Пишу программу, которая решает следующую задачу:

Сколько существует 11-значных чисел, в записи которых встречаются все цифры?

Вот что у меня получилось:

count=0
for i in range(10**10, 10**11):
    cnt=0
    for j in range(0, 10):
        k=i
        while k>0:
            if k%10!=j:
                k=k//10
            else:
                cnt+=1
                break
    if cnt==10:
        count+=1
print(count)

Однако такой код будет выполняться слишком долго. Как можно решить эту проблему?

Answer 1

Подход должен быть немного другим.

в 11 значном числе, в котором должны встречаться все 10 цифр, две цифры должны повторяться.

Тогда задача сводится к тому, сколько есть 11 значных чисел, в записи которых есть две одинаковые цифры.

Такое число характеризуется тремя независимыми параметрами:

какая цифра повторяется (10 вариантов)
где она встречается в числе первый раз (11 вариантов)
где она встречается второй раз (10 вариантов)

Таким образом, это 10 * 11 * 10.

Это кол-во надо разделить на два (это понятно?) и выкинуть те варианты, когда впереди один или два ведущих нуля.

Как то так :-)

Answer 2

Перебор такого количества чисел за разумное время на сделать, так что эту проблему не решить. Чуток ускорить можно, например, так

for i in range(10**10, 10**11):
    cnt=0
    print(i)
    s = set(str(i))
    if len(s)==10:
        count+=1

Ну и начинать надо не с 10¹⁰, а с минимального 11-значного числа, в котором есть все 10 цифр. Заканчивать, соответственно, максимальным.

Но это все как экономия на трамвайном билете, когда направляешься в автосалон пешком, чтобы купить автомобиль.

Answer 3

Надеюсь, я правильно всё сообразил. За минуту примерно посчиталось:

from tqdm.auto import tqdm
from itertools import permutations

n = 11
count=0
items = list(range(10))
for i in tqdm(range(10)):
    for x in permutations(items + [i], n):
        if x[0] == 0:
            continue
        count += 1
print(count//2)

Вывод:

179625600

берём список из 10 разных цифр
добавляем к нему по очереди разные цифры
считаем все возможные комбинации из этих 11 цифр
но отбрасываем из них те, которые начинаются на 0 (это не будут числа с длиной 11)
делим результат на 2 (потому что две перебираемые цифры в каждом из чисел взаимозаменяемы и эти числа не отличимы друг от друга)

Ну и "однострочник" (если не считать строку с подключением библиотеки):

from itertools import permutations

print(sum(x[0] != 0 for i in range(10) for x in permutations(list(range(10)) + [i], 11)) // 2)

Answer 4

В развитие логического подхода S.H.:

Удвоенная цифра может стоять на первом месте, 9 вариантов, тогда остаётся десять мест для десяти цифр, и подобных комбинаций 9*10!

Пусть теперь на первом месте стоит одиночная цифра a, 9 вариантов. Применим хитрость - расставим 10 разных цифр на оставшиеся 10 мест - это 10! перестановок, потом заменим внутри этих перестановок уже имеющуюся первую цифру a на 9 возможных замен, получается 9*10!*9, и разделим пополам, потому что не можем различить две одинаковые цифры 9*10!*9/2

Вместе получается

9*10! + 9*10!*9/2 = 10! * (18 + 81)/2 = 10!*99/2 = 179 625 600

Для случаев, когда система основания N не равна 10, общая формула

n! * (n-1)*(n+1) / 2 =  (n+1)!*(n-1)/2

например, для n=2 легко проверить результат 3 (0b100,0b101,0b110), для n=3 результат 24 и т.д.

БЛОГ НА HUSL

Как ускорить выполнение кода?

Ответы (4 шт):