我们如何找到小于给定数字且其中没有重复数字的数字的数量？
例如，小于 100 的此类数字的数量为 90。（11、22、33、44、55、66、77、88、99 具有重复数字，因此被排除在外）。
同样，对于小于 1000 的数字，必须排除 101、110、122、202 等数字。
问问题
6939 次
3 回答
2
Here is a way to make it quicker. Notice that there is a correlation between the number of digits in the max number and the solution (number of numbers which 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're bound to repeat a digit
于 2012-11-06T08:00:39.610 回答
2
你可以考虑两种情况：
- 比限制短的数字
- 与某个数字的限制不同的数字
d-digit 数字的计数是9*9*8*... = 9*9!/(9-d)!（第一个数字可能不为零）。所有短于d0 位数字的计数 + .. - 位数字的计数d-1。这些总和可能是预先计算的（甚至是硬编码的）。
d给出第一个数字的数字的计数f是(10-f)*...*(10-(d-1)) = (10-f)!/(10-d)!。您也可以预先计算阶乘。
伪代码：
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
于 2012-11-06T09:10:26.143 回答
0
这是一些执行此操作的代码。代码中的注释。基本思想是您一次遍历最后计数的数字的数字，并且对于每个数字位置，您可以计算在该位置之前具有相同数字但在该当前位置具有较小数字的数字。这些函数建立在彼此之上，因此最后的cntSmaller函数是您实际调用的函数，也是具有最详细注释的函数。我已经检查了这是否与高达 30000 的所有参数的蛮力实现一致。我已经对替代实现进行了广泛的比较，所以我相当有信心这段代码是正确的。
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
编辑： cntSmaller(9876543211)返回 8877690，这是您可以使用非重复数字形成的最大数字数。这超过 10!=3628800 的事实让我困惑了一段时间，但这是正确的：当您考虑将序列填充到长度 10 时，除了数字中某处的零之外，还允许前导零序列。这增加了纯排列的计数。
于 2012-11-06T11:19:20.600 回答