CODEWITHSUNDEEP
pythonrecursion
Andreas Thanopoulos
Andreas Thanopoulos

Reputation: 11

I have tried 2 variations of the same code and I can't for the life of me figure out why they give different results while they seem to be equivilent

I was trying to write my own code to print all the permutations of a string(cause I'm a beginner and want to practice and get familiar). But when I convert the string into a list outside the function it doesn't work, while if I convert it inside and convert it back to a string before the recursion, it works...

def permutations(mesg, l, r):
    msg = list(mesg)
    if l == r-1:
        print("".join(msg))
    else:
        for i in range(l, r):
            msg[i], msg[l] = msg[l], msg[i]
            permutations("".join(msg), l+1, r)


message = "ABC"
permutations(message, 0, len(message))

input("press X to exti: ")

and the output is: ABC ACB BAC BCA CAB CBA

def permutations(msg, l, r):
    if l == r-1:
        print("".join(msg))
    else:
        for i in range(l, r):
            msg[i], msg[l] = msg[l], msg[i]
            permutations(msg, l+1, r)


message = "ABC"
permutations(list(message), 0, len(message))
input("press X to exti: ")

and the output is: ABC ACB CAB CBA ABC ACB

the l and i variable progress how they should: # 00,11,12,01,11,12,02,11,12. The first number is l and the other is i. each pair is printed inside the for loop before the recursion.

Upvotes: 1

Views: 52

Answers (1)

ggorlen
ggorlen

Reputation: 57204

The reason for this behavior is that lists are mutable, yet recursion requires a property of self-similarity: the input to a recursive call cannot mess with its parent state or you'll wind up with a different list than the caller originally was working on in its for loop once the child finishes working and control returns to the parent.

The top code breaches this rule: the each trip through the loop swaps elements in the list but nothing is ever restored, so all of the recursive manipulations down through the calls to a leaf node pollute future trips through the parent loop.

list() solves the problem by achieving immutability, but it's not the most performance-conscious approach because you're copying the whole list on every call frame. The other typical approach is usually to "undo" the swap operation after each child call returns:

def permutations(lst, left, right):
    if left == right - 1:
        print("".join(lst))
    else:
        for i in range(left, right):
            lst[i], lst[left] = lst[left], lst[i]
            permutations(lst, left + 1, right)

            # undo the swap to restore the list
            lst[i], lst[left] = lst[left], lst[i]

if __name__ == "__main__":
    permutations(list("abc"), 0, 3)

A few additional suggestions:

  • PEP-8 prohibits using l as a variable name because it's too easy to confuse for a 1 or an i.
  • right is just an alias for len(lst). Just call len instead and simplify your state. Only use right if it's a movable index, like binary search.
  • print("".join(lst)) is better as yield lst[:]. Any permutation function should basically return a generator as itertools.permutations does. Returning a list of lists is also much better than a print side effect that basically makes the function single-purpose and unuseful for anything programmatic that you want to apply more operations to (and you usually do; print is a dead end here).
  • Avoid string joining operations to keep the function generic. Let the caller do that if they want to. There's no reason for an error on [1, 2, 3] as the argument, and the result should still be a list instead of "123", ....
  • left (really i) can be a default argument.

Putting it together:

def permutations(lst, i=0):
    if i == len(lst) - 1:
        yield lst[:]
    else:
        for j in range(i, len(lst)):
            lst[i], lst[j] = lst[j], lst[i]
            yield from permutations(lst, i + 1)
            lst[i], lst[j] = lst[j], lst[i]

if __name__ == "__main__":
    for p in permutations(list("abc")):
        print("".join(p))

(needless to say, never actually use this code, use itertools.permutations -- it's much faster)

Upvotes: 0

Related Questions