python - 获取字符串的每个组合

Question

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

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

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

Answer 1

假设您的意思是组合(没有重复，顺序无关紧要):

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's被认为是等价的，这种方法可以产生一个字符串> 1次;例如，它产生 ('a', 'ba') 与 ('ab', 'a') 不同，尽管它们的 ''.join 是相同的(我猜来自不同所谓的“组合”的相同“词” -- 使用的术语不完全清楚)。