没有重复数字的给定数以下的数字数量

Question

如何找到一个给定数字之前没有重复数字的数字数量？

例如，小于100的这种数字的数量是90。(11、22、33、44、55、66、77、88、99有重复数字，因此被排除在外)。

同样地，在小于1000的数字中，像101、110、122、202等数字也必须被排除。

- Ankur Ankan

---

你是想计算这些数字还是枚举它们？ - eh9

你能添加一些上下文吗？数字的最大大小是多少？速度要求是什么？为什么不简单地迭代和计数？ - Denys Séguret

数字的最大值为10^18。迭代速度会非常慢。 - Ankur Ankan

最大值仅为10^10，因为所需的值没有超过9876543210。你可以承受得起。 - John Dvorak

好的，没有重复数字的数量是有限的，所以我们可以建立一个查找表，在O(1)时间内得到结果。 :p - kennytm

Answer 1

这里有一个更快的方法。请注意最大数字的位数与解决方案（我将称之为 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

当数字达到十亿时，很可能会出现重复的数字。

- donebizkit

Answer 2

您可以考虑两种情况：

• 长度小于限制的数字
• 与某个数字在某一位上不同的数字

- 位数的数字数量为 9*9*8*... = 9*9!/(9-d)!（第一个数字可能不为零）。小于 - 位数的所有数字的数量是 0 位数数字的数量 + ... + d-1 位数数字的数量。这些总和可以预先计算（甚至硬编码）。

给定 - 个首位数字的 - 位数数字的数量为 (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

- John Dvorak

---

将您的伪代码与我的代码进行比较，我看到很多相似之处。您也将数字在位置len处分为一个头部和一个尾部，其中头部保留，尾部计算较小的数字。但是，您代码中的(d[len]-1)项忽略了头部已经出现过的数字不能再次出现在尾部的事实。与我的代码中的firstHere计算进行比较，以了解差异。 - MvG

@MvG 说得好。(d[len]-1) 这个术语是不正确的。我会更新我的答案。 - John Dvorak

Answer 3

这里有一些代码可以实现这个功能。代码中有注释。基本思路是逐个迭代上一个计数数字的每个数字，对于每个数字位置，您可以计算在该位置之前具有相同数字但当前位置较小的数字的数量。函数相互构建，因此最后的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时，那么除了数字中的零之外，前导零序列也是允许的。这增加了计数，超过了纯排列的计数。

- MvG