從python獲得字符串或字符串的所有組合的最佳方法

如何從給定的字符串獲取所有可能的組合組合？一組可以是一個字母或一對（彼此相鄰）。例如，從python獲得字符串或字符串的所有組合的最佳方法

"abc" = 
a, b, c 
ab, c 
a, bc

或

"abcd" = 
a, b, c, d 
ab, c, d 
a, bc, d 
a, b, cd 
ab, cd

針對上述情況，在其本身想產生類似

其中 '1' 表示的， '1 0' 是指其一起。如果兩個'0'不能彼此相鄰，並且'0'不能在第一個項目上。可能可以用遞歸完成，但可能會令人困惑。我不確定它是否真的是解決問題的正確方法。

想知道是否有itertools函數可以使用？如果不是，那麼獲得解決方案的最佳方法是什麼？

來源

2017-03-16 user1179317

@Julien：這是不是所有的組合 - - 單打和雙打。但是，鏈接將有助於獲得解決方案。 – Prune

您是否嘗試過創建一個接受字符串的函數，迭代sting的長度，並返回一個包含每個char和每對的列表？這應該是幾行代碼，您可以將其提供給itertools.combinations。 – SuperTetelman

我認爲你可以使用受限制的分區來做些什麼https://en.m.wikipedia.org/wiki/Partition_(number_theory)#Restricted_partitions –

爲什麼不用這個簡單的遞歸方法？

def sets(s): 
    if len(s) < 2: 
     return [list(s)] 
    return [[s[0]]+x for x in sets(s[1:])] + [[s[:2]]+x for x in sets(s[2:])] 

sets('abcd')

給出：

[['a', 'b', 'c', 'd'], 
['a', 'b', 'cd'], 
['a', 'bc', 'd'], 
['ab', 'c', 'd'], 
['ab', 'cd']]

說明：您的字符串分割爲單峯或對，第一個字母是單獨（第一列表與s[0]）或加上第二個字母（第二列表與s[:2] ），則需要通過對剩餘的字符串進行分區來完成該集合：對於列表中剩餘的每個集合：預先安排第一個元素。

來源

2017-03-16 02:14:53 Julien

這個簡單但很棒的解決方案絕對是我一直在尋找的。小心解釋這是如何工作的？我的意思是我可以閱讀你的代碼，但只是想知道你是如何提出解決方案的。喜歡你的思維邏輯lol – user1179317

看編輯，夠清楚了嗎？ – Julien

我覺得它很清楚。將花更多的時間來學習你的技術。 – user1179317

這是一個更強大的編程問題的可愛改編。你需要一個雙遞歸。在許多這樣的問題中，您想要查找全部分區或字符串的組合;在這種情況下，你只需要前兩個。

關鍵部分是這樣的，對於輸入字符串STR：

result1 = my_func(str[1:]) 
result2 = my_func(str[2:])

對於每一個結果，你需要預先掛起你從正面排除的字母或字母，以每個返回序列。

這與您對遞歸算法的研究相結合，應該讓您朝着解決方案邁進。

來源

2017-03-16 02:07:42 Prune

這是一種避免遞歸的方法。它通過列出對的起始索引來指紋所有可能的分區。如果m是輸入字符串然後ķ雙所有這樣的指紋可以通過

構建的查找所有itertools.combination S的ķ出米長度 - ķ然後
加入1到第二位置，2到第三3到第四等

代碼：

m = 'abcdef' 
fp = [[l+i for i, l in enumerate(c)] for k in range(len(m) // 2 + 1) for c in it.combinations(range(len(m)-k), k)] 
fp 
# [[], [0], [1], [2], [3], [4], [0, 2], [0, 3], [0, 4], [1, 3], [1, 4], [2, 4], [0, 2, 4]] 
[list(m)] + [list(m[:f[0]]) + sum([[m[i:i+2]] + list(m[i+2:j]) for i, j in zip(f,f[1:] + [len(m)])], []) for f in fp[1:]] 
# [['a', 'b', 'c', 'd', 'e', 'f'], ['ab', 'c', 'd', 'e', 'f'], ['a', 'bc', 'd', 'e', 'f'], 
    ['a', 'b', 'cd', 'e', 'f'], ['a', 'b', 'c', 'de', 'f'], ['a', 'b', 'c', 'd', 'ef'], 
    ['ab', 'cd', 'e', 'f'], ['ab', 'c', 'de', 'f'], ['ab', 'c', 'd', 'ef'], ['a', 'bc', 'de', 'f'], 
    ['a', 'bc', 'd', 'ef'], ['a', 'b', 'cd', 'ef'], ['ab', 'cd', 'ef']]

來源

2017-03-16 03:01:29

這是一個使用遞歸生成器的解決方案。

arg到gen是一個字符串列表。它掃描列表尋找相鄰的單字母字符串並將它們連接成對。

def gen(seq, lo=0): 
    yield seq 
    for i in range(lo, len(seq) - 1): 
     u, v = seq[i:i+2] 
     if len(u) == 1 == len(v): 
      yield from gen(seq[:i] + [u + v] + seq[i+2:], i + 1) 

src = 'abcde' 
for s in gen(list(src)): 
    print(s)

輸出

['a', 'b', 'c', 'd', 'e'] 
['ab', 'c', 'd', 'e'] 
['ab', 'cd', 'e'] 
['ab', 'c', 'de'] 
['a', 'bc', 'd', 'e'] 
['a', 'bc', 'de'] 
['a', 'b', 'cd', 'e'] 
['a', 'b', 'c', 'de']

要在Python 2中運行該代碼具有for循環替換yield from語句，如：

for item in gen(seq[:i] + [u + v] + seq[i+2:], i + 1): 
    yield item

來源

2017-03-16 07:57:49

從python獲得字符串或字符串的所有組合的最佳方法

回答

相關問題