有效查找長整數數字序列

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