14

たとえば、0と1のタプルがあります。

(1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1)

それが判明：

(1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1) == (1, 0, 1, 1) * 3

fifsが0と1の空でないタプルであるような関数が必要なのは、ある正の整数に対してf(s)、が最短のサブタプルrであるということです。s == r * nn

たとえば、

f( (1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1) ) == (1, 0, 1, 1)

fPythonで関数を書くための巧妙な方法は何ですか？

編集：

私が現在使用している素朴な方法

def f(s):
  for i in range(1,len(s)):
    if len(s)%i == 0 and s == s[:i] * (len(s)/i):
      return s[:i]
4

7 に答える 7

5

接尾辞木を使用せず、文字列照合アルゴリズム（KMPなど）を使用するO（n）時間ソリューション（実際には2n + r、nはタプルの長さ、rはサブタプル）があると思います。 -棚）。

次のあまり知られていない定理を使用します。

If x,y are strings over some alphabet,

then xy = yx if and only if x = z^k and y = z^l for some string z and integers k,l.

私は今、私たちの問題の目的のために、これは私たちがする必要があるのは、与えられたタプル/リスト（または文字列）がそれ自体の循環シフトであるかどうかを判断することだけであることを意味すると主張します！

文字列がそれ自体の循環シフトであるかどうかを判断するために、文字列をそれ自体と連結し（実際の連結である必要はなく、仮想の連結で十分です）、部分文字列の一致をチェックします（それ自体と）。

その証拠として、文字列がそれ自体の循環シフトであると仮定します。

与えられた文字列y=uv=vuがあります。uv = vuであるため、上記の定理からu = z^kおよびv=z ^ l、したがってy = z ^ {k+l}である必要があります。他の方向は簡単に証明できます。

これがPythonコードです。この方法はpowercheckと呼ばれます。

def powercheck(lst):
    count = 0
    position = 0
    for pos in KnuthMorrisPratt(double(lst), lst):
        count += 1
        position = pos
        if count == 2:
            break

    return lst[:position]


def double(lst):
    for i in range(1,3):
        for elem in lst:
            yield elem

def main():
    print powercheck([1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1])

if __name__ == "__main__":
    main()

そして、これが私が使用したKMPコードです（David Eppsteinによる）。

# Knuth-Morris-Pratt string matching
# David Eppstein, UC Irvine, 1 Mar 2002

def KnuthMorrisPratt(text, pattern):

    '''Yields all starting positions of copies of the pattern in the text.
Calling conventions are similar to string.find, but its arguments can be
lists or iterators, not just strings, it returns all matches, not just
the first one, and it does not need the whole text in memory at once.
Whenever it yields, it will have read the text exactly up to and including
the match that caused the yield.'''

    # allow indexing into pattern and protect against change during yield
    pattern = list(pattern)

    # build table of shift amounts
    shifts = [1] * (len(pattern) + 1)
    shift = 1
    for pos in range(len(pattern)):
        while shift <= pos and pattern[pos] != pattern[pos-shift]:
            shift += shifts[pos-shift]
        shifts[pos+1] = shift

    # do the actual search
    startPos = 0
    matchLen = 0
    for c in text:
        while matchLen == len(pattern) or \
              matchLen >= 0 and pattern[matchLen] != c:
            startPos += shifts[matchLen]
            matchLen -= shifts[matchLen]
        matchLen += 1
        if matchLen == len(pattern):
            yield startPos

サンプルの場合、この出力

[1,0,1,1]

予想通り。

これをshx2のコード（numpyのコードではない）と比較しました。ランダムな50ビットの文字列を生成し、複製して全長を100万にしました。これが出力でした（10進数はtime.time（）の出力です）

1362988461.75

(50, [1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1])

1362988465.96

50 [1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1]

1362988487.14

上記の方法は約4秒かかりましたが、shx2の方法は約21秒かかりました。

これがタイミングコードです。（shx2のメソッドはpowercheck2と呼ばれていました）。

def rand_bitstring(n):
    rand = random.SystemRandom()
    lst = []
    for j in range(1, n+1):
        r = rand.randint(1,2)
        if r == 2:
            lst.append(0)
        else:
            lst.append(1)

    return lst

def main():
    lst = rand_bitstring(50)*200000
    print time.time()
    print powercheck(lst)
    print time.time()
    powercheck2(lst)
    print time.time()
于 2013-03-11T07:02:06.213 に答える
4

次のソリューションはO（N ^ 2）ですが、イテレーターに基づいているため、データのコピー（またはスライス）を作成しないという利点があります。

入力のサイズによっては、データのコピーを作成しないようにすることで大幅な速度向上を実現できますが、もちろん、複雑度の低いアルゴリズム（O（N *など）ほど巨大な入力に対してはスケーリングしません。 logN））。

[これは私のソリューションの2番目のリビジョンであり、最初のリビジョンを以下に示します。これは理解が簡単で、OPのタプル乗算に沿っており、イテレータのみを使用しています。]

from itertools import izip, chain, tee

