4

文字列に変換せずに整数で定義されたシーケンスを見つけることは可能ですか? つまり、何らかの形式のパターン マッチングを整数に対して直接実行することは可能ですか。私は考えたことはありませんが、これを行う数学的な方法があるべきだと考え続けています。より効率的であると言っているわけではありません。

（編集）私が実際に探している数字のシーケンスを含まない数字は何ですか。

整数は大きく、少なくとも 289 桁になります。検索するシーケンスは、「123」、「5」(5 つある)、「66666」のいずれかです。

私は一般的な解決策に興味がありますが、実際の問題を解決したい場合は、読み続けて解決しようとしています.

より具体的には、長さ 4 の繰り返し数字、つまり 1324322223313 "2222" を探しています。4 つの長さの繰り返しで整数に到達しない限り、連続した整数をインクリメントするため、整数を見つめています。繰り返しなしで次の整数にスキップします。また、4より大きい数字の整数、つまり12322135（5がある）が除外されることもありません。

問題は次のように述べることもできます。z[a] に長さ 4 の数字と 4 より大きい数字の繰り返しが含まれないように、z = range(x,y) 内のすべての整数を検索します。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

多分あなたはここを見たいと思うでしょう: Cyclic Numbers ; また、巡回数を構築するアルゴリズムもあります。

これも役に立ちます:サイクル検出

于 2010-01-11T16:02:15.927 に答える
0

@Fortran は優れたソリューションを提供します。非常に用途が広いです。

この質問の修正版を mathoverflow.net で尋ねたところ、彼らはその質問を気に入らなかったようですが、すばらしい回答が得られました。少し異なる質問に答えますが、私のアプリケーションには役立ちます。

数字 4444 が 35344442345321456754 にあるかどうかをテストし、どこで何を探すべきかを知っていると仮定すると、これは良い解決策であり、一度見れば明らかです。

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