algorithm - 如何查找范围内重复数字的数字

Question

我正在尝试查找 000000000..999999999 范围内至少有 3 个或更多相似数字组合在一起的所有数字。

以下是通过的整数示例:112333678、111234567、122111876

以下是失败的整数示例:123456789、122334455、123123123

我在 Ruby 中运行了这一行，然后我的 16 GB 内存的 Macbook Pro 内存不足:(000000000..999999999).to_a.select{|e| e.to_s =~/(\d)\1+/>

Answer 1

要计算它们，请取所有 9 位数字，

999999999 + 1

减去没有连续相似数字的9位数字的个数，

- 9^9

并减去一组或多组两个连续相似数字的9位数字的个数，

- (10 - 2*k) choose k * 9^(9 - k) for k=1 to 4

要按字典顺序列出它们，我们可以使用以下方法:

Until done:
  Increment the number until done or the next increment would invalidate it
  If the third digit from the right is less than 9:
    Increment it and set the last two to the same digit
    Increment all three last digits at once until they are 999
  Increment the first digit, l, left of the the third digit 
   from the right that is less than 9
  Set the digits right of l to 0