CODEWITHSUNDEEP
pythonrecursionbacktracking
static_class
static_class

Reputation: 23

How to store recursive results while backtracking?

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?

Upvotes: 2

Views: 886

Answers (2)

Shubham
Shubham

Reputation: 2855

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)

Upvotes: 0

Reblochon Masque
Reblochon Masque

Reputation: 36662

As your recursion progresses, you keep mutating the result over and over again.
you could do something like this:

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)

Upvotes: 1

Related Questions