獲取字符串的每個組合

Question

我有一個組合指派，它涉及從特定的字符串組合中獲取長度小於或等於6的每個單詞。

在這種情況下，它是S = {'a'，'ab'，'ba'}。教授剛開始列出他們，但我認爲用程序可以更容易地解決這個問題。唯一的問題是我無法得到一個能夠真正計算每個可能選項的好算法。

如果有人可以幫忙，我會很感激。我通常使用Python進行編程，但實際上我只需要使用該算法的幫助。

Answer 1

您可以反覆生成由一個部分，兩個部分，三個部分等組成的所有字符串，直到在一個步驟中生成的所有字符串都超過六個字符。進一步的步驟只會生成更長的字符串，因此所有可能的短字符串都已經生成。如果在每一步中收集這些短字符串，則最終會生成一組所有可能生成的短字符串。

在Python：

S = set(['a', 'ab', 'ba']) 

collect = set() 
step = set(['']) 
while step: 
    step = set(a+b for a in step for b in S if len(a+b) <= 6) 
    collect |= step 

print sorted(collect) 

Answer 2

假設你的意思是組合（不重複，順序並不重要）：

import itertools 

S = [ 'a', 'ab', 'ba' ] 

for i in range(len(S)+1): 
    for c in itertools.combinations(S, i): 
    cc = ''.join(c) 
    if len(cc) <= 6: 
     print c 

發射一切準備：

() 
('a',) 
('ab',) 
('ba',) 
('a', 'ab') 
('a', 'ba') 
('ab', 'ba') 
('a', 'ab', 'ba') 

如果你的意思是不是「組合」不同，它只是在for（例如，itertools.permutations或您自己設計的其他東西）中使用正確的迭代器或生成器的問題。

編輯：例如，如果你的意思是「重複和順序是很重要的」，

def reps(seq, n): 
    return itertools.product(*[seq]*n) 

for i in range(7): 
    for c in reps(S, i): 
    cc = ''.join(c) 
    if len(cc) <= 6: 
     print c 

會給你所需的85行輸出。

再次編輯：我有錯誤的循環限制（因此錯誤的輸出長度） - tx給指出的評論者。此外，如果不同元組的''.join被認爲是等價的，那麼這種方法可以產生大於1次的字符串;例如，它產生（'a'，'ba'）與（'ab'，'a'）不同，雖然它們的'.join是來自不同的所謂「組合」的相同（相同的「單詞」 - 使用中的術語不完全清楚）。

Answer 3

做這遞歸是一種方法：

cache = {} 
def words_of_length(s, n=6): 
    # memoise results 
    if n in cache: return cache[n] 

    # base cases 
    if n < 0: return [] 
    if n == 0: return [""] 

    # inductive case 
    res = set() 
    for x in s: 
     res |= set((x+y for y in words_of_length(s, n-len(x)))) 

    # sort and memoise result 
    cache[n] = sorted(res) 

    # sort results 
    return cache[n] 

def words_no_longer_than(s, n=6): 
    return sum([words_of_length(s, i) for i in range(n+1)], []) 

Answer 4

def combos(S,n): 
    if (n <= 0): return 
    for s in S: 
     if len(s) <= n: yield s 
     for t in combos(S,n-len(s)): yield s+t 

for x in combos(["a","ab","ba"],6): print x 

打印輸出：

a 
aa 
aaa 
aaaa 
aaaaa 
aaaaaa 
aaaaab 
aaaaba 
aaaab 
aaaaba 
aaaba 
aaabaa 
aaab 
aaaba 
aaabaa 
aaabab 
aaabba 
aaba 
aabaa 
aabaaa 
aabaab 
aababa 
aab 
aaba 
aabaa 
aabaaa 
aabaab 
aababa 
aabab 
aababa 
aabba 
aabbaa 
aba 
abaa 
abaaa 
abaaaa 
abaaab 
abaaba 
abaab 
abaaba 
ababa 
ababaa 
ab 
aba 
abaa 
abaaa 
abaaaa 
abaaab 
abaaba 
abaab 
abaaba 
ababa 
ababaa 
abab 
ababa 
ababaa 
ababab 
ababba 
abba 
abbaa 
abbaaa 
abbaab 
abbaba 
ba 
baa 
baaa 
baaaa 
baaaaa 
baaaab 
baaaba 
baaab 
baaaba 
baaba 
baabaa 
baab 
baaba 
baabaa 
baabab 
baabba 
baba 
babaa 
babaaa 
babaab 
bababa