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 行の出力が得られます。

もう一度編集してください：ループ制限が間違っていました（したがって、出力長が間違っていました）-それを指摘したコメンターへのtx。また、このアプローチでは、異なるタプルの ''.join が同等と見なされる場合、文字列が > 1 回生成される可能性があります。たとえば、('ab', 'a') とは異なるものとして ('a', 'ba') を生成しますが、それらの ''.join は同じです (異なるいわゆる「組み合わせ」からの同じ「単語」だと思います)。 -- 使用されている用語が完全に明確ではない)。

Answer 2

ステップで生成されるすべての文字列が6文字より長くなるまで、1つの部分、2つの部分、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)

Answer 3

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 4

再帰的に行うことは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)], [] )