Ottenere ogni combinazione di stringhe

Question

Ho avuto un incarico combinatoria che ha coinvolto ottenere ogni parola con lunghezza inferiore o uguale a 6 da una specifica combinazione di stringhe.

In questo caso, è stato S = { 'a', 'ab', 'ba'}. Il professore appena iniziato elencandoli fuori, ma ho pensato che sarebbe stato più facile risolto con un programma. L'unico problema è che non riesco a ottenere un buon algoritmo che sarebbe in realtà calcolare ogni possibile opzione.

Se qualcuno potrebbe aiutare, lo apprezzerei. Io di solito programma in Python, ma in realtà ho solo bisogno di aiuto con l'algoritmo.

Answer 1

È possibile generare in modo iterativo tutte le stringhe fatti da una parte, due parti, tre parti e così via, fino a quando tutte le stringhe generate in un passo sono più lunghi di sei caratteri. Ulteriori passi genererebbero solo corde ancora più lungo, in modo da tutte le possibili stringhe brevi sono già stati generati. Se si raccolgono queste brevi stringhe in ogni passo si finisce con un insieme di tutti i possibili brevi stringhe generate.

In 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

a patto che le combinazioni medi (ripetizioni, l'ordine non ha importanza):

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

emette tutte le possibilità:

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

Se vuoi dire qualcosa di diverso da "combinazioni", è solo una questione di usare l'iteratore destra o generatore nel for (ad esempio, itertools.permutations, o qualcos'altro del proprio ideazione).

Modifica : se per esempio si intende "ripetizioni e l'ordine sono importanti",

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

vi darà i necessari 85 linee di produzione.

Modifica di nuovo : ho avuto il limite sbagliato loop (e la lunghezza di uscita quindi errato) - tx al commentatore che ha sottolineato che fuori. Inoltre, questo approccio può produrre uno string> 1 volte, se i '' .join di di diverse tuple sono considerate equivalenti; per esempio, produce ( 'a', 'ba') distinto da ( 'ab', 'a') sebbene la loro '' .join è lo stesso (stessa "parola" da diversi cosiddetti "combinazioni", immagino -. la terminologia in uso non essere del tutto chiaro)

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

uscita Stampe:

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

Farlo in modo ricorsivo è un modo:

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)], [] )