4

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

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

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

我对一般解决方案感兴趣，但如果您想帮助解决我正在尝试解决的实际问题，请继续阅读。

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

问题也可以表述为。查找 z = range(x,y) 中的所有整数，使得 z[a] 不包含任何长度为 4 的重复数字和大于 4 的数字。 range(x,y) 可能非常大

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

4

5 回答 5

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"

等等

请记住，数字索引是“反转的”，即从右到左读取。

于 2010-01-11T18:39:38.573 回答
1

数字列表非常简单。

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

然后，您可以在此数字列表上进行模式匹配。那是你要找的吗？

于 2010-01-11T16:52:38.633 回答
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]
于 2010-01-11T19:47:19.140 回答
0

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

这也很有用：循环检测

于 2010-01-11T16:02:15.927 回答
0

@Fortran 提供了一个很好的解决方案，它非常通用。

我在 mathoverflow.net 上问了这个问题的修改版本，他们似乎不喜欢这个问题，但我得到了一个很好的答案。它回答了一个稍微不同的问题，但对我的应用程序很有用。

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

(35344442345321456754 / 10**13) % 10**4 == 4444
于 2010-01-12T04:05:54.357 回答