Рекурсивные последовательности Python

Question

как мне распечатать все последовательности длиной n, содержащие буквы из списка (которые могут повторяться)? с использованием рекурсии .например:

seq = ['a', 'b']
n = 2

вывод:

aa,ab,ba,bb

Я искал и мог найти только рекурсивные программы, которые дают все последовательности с без повторений.Более того, я не смог найти какое-либо решение относительно данного списка (большинство из них являются заданными строками)

одна из проблем заключается в том, что я не уверен, как рекурсивно обращаться к функции, пока она содержит длину n,

Answer 1

Вот другой подход, использующий только рекурсию.findSeqRecPerChar находит все возможные комбинации для определенного символа в списке, а findSeqRec находит все возможные комбинации для каждого символа:

seq = ['a', 'b']
n = 2

def findSeqRecPerChar(seq,n,elem,index):
    if index == n:
        return []
    else:
        return [elem+seq[index]] + findSeqRecPerChar(seq,n,elem,index+1)

def findSeqRec(seq,n,index,l):
    if index == n-1:
        return l + []
    else:
        l.extend(findSeqRecPerChar(seq,n,seq[index-1],0))
        return findSeqRec(seq,n,index+1,l)

result = findSeqRec(seq,n,-1,[])

print(result)

Вывод:

['aa', 'ab', 'ba', 'bb']

Answer 2

Я буду использовать itertools

import itertools

seq = ['a', 'b']
n = 2

print([i+j for i,j in itertools.product(seq,repeat=n)])

Это задача для продукта;)

Кстати: если вы не хотите, чтобы модули смотрели на исходный код:

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100     101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Исходный код по адресу: https://docs.python.org/3/library/itertools.html#itertools.product

Изучите и перепроектируйте его в соответствии с вашими потребностями;).Пример, если вы не хотите, чтобы он возвращал кортежи.

Answer 3

Один из способов решить эту проблему - использовать itertools.product

import itertools

seq = ['a', 'b']
n = 2

for a, b in itertools.product(seq,repeat = n): print (f"{a}{b}") #loop through all the products and print them

#result --> 
# aa
# ab
# ba
# bb

Надеюсь, это поможет:)

Answer 4

Вы можете набрать на n, длина подпоследовательности.Если n == 0, то есть только одна подпоследовательность - пустая.В противном случае вы берете все пары элементов вашего списка и подпоследовательности длины n-1 и получаете все подпоследовательности длины n.

def subseqs(lst, n):
    if n <= 0:
        return [[]]
    else:
        return [[x] + xs for x in lst for xs in subseqs(lst, n - 1)]