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

Question

我有一个数组值，我需要它来获取所有可能的组合。使用 itertools.product 可以轻松做到这一点。

例如。苹果可以是 elppa、appel、lppae 等。

但是，有两个警告。

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

显然，我们正在使用一个巨大的数据源，因此当我运行例如 6-10 次重复的测试时，速度相当快(即不到一分钟)。当过夜运行测试的 30 次方时，表明测试需要几天时间才能完成。

我使用过 Numpy，StackOverflow 上通常建议将其作为更快/更轻的使用方法。但我在这方面遇到了困难，因为我发现的所有变体都导致脚本杀死我的机器并使用磁盘空间，与缓慢(对于此测试来说太慢)但更高效的itertools.product。

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

最终。

练习的重点是计算单词 apple 在每行结果中出现的次数。但仅当它连续出现一次时。 这算:aaaaaaaaaaaaaaaaaaaaaaaaaapple 这不会:苹果aaaaaaaaaaaaaaaaaaaa苹果

下面的代码工作时不会对机器造成太大压力，但运行速度太慢。

谢谢

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”是否匹配？如果不是，您应该删除马尔可夫链中的状态。