获取所有字符串组合

Question

我有一个组合数学的作业，要求从一组特定的字符串中找出所有长度小于或等于6的单词。

在这个例子中，字符串集合是 S = { 'a', 'ab', 'ba' }。教授只是开始一个个列出这些单词，但我觉得用程序来解决会更简单。唯一的问题是，我找不到一个好的算法来计算出所有可能的选项。

如果有人能帮忙，我会非常感激。我通常用Python编程，但其实我只需要算法方面的帮助。

Answer 1

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

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行输出。

再补充说明：我之前设定的循环限制不对（所以输出的长度也错了）——感谢指出这一点的评论者。此外，这种方法可能会产生一个字符串出现超过一次的情况，如果不同的元组的''.join结果被认为是相同的；例如，它会把('a', 'ba')和('ab', 'a')当作不同的组合，尽管它们的''.join结果是一样的（同样的“单词”来自不同的所谓“组合”，我想——用词上并不是特别清晰）。

Answer 3

你可以一步一步地生成所有由一个部分、两个部分、三个部分等等组成的字符串，直到某一步生成的所有字符串都超过六个字符。之后的步骤只会生成更长的字符串，所以所有可能的短字符串都已经生成完了。如果你在每一步都收集这些短字符串，最后你就会得到一个包含所有可能生成的短字符串的集合。

在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)