高效查找长整型中的数字序列

Question

有没有办法在不把整数转换成字符串的情况下，找到一个特定的数字序列？也就是说，能不能直接在整数上进行某种模式匹配。我还没有想到具体的方法，但我一直在想应该有数学上的办法可以做到。这并不意味着这样做会更有效率。

（编辑）其实我想要的是那些不包含我想找的数字序列的数字。

这些整数会很大，至少有289位。要找的序列可以是任何东西，比如“123”、“5”（有一个五）、“66666”。

我对一个通用的解决方案感兴趣，但如果你想帮我解决我正在尝试解决的实际问题，可以继续往下看。

更具体地说，我在寻找长度为4的重复数字，比如在1324322223313中找到“2222”。我从整数开始，因为我会逐个增加整数，除非遇到一个有4位重复的整数，那我就会跳到下一个没有重复的整数。我也不想要包含大于4的数字的整数，比如12322135（它有一个5），这些会被排除。

这个问题也可以这样描述：在范围(x,y)内找到所有整数z，使得z[a]不包含任何长度为4的重复数字和大于4的数字。范围(x,y)可能非常大。

（编辑）针对评论，是的，我确实想生成一个列表，我的问题是我不确定如何制作一个满足我所有条件的生成器。也许我应该再考虑一下，我同意这样做会更简单，但这可能类似于生成素数的生成器，目前还没有这样的生成器。

Answer 1

你可以通过这种方式创建一个迭代器，让数字从左到右排列。

>>> import math
>>> number = int(123456789012345678901)
>>> #Get the maximum power of 10 using a logarithm
>>> max_digit = int(math.log10(number))
>>> range_pow = xrange(max_digit, 0, -1)
>>> # pot is an iterator with 1000, 100, 10, 1...
>>> pot = ( 10**x for x in range_pow)
>>> #Get the digits one by one on an iterator
>>> digits = ( (number/x)%10 for x in pot )
>>> l = list(digits)
>>> print l
[1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 0L, 1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 0L]

然后你可以检查这个序列是否存在……我在寻找一种简单的方法通过迭代器来做到这一点，类似于状态机来解析结果，但我不确定有没有现成的方法可以做到，而不需要自己创建一个列表或者自己做一个有限状态机……

你可以尝试这样的方式，但我觉得这样会影响性能（相比于在低级别上直接对迭代器进行有限状态解析），因为你需要先构建一个列表，而不是直接使用迭代器：

>>> print l
[1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 0L, 1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 0L]
>>> find = [1,2,3]
>>> lf = len(find)
>>> for i in xrange(len(l)):
...     if find == l[i:i+lf]:
...          print 'Found!', i
Found! 1
Found! 11

编辑：我想出了一个更迭代的方式来处理这些事情……如果需要，数字参数可以被优化为从一个数字创建一个列表。

import math
from itertools import count

def find_digits_in_number(digits, number):
    #Get the maximum power of 10 using a logarithm
    max_digit = int(math.log10(number))
    range_pow = xrange(max_digit, -1, -1)
    # pot is an iterator with 1000, 100, 10, 1...
    pot = (10 ** x for x in range_pow)
    #Get the digits one by one on an iterator
    dig = ((number / x) % 10 for x in pot)

    #Current will store a moving windows with the 
    #size of the digits length to check if present
    current = []
    for i in digits:
        current.append(next(dig))

    digits = list(digits) 

    founds = []
    #The basic loop is this...
    #for digit, i in zip(dig, count()):
    #    if current == digits:
    #        founds.append(i)
    #    current.pop(0)
    #    current.append(digit)

    #But it can also be optimized like this list comprehension, 
    #while it's much less readable            
    [ (founds.append(i) if current == digits else None,\
      current.pop(0), current.append(digit)) \
      for digit, i in zip(dig, count()) ]

    #Check last posibility, with the last values
    if current == digits:
        founds.append(i + 1)

    return founds


if __name__ == '__main__':
    assert find_digits_in_number((3, 4, 5), 123456789012345678901) == [2, 12]
    assert find_digits_in_number((3, 4), 123456789034) == [2, 10]

Answer 2

一串数字其实很简单。

# given n, a long integer
digits = [] 
while n != 0:
    digits.append( n%10 )
    n //= 10
digits.reverse()

然后你可以在这串数字上进行模式匹配。这样说是不是你想要的呢？

Answer 3

你可以使用这个类来生成数字 :-)

import math

class DecimalIndexing:
    def __init__(self, n):
        self.n = n
    def __len__(self):
        return int(math.floor(math.log10(self.n)+1))
    def __getitem__(self, i):
        if isinstance(i, slice):
            return [self[x] for x in range(i.start, i.stop, i.step or 1)]
        else:
            return (self.n/(10**i))%10
    def __iter__(self):
        for i in xrange(len(self)):
            yield self[i]

你可以这样使用它：

di = DecimalIndexing(31415927)
for i in xrange(len(di)):
    if di[i:i+4] == [9,5,1,4]:
        print "found"

或者这样：

for i in xrange(len(di)):
    if di[i:i+3] == [di[i]]*3:
        print "group of three equal digits at," i

或者这样：

if 5 in di:
    print "has a five"

或者这样：

if any(x > 5 in di):
    print "some digit was greater than five"

等等。

请记住，数字的索引是“反向”的，也就是说是从右到左读取的。