4

我有一个组合任务，涉及从特定的字符串组合中获取长度小于或等于 6 的每个单词。

在这种情况下，它是 S = { 'a', 'ab', 'ba' }。教授刚开始列出它们，但我认为使用程序会更容易解决。唯一的问题是我无法获得一个可以实际计算所有可能选项的好算法。

如果有人可以提供帮助，我将不胜感激。我通常用 Python 编程，但实际上我只需要算法方面的帮助。

4

4 回答 4

10

假设您确实意味着组合（没有重复，顺序无关紧要）：

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 是相同的（来自不同所谓的“组合”的相同“单词”，我猜-- 使用的术语不完全清楚）。

于 2009-09-22T02:17:59.630 回答
8

您可以迭代生成由一个部分、两个部分、三个部分等组成的所有字符串，直到一个步骤中生成的所有字符串都超过六个字符。进一步的步骤只会生成更长的字符串，因此所有可能的短字符串都已生成。如果您在每个步骤中收集这些短字符串，您最终会得到一组所有可能生成的短字符串。

在 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)
于 2009-09-22T02:34:30.190 回答
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
于 2009-09-22T03:28:38.130 回答
1

递归执行是一种方法：

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)], [] )
于 2009-09-22T03:03:02.610 回答