Python幫助：生成所有可能的字符串給出可選字符

我想在Python中編寫一個函數，給定一個字符串和一個可選字符，從給定字符串生成所有可能的字符串。大圖是使用這個函數來最終幫助將CFG變成喬姆斯基正常形式。Python幫助：生成所有可能的字符串給出可選字符

例如，給定的字符串「ASA」和可選的字符「A」，我希望能夠生成以下的數組：

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

由於這些都是可以由要生成的可能的串省略原始字符串的A中的一個或兩個。

作爲參考，我看了下面的問題：generating all possible strings given a grammar rule，但問題似乎有點不同，因爲語法的規則是在原始字符串中定義的。

這裏是我如何去解決問題的思考：有一個遞歸函數，它需要一個字符串和一個可選字符，循環查找第一個可選字符，然後創建一個新的字符串可選字符省略，將其添加到返回數組中，並使用剛剛生成的字符串和相同的可選字符再次調用自身。

然後，在所有遞歸返回之後，回到原始字符串並省略第二次出現的可選字符，並重復該過程。

這將繼續，直到所有出現的可選字符都被省略。

我想知道是否有更好的方法來做這件事比使用我剛纔描述的邏輯類型。

來源

2015-11-28 CdSdw

但是您是否嘗試過任何操作？ –

您的解決方案非常高效。至於另一個方面，你可能會嘗試圍繞「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)

來源

2015-11-28 11:02:58 Michael

這是基於組合方法，它返回列表中所有可能組合的列表（不考慮順序）。將其中的字符出現索引列表傳遞給它，其餘內容很簡單：

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']

它也包含字符串本身。但這應該是一個很好的起點。

來源

2015-11-28 11:02:27 schwobaseggl

Python幫助：生成所有可能的字符串給出可選字符

回答

相關問題