How to store recursive results while backtracking?

Question

I'm currently learning about permutation generation via recursion.

The following code I found works great for printing the permutations, but I can't seem to store the values: all values in the stack are lost upon going a level up.

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)

---

Results:

['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']

---

I've tried adding result to a global list in the base case, but only the latest level will get store while all other previous values will get overwritten, like so

 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']

Also tried this to the same effect:

 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)

What would be the best approach to store all "result" in the base case in a list and return it on completion?

Answer 1

Python appends the pointer to the list rather than the actual list. Thus, what you have is a lot of pointers pointing to the final state of result hence the duplicate values. Try creating the copy every time you are appending, like the following:

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)