Python帮助：生成所有可能的字符串给出可选字符

问题描述：

我想在Python中编写一个函数，给定一个字符串和一个可选字符，从给定字符串生成所有可能的字符串。大图是使用这个函数来最终帮助将CFG变成乔姆斯基正常形式。Python帮助：生成所有可能的字符串给出可选字符

例如，给定的字符串“ASA”和可选的字符“A”，我希望能够生成以下的数组：

['SA', 'AS', 'S']

由于这些都是可以由要生成的可能的串省略原始字符串的A中的一个或两个。

作为参考，我看了下面的问题：generating all possible strings given a grammar rule，但问题似乎有点不同，因为语法的规则是在原始字符串中定义的。

这里是我如何去解决问题的思考：有一个递归函数，它需要一个字符串和一个可选字符，循环查找第一个可选字符，然后创建一个新的字符串可选字符省略，将其添加到返回数组中，并使用刚刚生成的字符串和相同的可选字符再次调用自身。

然后，在所有递归返回之后，回到原始字符串并省略第二次出现的可选字符，并重复该过程。

这将继续，直到所有出现的可选字符都被省略。

我想知道是否有更好的方法来做这件事比使用我刚才描述的逻辑类型。

但是您是否尝试过任何操作？ –

您的解决方案非常高效。至于另一个方面，你可能会尝试围绕“itertools”模块（组合，排列等）“玩”：首先，找到所有“可选字符”的出现，然后在其索引的所有可能的unqiue组合上创建迭代器。 – soupault

谢谢！我能够创建一个类似于我所描述的功能。一旦一切正常并运行起来，我会确定在稍后看看itertools，看看我是否可以提高效率。感谢提及它！ – CdSdw

答

正如在评论中提到的，它也可以用itertools来完成。这里有一个快速演示：

import itertools 

mystr='ABCDABCDAABCD' 
optional_letter='A' 

indices=[i for i,char in enumerate(list(mystr)) if char==optional_letter] 

def remover(combination,mystr): 

    mylist=list(mystr) 

    for index in combination[::-1]: 
     del mylist[index] 

    return ''.join(mylist) 

all_strings=[remover(combination,mystr) 
      for n in xrange(len(indices)+1) 
      for combination in itertools.combinations(indices,n)] 

for string in all_strings: print string

它首先发现你的性格发生的各项指标，然后从你的字符串中删除这些指数的所有组合。如果在sring中连续有两个可选字母，则会得到可以通过使用删除的副本：

set(all_strings)

答

这是基于组合方法，它返回列表中所有可能组合的列表（不考虑顺序）。将其中的字符出现索引列表传递给它，其余内容很简单：

def indexes(string, char): 
    return [i for i in range(len(string)) if string[i] == char] 

def combinations(chars, max_length=None): 
    if max_length is None: 
     max_length = len(chars) 
    if len(chars) == 0: 
     return [[]] 
    nck = [] 
    for sub_list in combinations(chars[1:], max_length): 
     nck.append(sub_list) 
     if len(sub_list) < max_length: 
      nck.append(chars[:1] + sub_list) 
    return nck 

def substringsOmitting(string, char): 
    subbies = [] 
    for combo in combinations(indexes(string, char)): 
     keepChars = [string[i] for i in range(len(string)) if not i in combo] 
     subbies.append(''.join(keepChars)) 
    return subbies 

if __name__ == '__main__': 
    print(substringsOmitting('ASA', 'A')) 

output: ['ASA', 'SA', 'AS', 'S']

它也包含字符串本身。但这应该是一个很好的起点。

Python帮助：生成所有可能的字符串给出可选字符

相关推荐