Как сохранить рекурсивные результаты при возврате?

Question

В настоящее время я изучаю генерацию перестановок с помощью рекурсии.

Следующий код, который я нашел, прекрасно работает для печати перестановок, но я не могу сохранить значения: все значения в стеке теряются при повышении уровня.

def permute_util(str, count, result, level):

    if level == len(result):
        print(result)
        return

    for i in range(len(str)):
        if count[i] == 0:
            continue;
        result[level] = str[i]
        count[i] -= 1
        permute_util(str, count, result, level + 1)
        count[i] += 1

permute_util(list("ABC"), [2,1,1], [None]*len("AABC"), 0)

---

Результаты:

['A', 'A', 'B', 'C']
['A', 'A', 'C', 'B']
['A', 'B', 'A', 'C']
['A', 'B', 'C', 'A']
['A', 'C', 'A', 'B']
['A', 'C', 'B', 'A']
['B', 'A', 'A', 'C']
['B', 'A', 'C', 'A']
['B', 'C', 'A', 'A']
['C', 'A', 'A', 'B']
['C', 'A', 'B', 'A']
['C', 'B', 'A', 'A']

---

Я попытался добавить результат к глобальному списку в базовом случае, но только последний уровень сохранится, а все остальные предыдущие значения будут перезаписаны, например

 def permute_util(str, count, result, level):
    global glob 
    if level == len(result):
        **glob += [result]**
        return

    for i in range(len(str)):
        if count[i] == 0:
            continue;
        result[level] = str[i]
        count[i] -= 1
        permute_util(str, count, result, level + 1)
        count[i] += 1

permute_util(list("ABC"), [2,1,1], [None]*len("AABC"), 0)

['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']
['C', 'B', 'A', 'A']

Также попробовал это с тем же эффектом:

 def permute_util(str, count, result, level, lists):
    global glob 
    if level == len(result):
        return [result]


    for i in range(len(str)):
        if count[i] == 0:
            continue;
        result[level] = str[i]
        count[i] -= 1
        foo = permute_util(str, count, result, level + 1, lists)
        lists = lists + foo
        count[i] += 1

   lists = []
   permute_util(list("ABC"), [2,1,1], [None]*len("AABC"), 0, lists)

Как лучше всего хранить все «результаты» в базовом случае в списке и возвращать его по завершении?

Answer 1

Python добавляет указатель к списку, а не к фактическому списку. Таким образом, у вас есть много указателей, указывающих на конечное состояние результата и, следовательно, дублирующиеся значения. Попробуйте создавать копию каждый раз, когда вы добавляете, как показано ниже:

final_ans = []
def permute_util(str, count, result, level):

    if level == len(result):
        final_ans.append(result[:])    # if you don't explicitly want list, try final_ans.append(''.join(result))
        return

    for i in range(len(str)):
        if count[i] == 0:
            continue;
        result[level] = str[i]
        count[i] -= 1
        permute_util(str, count, result, level + 1)
        count[i] += 1

permute_util(list("ABC"), [2,1,1], [None]*len("AABC"), 0)
for ans in final_ans:
    print(ans)

Answer 2

По мере продвижения вашей рекурсии вы продолжаете мутировать результат снова и снова.
Вы могли бы сделать что-то вроде этого:

def permute_util(string, count, result, level):

    if level == len(result):
        print(result)
        res.append(tuple(result))   # stores current result as a copy in an immutable tuple
        return

    for i in range(len(string)):
        if count[i] == 0:
            continue;
        result[level] = string[i]
        count[i] -= 1
        permute_util(string, count, result, level + 1)
        count[i] += 1


if __name__ == '__main__':

    res = []

    permute_util(list("ABC"), [2, 1, 1], [None]*len("AABC"), 0)
    print(res)