Получить количество неповторяющихся чисел в зависимости от системы исчисления.(оптимизация)
Неповторяющееся число, то число где все цифры в числе не повторяются, например 53498
Помогите, пожалуйста, сделать так, чтобы код не вычислял все возможные последовательности, потому что при системе исчисления, например, в 10 тратится очень большое количество памяти и я в, принципе, понимаю, что есть какой то вариант просто прибавлять счетчик не сохраняя данные каждого множества.
Вот пример моего кода:
def non_repeats(radix):
from itertools import permutations
thelist = [x for x in range(radix)]
arr = []
if len(thelist) > 0:
for r in range(0,len(thelist)+1):
arr += list(permutations(thelist, r))
n = len(arr)
for i in range(1, len(arr)-1):
if arr[i][0] == 0:
n -= 1
return n-1
print(non_repeats(6))
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Если я правильно понял:
import math
def count_non_repeats(radix):
cnt = radix
for i in range(2, radix + 1):
cnt += (radix-1)*math.perm(radix-1, i-1)
return cnt
>> 3 11 49 261 1631 11743 95901 876809 8877691
Откуда взялось: на первом месте в k-значном числе может стоять любая из цифр 1..radix-1, а после идёт любое из размещений выборки k-1 цифр из остальных цифр 0..radix-1, не включая уже задействованную цифру, таких размещений A(radix-1, i-1)