4

我一直在研究一种快速、有效的方法来解决以下问题，但到目前为止，我只能使用一种相当慢的嵌套循环解决方案来解决它。无论如何，这里是描述：

所以我有一个长度为 L 的字符串，可以说'BBBX'。我想找到所有可能的长度为 L 的字符串，从 开始'BBBX'，最多 2 个位置和至少 0 个位置不同。最重要的是，在构建新字符串时，必须从特定字母表中选择新字符。

我猜字母表的大小无关紧要，所以在这种情况下假设字母表是['B', 'G', 'C', 'X'].

因此，一些示例输出将是 、'BGBG'、'BGBC'等'BBGX'。对于这个长度为 4 且最多有 2 个替换字符串的示例，我的算法找到 67 个可能的新字符串。

我一直在尝试用它itertools来解决这个问题，但我很难找到解决方案。我尝试用它itertools.combinations(range(4), 2)来找到所有可能的位置。然后我正在考虑使用product()fromitertools来构建所有可能性，但我不确定是否有办法将它以某种方式连接到combinations().

4

2 回答 2

2

这是我的解决方案。

第一个 for 循环告诉我们将执行多少次替换。（0、1 或 2 - 我们遍历每个）

第二个循环告诉我们将更改哪些字母（通过它们的索引）。

第三个循环遍历这些索引的所有可能的字母更改。有一些逻辑可以确保我们确实更改了字母（将“C”更改为“C”不算数）。

import itertools

def generate_replacements(lo, hi, alphabet, text):
    for count in range(lo, hi + 1):
        for indexes in itertools.combinations(range(len(text)), count):
            for letters in itertools.product(alphabet, repeat=count):
                new_text = list(text)
                actual_count = 0
                for index, letter in zip(indexes, letters):
                    if new_text[index] == letter:
                        continue
                    new_text[index] = letter
                    actual_count += 1
                if actual_count == count:
                    yield ''.join(new_text)

for text in generate_replacements(0, 2, 'BGCX', 'BBBX'):
    print text

这是它的输出：

BBBX GBBX CBBX XBBX BGBX BCBX BXBX BBGX BBCX BBXX BBBB BBBG BBBC GGBX
GCBX GXBX CGBX CCBX CXBX XGBX XCBX XXBX GBGX GBCX GBXX CBGX CBCX CBXX
XBGX XBCX XBXX GBBB GBBG GBBC CBBB CBBG CBBC XBBB XBBG XBBC BGGX BGCX
BGXX BCGX BCCX BCXX BXGX BXCX BXXX BGBB BGBG BGBC BCBB BCBG BCBC BXBB
BXBG BXBC BBGB BBGG BBGC BBCB BBCG BBCC BBXB BBXG BBXC
于 2013-11-12T03:02:13.333 回答
1

没有经过太多测试，但是对于您给出的示例，它确实找到了 67。将指数连接到产品的简单方法是通过zip()：

def sub(s, alphabet, minsubs, maxsubs):
    from itertools import combinations, product
    origs = list(s)
    alphabet = set(alphabet)
    for nsubs in range(minsubs, maxsubs + 1):
        for ix in combinations(range(len(s)), nsubs):
            prods = [alphabet - set(origs[i]) for i in ix]
            s = origs[:]
            for newchars in product(*prods):
                for i, char in zip(ix, newchars):
                    s[i] = char
                yield "".join(s)

count = 0
for s in sub('BBBX', 'BGCX', 0, 2):
    count += 1
    print s
print count

注意：与 FogleBird 的主要区别在于我首先发布了 - LOL ;-) 算法非常相似。Mine 构造输入，product()因此不会尝试用字母替换它自己；FogleBird 允许“身份”替换，但会计算进行了多少有效替换，然后在发生任何身份替换时将结果丢弃。在更长的单词和更多的替换上，这可能会慢得多（可能是循环之间的差异len(alphabet)**nsubs和(len(alphabet)-1)**nsubs时间）。... in product():

于 2013-11-12T02:59:33.420 回答