Найдите все способы вставить данный символ в список

Question

У меня есть следующий список ["?","?","?,"?"], и я хочу найти все способы вставить * n раз, а другие индексы будут "-", например, для n = 3 я получу [['*', '*', '*', '-'], ['*', '*', '-', '*'], ['*', '-', '*', '*'], ['-', '*', '*', '*']]

Я надевал это

def backtrack(lst, index_lst, res, number, index=0):
    if index == len(index_lst):
       if lst.count("*") == number:
           lst_copy = lst.copy()
           res.append(lst_copy)
       return
    lst[index] = "*"
    backtrack(lst, index_lst, res, number, index + 1)
    lst[index] = "-"
    backtrack(lst, index_lst, res, number, index + 1)
    lst[index] = "?"


res1 = []
backtrack(["?", "?", "?","?"], [0, 1, 2,3], res1, 3)

И это работает, но с большими списками требуется огромное количество времени. Любые предложения, как я могу сделать его более эффективным?

кстати, индекс list необходим, потому что я хочу предварительно сформировать его в списках, подобных этому ["?","*","?"] или ["?","-","?"], поэтому мне нужно там, где есть ?

И без использования какого-либо модуля

Answer 1

Вы запрашиваете перестановки в списке.

L = ["-","*","*","*"]
print(list(itertools.permutations(L)))