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

我想要一个函数f，使得 ifs是一个由零和一组成的非空元组，f(s)是最短的子元组r，使得s == r * n对于某个正整数n。

例如，

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

f用 Python编写函数的巧妙方法是什么？

编辑：

我目前使用的幼稚方法

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

我相信我有一个 O(n) 时间解决方案（实际上是 2n+r，n 是元组的长度，r 是子元组），它不使用后缀树，而是使用字符串匹配算法（如 KMP，你应该找到它-架子）。

我们使用以下鲜为人知的定理：

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 万。这是输出（十进制数是 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*日志N))。

[这是我的解决方案的第二次修订，第一个在下面给出。这个更容易理解，并且更符合 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

这只是 Haskell 中的一个愚蠢的递归比较。Knoothe 的百万长弦 (fa) 大约需要一秒钟。很酷的问题！我会再考虑一下。

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 回答
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

您可以通过对输入数组的旋转二进制形式进行异或运算，在亚线性时间内将其存档：

  1. 得到数组的二进制表示，input_binary
  2. 从 循环i = 1 to len(input_array)/2，对于每个循环，将input_binary向右旋转i一位，将其保存为，rotated_bin然后比较XOR和。rotated_bininput_binary
  3. 产生 0的第一个i是所需子字符串的索引。

完整代码：

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 回答