def iter_eq(seq1, seq2):
    """ assumes the sequences have the same len """
    return all( v1 == v2 for v1, v2 in izip(seq1, seq2) )

def dup_seq(seq, n):
    """ returns an iterator which is seq chained to itself n times """
    return chain(*tee(seq, n))

def is_reps(arr, slice_size):
    if len(arr) % slice_size != 0:
        return False
    num_slices = len(arr) / slice_size
    return iter_eq(arr, dup_seq(arr[:slice_size], num_slices))

s = (1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1)
for i in range(1,len(s)):
    if is_reps(s, i):
        print i, s[:i]
        break

[私の元の解決策]

from itertools import islice

def is_reps(arr, num_slices):
    if len(arr) % num_slices != 0:
        return False
    slice_size = len(arr) / num_slices
    for i in xrange(slice_size):
        if len(set( islice(arr, i, None, num_slices) )) > 1:
            return False
    return True

s = (1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1)
for i in range(1,len(s)):
    if is_reps(s, i):
        print i, s[:i]
        break

set()次のようなものを使用して、への呼び出しを回避できます。

def is_iter_unique(seq):
    """ a faster version of testing len(set(seq)) <= 1 """
    seen = set()
    for x in seq:
        seen.add(x)
        if len(seen) > 1:
            return False
    return True

そしてこの行を置き換えます：

if len(set( islice(arr, i, None, num_slices) )) > 1:

と：

if not is_iter_unique(islice(arr, i, None, num_slices)):
于 2013-03-11T06:35:51.400 に答える
3

Knootheのソリューションを簡素化します。彼のアルゴリズムは正しいですが、彼の実装は複雑すぎます。この実装もO（n）です。

配列は1と0のみで構成されているため、既存のstr.find実装（Bayer Moore）を使用してKnootheのアイデアを実装します。実行時に驚くほどシンプルで驚くほど高速です。

def f(s):
    s2 = ''.join(map(str, s))
    return s[:(s2+s2).index(s2, 1)]
于 2013-03-11T20:03:22.593 に答える
1

これは、numpyを活用した別のソリューション（以前のイテレーターベースのソリューションと競合する）です。

データの（単一の）コピーを作成しますが、値が0と1であるという事実を利用して、numpyの魔法のおかげで超高速です。

import numpy as np

def is_reps(arr, slice_size):
    if len(arr) % slice_size != 0:
        return False
    arr = arr.reshape((-1, slice_size))
    return (arr.all(axis=0) | (~arr).all(axis=0)).all()

s = (1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1) * 1000
a = np.array(s, dtype=bool)
for i in range(1,len(s)):
    if is_reps(a, i):
        print i, s[:i]
        break
于 2013-03-11T07:25:07.790 に答える
0

問題へのちょうど異なるアプローチ

最初に長さのすべての要素を決定し、次にリストを分割して、すべての部分が同じであるかどうかを確認します

>>> def f(s):
    def factors(n):
        #http://stackoverflow.com/a/6800214/977038
        return set(reduce(list.__add__,
                ([i, n//i] for i in range(2, int(n**0.5) + 1) if n % i == 0)))
    _len = len(s)
    for fact in reversed(list(factors(_len))):
        compare_set = set(izip(*[iter(s)]*fact))
        if len(compare_set) == 1:
            return compare_set


>>> f(t)
set([(1, 0, 1, 1)])
于 2013-03-11T06:20:45.503 に答える
0

入力配列の回転されたバイナリ形式をXORすることにより、劣線形時間でアーカイブできます。

  1. 配列のバイナリ表現を取得し、input_binary
  2. からループしi = 1 to len(input_array)/2、ループごとに、をビット単位でinput_binary右に回転し、として保存してから、とを比較します。irotated_binXORrotated_bininput_binary
  3. 最初iに0を生成するのは、目的のサブストリングであるインデックスです。

完全なコード：

def get_substring(arr):
    binary = ''.join(map(str, arr)) # join the elements to get the binary form

    for i in xrange(1, len(arr) / 2):
        # do a i bit rotation shift, get bit string sub_bin
        rotated_bin = binary[-i:] + binary[:-i]
        if int(rotated_bin) ^ int(binary) == 0:
            return arr[0:i]

    return None


if __name__ == "__main__":
    test = [1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1]
    print get_substring(test) # [1,0,1,1]
于 2013-03-11T07:07:25.717 に答える
0

これはHaskellでのばかげた再帰的な比較です。Knootheの100万本の長い弦（fa）には約1秒かかります。かっこいい問題！もう少し考えてみます。

a = concat $ replicate 20000 
    [1,1,1,0,0,1,0,1,0,0,1,0,0,1,1,1,0,0,
     0,0,0,0,1,1,1,1,0,0,0,1,1,0,1,1,1,1,
     1,1,1,0,0,1,1,1,0,0,0,0,0,1]

f s = 
  f' s [] where
    f' [] result = []
    f' (x:xs) result =
      let y = result ++ [x]   
      in if concat (replicate (div (length s) (length y)) y) == s
            then y
            else f' xs y
于 2013-03-12T01:06:59.027 に答える