获取带有重复的单词的所有组合 - python itertools.product 太慢了

Question

我有一个数组值，我需要它来获得所有可能的组合。使用 itertools.product 很容易。

例如。 apple 可以是 elppa、appel、lppae 等

然而，有两个警告。

我需要得到这个单词所有字母重复30次的组合。例如。 aaaaaaaaaaaaaaaaaaaaaaaa苹果 , 苹果aaaaaaaaaaaaaaaaaaaa苹果

显然我们在这里使用的是一个巨大的数据源，所以当我运行测试时，例如重复 6-10 次，速度相当快（即不到一分钟）。当运行通宵测试 30 次方时，表明测试需要几天才能完成。

我玩过 Numpy，Whosebug 上通常建议将其作为 faster/lighter 方法使用。但是我对此感到困惑，因为我发现的所有变体都导致脚本杀死我的机器并使用磁盘 space，与慢速（对于此测试来说太慢）相比，但效率更高 itertools.product。

此外，我不明白如何将所有这些数据提取到一个 numty 数组中，然后计算以下内容，而不会增加系统开销。

最终。

练习的重点是计算 apple 这个词在每行结果中出现的次数。但只有当它连续出现一次时。这算： aaaaaaaaaaaaaaaaaaaaaaaaapple 这不会：appleaaaaaaaaaaaaaaaaaaaaapple

下面的代码对机器没有太大的压力，但是运行太慢了。

谢谢

import itertools
import time
import numpy as np

apple = ['a','p','l','e']
occurences = 0
line = 0
arr_len = len(apple)
length = 30
squared = arr_len**length

start_time = time.time()

for string in itertools.imap(''.join, itertools.product(apple, repeat=length)):
    line += 1
    if (string.count('apple')==1):
        occurences += 1
        if occurences % 100000 == 0:
            print occurences, ("--- %s seconds ---" % (time.time() - start_time)),squared, line

print ('Occurences : ',occurences)
print ('Last line no. ',line)  
print ("--- %s seconds ---" % (time.time() - start_time))

Answer 1

您尝试解决问题的方式本质上是指数级的。您需要使用动态规划。这个问题有一个多项式时间解。如果你的单词中有 n 个字符，你可以使用具有 2n 个状态的马尔可夫链。

import numpy as np

word = 'papal'
length = 10

word_chars = list(set(word))
n = len(word)
m = len(word_chars)
states = [0] * (2*n)
states[0] = 1
jumps = np.zeros((n, m), dtype=np.int)
for i in range(n):
    for j in range(m):
        # We've seen the first i characters of word, and we see character word_chars[j]
        if word[i] == word_chars[j]:
            value = i+1
        else:
            for k in range(i+1):
                if word[k: i] + word_chars[j] == word[:i - k + 1]:
                    value = i - k + 1
                    break
            else:
                value = 0
        jumps[i, j] = value

for i in range(length):
   new_states = [0] * (2*n)
    for j in range(n):
        for jump in jumps[j]:
            new_states[jump] += states[j]
            if n+jump < 2*n:
                new_states[n+jump] += states[n+j]
    states = new_states

print(np.sum(states[n:]))

如果单词是 "papa" 那么 "papapa" 是否匹配？如果不是，你应该删除马尔可夫链中的状态。

Answer 2

稍加思考，我们就可以应用基本概率中的一些计数技术来计算最多包含一个单词出现一次的序列数。不过，动态规划解决方案可能更容易提出，并且对于小序列大小可能运行得更快——下面的解决方案在序列长度上具有线性时间复杂度，但没有针对速度进行优化，我只是 post这里仅供参考：

from scipy.misc import comb

def k(i, t, w):
    """Compute the number of occurrences.

    Arguments
    ---------
    i : int
        The number of products.
    w : int
        Length of the word.
    t : int
        The number of characters in the alphabet.

    """
    # consider all i - w + 1 ways of placing the word into `i` slots,
    # and subtract the number of sequences with multiple occurrences (n_x, n_y)
    r = i - w
    tot = 0
    for x in range(r + 1):
        y = r - x
        n_y = 0 if y < w else (y - w + 1) * t**(y - w)
        n_x = 0 if x < w else (x - w + 1) * t**(x - w)
        s = t**x * n_y + t**y * n_x
        tot += t**r - s

    # for i >= 15 we must compute a correction, because we are "double 
    # counting" some sequences with multiple occurrences. The correction
    # turns out to be an alternating sequence of binomial coefficients
    cor = 0
    for c_k in range(2, i // w):
        c_n = (c_k + 1) + i - w * (c_k + 1)
        cor += (-1)**c_k * int(comb(c_n, c_k)) * n(i - w * c_k)

    return tot + cor

这样

>>> for i in range(31): print(i, k(i, 4, 5))

0 0
1 0
2 0
3 0
4 0
5 1
6 8
7 48
8 256
9 1280
10 6142
11 28648
12 130880
13 588544
14 2613760
15 11491331
16 50102320
17 216924640
18 933629696
19 3997722880
20 17041629180
21 72361164720
22 306190089280
23 1291609627904
24 5433306572800
25 22798585569285
26 95447339991160
27 398767643035280
28 1662849072252416
29 6921972555609600
30 28768047528652794

获取带有重复的单词的所有组合 - python itertools.product 太慢了

Get all combinations of a word with repeat - python itertools.product too slow

python

numpy

itertools