Эффективно находить последовательности цифр в длинных целых

Question

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

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

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

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

Более конкретно, я ищу повторяющиеся цифры длины 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

Список цифр довольно прост.

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

Затем вы можете сопоставить шаблон с этим списком цифр. Это то, что вы ищете?

Answer 3

@ Fortran дает отличное решение, оно очень универсально.

Я спрашиваю модифицированную версию на mathoverflow.net, Кажется, им это не понравилось, но я получил отличный ответ. Это действительно отвечает на вопрос, немного отличающийся от того, что я задаю здесь, но это очень полезно для меня.

чтобы найти тест, если цифры 4444 находятся в 35344442345321456754, и, если я знаю, где мне их искать, то это хорошее решение, и оно становится очевидным, когда вы его видите.

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

Answer 4

Вы можете создать итератор с цифрами, упорядоченными слева направо, таким образом

>>> 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 5

Может быть, вы хотите посмотреть здесь: Циклические числа ; у них также есть алгоритм для построения циклического числа.

Это также может быть полезно: Обнаружение цикла