Number of numbers less than a given number without duplicate digits

Question

How can we find the number of numbers less than a given number without any duplicate digits?

For example, the number of such numbers less than 100 is 90. (11, 22, 33, 4, 55, 66, 77, 8, 9, 9) repeat the numbers, therefore they are excluded).

Similarly, for less than 1000, numbers such as 101, 110, 122, 202, etc., should be excluded.

Answer 1

Here is a way to do it faster. Please note that there is a correlation between the number of digits in the maximum number and the solution (the number of numbers that I will call NON )

 100 (3 digits) => NON = 10 * 9 1000 (4 digits) => NON = 10 * 9 * 8 10000 (5 digits) => NON = 10 * 9 * 8 * 7 ... 10000000000 (11 digits) => NON = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 

after one billion you must repeat the number

Answer 2

You can consider two cases:

• figures shorter than the limit
• digits that differ from the limit by some value

The number of d digit numbers is 9*9*8*... = 9*9!/(9-d)! (the first digit may not be zero). The count of all numbers shorter than d is the number of 0-digit numbers + .. count d-1 -digit numbers. These amounts can be pre-calculated (or even hard-coded).

The number of d -digits with f with the numbers below is (10-f)*...*(10-(d-1)) = (10-f)!/(10-d)! . You can also pre-copy factorials.

Pseudocode:

 To precompute fac: - fac = int[10]; - fac[0] = 1; - for i in 1..10: - fac[i] = fac[i-1] * i; To precompute count_shorter: - cs = int[10]; - cs[0] = 0; - cs[1] = 1; // if zero is allowed - for i in 1..10: - cs[i+1] = cs[i] + 9 * fac[9] / fac[10-i] - count_shorter = cs; To determine the count of numbers smaller than d: - sl = strlen(d) - if sl > 10 - return count_shorter[11] - else - sum = 0 account for shorter numbers: - sum += count_shorter[sl] account for same-length numbers; len=count of digits shared with the limit: - sum += 9* fac[9] / fac[10-sl]; - for every len in 1..{sl-1}: count the unused digits less than d[len]; credits to @MvG for noting: - first_opts = d[len]-1; - for every i in 0..{len-1}: - if d[i] < d[len] - first_opts -= 1; - sum += first_opts * fac[9-len] / fac[10-sl] - return sum 

Answer 3

Here is the code that does this. Comments in the code. The basic idea is that you iterate over the digits of the last counted number one at a time, and for each digit position you can count the numbers that have the same digits to this position, but a smaller digit in this current position. Functions are built on top of each other, so the cntSmaller function at the very end is the one you actually call, as well as the one that contains the most detailed comments. I checked that this is consistent with brute force implementation for all arguments up to 30,000. I made extensive comparisons with alternative implementations, so I'm sure this code is correct.

 from math import factorial def take(n, r): """Count ways to choose r elements from a set of n without duplicates, taking order into account""" return factorial(n)/factorial(n - r) def forLength(length, numDigits, numFirst): """Count ways to form numbers with length non-repeating digits that take their digits from a set of numDigits possible digits, with numFirst of these as possible choices for the first digit.""" return numFirst * take(numDigits - 1, length - 1) def noRepeated(digits, i): """Given a string of digits, recursively compute the digits for a number which is no larger than the input and has no repeated digits. Recursion starts at i=0.""" if i == len(digits): return True while digits[i] in digits[:i] or not noRepeated(digits, i + 1): digits[i] -= 1 for j in range(i + 1, len(digits)): digits[j] = 9 if digits[i] < 0: digits[i] = 9 return False return True def lastCounted(n): """Compute the digits of the last number that is smaller than n and has no repeated digits.""" digits = [int(i) for i in str(n - 1)] while not noRepeated(digits, 0): digits = [9]*(len(digits) - 1) while digits[0] == 0: digits = digits[1:] assert len(digits) == len(set(digits)) return digits def cntSmaller(n): if n < 2: return 0 digits = lastCounted(n) cnt = 1 # the one from lastCounted is guaranteed to get counted l = len(digits) for i in range(1, l): # count all numbers with less digits # first digit non-zero, rest all other digits cnt += forLength(i, 10, 9) firstDigits = set(range(10)) for i, d in enumerate(digits): # count numbers which are equal to lastCounted up to position # i but have a smaller digit at position i firstHere = firstDigits & set(range(d)) # smaller but not duplicate if i == 0: # this is the first digit firstHere.discard(0) # must not start with a zero cnt += forLength(l - i, 10 - i, len(firstHere)) firstDigits.discard(d) return cnt 

Edit: cntSmaller(9876543211) returns 8877690, which is the maximum number of numbers that you can generate using non-repeating digits. The fact that this is more than 10! = 3628800 confused me a little, but it’s right: if you think that your sequences are filled with a length of 10, then leading zeros are allowed instead of zeros somewhere in the number. This increases the counter above the number of net lookups.