Создайте все строки заданного набора символов k и lemgth n

Question

Так что я не смог найти точный ответ на следующую проблему в Интернете. Если у меня есть набор символов k, и я хочу сделать все возможные комбинации в строке длиной n, каждый символ должен появляться хотя бы один раз в строке, и я говорю, что 'abc' == 'cba'. Мне нужен код, который доставит мне эти строки. (Так что без дубликатов, таких как 'abc' == 'cba') Я пробовал несколько вложенных циклов и рекурсивных блоков кода, но ни один из них не работал для меня, надеюсь, вы, ребята, можете помочь! (Python мой основной язык делать, если ответ может быть на этом языке, что было бы здорово)

Пример:

In: 
chars = ['a', 'b', 'c'] 
length = 5 
Out: 
'abccc', 'abbcc', 'abbbc', 'aabcc', 'aabbc', 'aaabc' 

Answer 1

itertools вы можете получить большую часть пути туда:

>>> def gen(s, count): 
...  for comb in itertools.combinations_with_replacement(s, count): 
...   if len(set(comb)) == len(s): 
...    yield ''.join(comb) 
...    
>>> [s for s in gen('abc', 5)] 
['aaabc', 'aabbc', 'aabcc', 'abbbc', 'abbcc', 'abccc'] 

Существует неэффективность в создании комбинаций, которые вы отфильтровываете, но если это не критически важный для производительности код, не беспокойтесь об этом преждевременно.

Answer 2

Вы можете просто использовать itertools для этого:

import itertools 

def generate_strings(chars,n): 
    return [''.join(x) for x in itertools.combinations_with_replacement(chars,n) if all(c in x for c in chars)] 

Это происходит потому, что combinations_with_replacement(..) генерирует, как говорит название, кортежи данных элементов, но где каждый элемент может происходить много раз. Итак:

>>> list(itertools.combinations_with_replacement(['a','b'],3)) 
[('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'b', 'b'), ('b', 'b', 'b')] 

Теперь мы проводим дополнительную фильтрацию:

... if all(c in x for c in chars) 

Таким образом, мы проверяем, если все символы присутствуют в строке, что мы будем генерировать.

Теперь мы вызываем ''.join(..), чтобы связать символы в кортежах вместе в строку. Поэтому для нашего примера выше мы создадим ["aab","abb"].

Для вашего данного запроса он генерирует:

>>> generate_strings(['a','b','c'],5) 
['aaabc', 'aabbc', 'aabcc', 'abbbc', 'abbcc', 'abccc'] 

Answer 3

Возьмите без изменений части - здесь «а»

Сформировать все строки с длиной (пк), используя рекурсивный путь или другой подход, здесь «аа», «аб», «ас», «бб», «BC», «куб.см»

Merge неизменной часть с каждой генерируемой строки