Найти последовательности цифр в длинных целых числах эффективно

Question

Возможно ли найти определенную последовательность в целое число без преобразования ее в строку? То есть, возможно ли выполнить некоторую форму соответствия шаблонов непосредственно на целых числах. Я не думал об одном, но я продолжаю думать, что должен быть математический способ сделать это. Это не значит, что это более эффективно.

(изменить) Я на самом деле какие числа, которые не содержат последовательности цифр, которые я ищу.

Целые числа будут большими, по меньшей мере, 289 цифр. Поиск по сайту может быть любым: «123», «5» (есть пять), «66666»

Я заинтересован в общем решении, но если вы хотите помочь в решении проблемы с acutal, я пытаюсь чтобы справиться, продолжайте читать.

Подробнее Я ищу повторяющиеся цифры длиной 4, т.е. 1324322223313 «2222». Я смотрю с целыми числами, потому что я буду увеличивать хотя бы целые целые числа, если я не получу целое число с повторением 4 длины, тогда я бы перешел к следующему целому числу без повтора. Также я не знаю, какие целые числа с цифрой больше, чем 4, т.е. 12322135 (она имеет 5).

Проблема может также быть указана как. Найдите все целые числа в z = range (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