有效查找长整数数字序列

Question

是否可以在整数中找到已定义的序列而不将其转换为字符串？ 也就是说，是否有可能直接在整数上进行某种形式的模式匹配。 我还没有想到一个，但我一直在想，应该有一个这样做的数学方法。这并不是说它更有效率。

（编辑）我其实是什么数字，不包含我正在寻找的数字序列。

整数会很大，至少有289位数字。发现的序列可能是任何东西，“123”，“5”（有一个五），“66666”

我对一般解决方案感兴趣，但如果你想帮助解决acutal问题，以保持阅读。

更具体地说，我正在寻找长度为4的重复数字，即1324322223313“2222”。 我盯着整数，因为我会增加虽然连续的整数，除非我得到一个4长度的整数重复然后我会跳到下一个整数没有重复。另外，我不会用数字大于4的整数，即12322135（它有5）将被排除。

这个问题也可以表述为。 在z =范围（x，y）中查找所有整数，使z [a]不包含任何长度为4的重复数字和大于4的数字。范围（x，y）可能非常大

（编辑）回应评论，是的，我真的想生成一个列表，我的问题是，我不知道我怎么能做一个发电机，满足我所有的条件。也许我应该多想一想，我认为这会更简单，但它可能类似于素数发生器，没有这样的发生器。

Answer 1

你可以使用这个类有你的数字发生器:-)

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" 

等

记住的数字指标是“颠倒”，即由右至左读。

Answer 2

也许你想看看这里：Cyclic Numbers;他们也有一个算法来建立一个循环数。

这可能是太有用：Cycle detection

Answer 3

的数字清单是非常简单的。

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

然后你可以在这个数字列表上做你的模式匹配。那是你在找什么？

Answer 4

你可以用有序的数字的迭代器从左至右这样

>>> import math 
>>> number = int(123456789) 
>>> #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), 123456789) == [2, 12] 
    assert find_digits_in_number((3, 4), 123456789034) == [2, 10] 

Answer 5

@Fortran提供了一个很好的解决方案，它是非常灵活的。

我问了mathoverflow.net上的一个修改版本，他们似乎不喜欢它，但我得到了一个很好的答案。这确实回答了一个与我在此问的问题略有不同的问题，但它对我非常有用。

所以要找到测试，如果数字4444是在35344442345321456754，并假设我知道我在哪里寻找他们，那么这是一个很好的解决方案，一旦你看到它，很明显。

(35344442345321456754/10**13) % 10**4 == 4444