All geek questions in one place

Get each row combination

I had a combinatorial task, which included getting each word less than or equal to 6 in length from a specific combination of lines.

In this case, it was S = {'a', 'ab', 'ba'}. The professor was just starting to list them, but I thought it would be easier to solve using the program. The only problem is that I cannot get a good algorithm that would actually calculate all the possible options.

If anyone could help, I would appreciate it. I usually program in Python, but actually I need help with the algorithm.

+3
source share
4 answers

, , .., , , . , . , .

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)
+8

, DO ( , ):

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

: , , " ARE important",

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 , . , > 1 , ".join ; , ('a', 'ba') (ab, a), ".join ( "" "", - ).

+8
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
+3

- :

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

Source: https://habr.com/ru/post/1718246/

More articles:


All Articles