I am writing a function that, given an array, returns a list of possible permutations. I came up with the following and it works great:
def _permutate(elems):
if len(elems) <= 1:
yield elems
else:
for i in range(len(elems)):
for perm in _permutate(elems[:i] elems[i 1:]):
yield [elems[i]] perm
So running print(list(_permutate([2, 1, 3])))
gives me: [[2, 1, 3], [2, 3, 1], [1, 2, 3], [1, 3, 2], [3, 2, 1], [3, 1, 2]]
But I want to know what's actually happening in the background... I know a recursive function adds to a stack until it reaches it's base case and then works backwards down the stack to give you a result, and then a generator function pauses computation at it's first yield and returns a generator that you have to loop through to get the results of each yield, but I'm really confused as to what happens when you put the two together.
Rewriting the function with debug statements
def _permutate(elems):
if len(elems) <= 1:
print(elems) # NEW
yield elems
else:
for i in range(len(elems)):
for perm in _permutate(elems[:i] elems[i 1:]):
print("NEW", [elems[i]], perm) # NEW
yield [elems[i]] perm
And then running
gen = _permutate([1,2,3,4,5])
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
Shows a bit clearer what's going on:
[5]
NEW [4] [5]
NEW [3] [4, 5]
NEW [2] [3, 4, 5]
NEW [1] [2, 3, 4, 5]
NEXT [1, 2, 3, 4, 5]
[4]
NEW [5] [4]
NEW [3] [5, 4]
NEW [2] [3, 5, 4]
NEW [1] [2, 3, 5, 4]
NEXT [1, 2, 3, 5, 4]
[5]
NEW [3] [5]
NEW [4] [3, 5]
NEW [2] [4, 3, 5]
NEW [1] [2, 4, 3, 5]
NEXT [1, 2, 4, 3, 5]
[3]
NEW [5] [3]
NEW [4] [5, 3]
NEW [2] [4, 5, 3]
NEW [1] [2, 4, 5, 3]
NEXT [1, 2, 4, 5, 3]
[4]
NEW [3] [4]
NEW [5] [3, 4]
NEW [2] [5, 3, 4]
NEW [1] [2, 5, 3, 4]
NEXT [1, 2, 5, 3, 4]
[3]
NEW [4] [3]
NEW [5] [4, 3]
NEW [2] [5, 4, 3]
NEW [1] [2, 5, 4, 3]
NEXT [1, 2, 5, 4, 3]
[5]
NEW [4] [5]
NEW [2] [4, 5]
NEW [3] [2, 4, 5]
NEW [1] [3, 2, 4, 5]
NEXT [1, 3, 2, 4, 5]
CodePudding user response:
I did an experiment to illustrate how the flow of the generator works:
def _permutate(elems):
if len(elems) <= 1:
print(elems) # NEW
yield elems
else:
for i in range(len(elems)):
for perm in _permutate(elems[:i] elems[i 1:]):
print([elems[i]] perm) # NEW
yield [elems[i]] perm
# NEW
gen = _permutate([1,2,3,4,5])
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
OUTPUT:
[5]
[4, 5]
[3, 4, 5]
[2, 3, 4, 5]
[1, 2, 3, 4, 5]
NEXT [1, 2, 3, 4, 5]
[4]
[5, 4]
[3, 5, 4]
[2, 3, 5, 4]
[1, 2, 3, 5, 4]
NEXT [1, 2, 3, 5, 4]
[5]
[3, 5]
[4, 3, 5]
[2, 4, 3, 5]
[1, 2, 4, 3, 5]
NEXT [1, 2, 4, 3, 5]
[3]
[5, 3]
[4, 5, 3]
[2, 4, 5, 3]
[1, 2, 4, 5, 3]
NEXT [1, 2, 4, 5, 3]
[4]
[3, 4]
[5, 3, 4]
[2, 5, 3, 4]
[1, 2, 5, 3, 4]
NEXT [1, 2, 5, 3, 4]
[3]
[4, 3]
[5, 4, 3]
[2, 5, 4, 3]
[1, 2, 5, 4, 3]
NEXT [1, 2, 5, 4, 3]
[5]
[4, 5]
[2, 4, 5]
[3, 2, 4, 5]
[1, 3, 2, 4, 5]
NEXT [1, 3, 2, 4, 5]