This generator is interesting for calling itself recursively.
The first time you come across recursion, it blows your mind, then you have an epiphany of the power of the technique. It makes some problems easy to code, as here. Lars had two epiphanies when he was 19. One of them was recursion.
def permutate(collection):
'''Yields all the permutations of the collection.
The collection must be sliceable.'''
for i, item in enumerate(collection):
subcollection = collection[:i] + collection[i+1:]
if subcollection:
for permutation in permutate(subcollection):
yield item + permutation
else:
yield item
list(permutate('RGB'))
['RGB', 'RBG', 'GRB', 'GBR', 'BRG', 'BGR']
Compare that to how permutations from itertools works.
from itertools import permutations
list(permutations('RGB'))
[('R', 'G', 'B'), ('R', 'B', 'G'), ('G', 'R', 'B'), ('G', 'B', 'R'), ('B', 'R', 'G'), ('B', 'G', 'R')]
list(permutations([2, 3, 5]))
[(2, 3, 5), (2, 5, 3), (3, 2, 5), (3, 5, 2), (5, 2, 3), (5, 3, 2)]
list(permutations([(2,), (3,), (5,)]))
[((2,), (3,), (5,)), ((2,), (5,), (3,)), ((3,), (2,), (5,)), ((3,), (5,), (2,)), ((5,), (2,), (3,)), ((5,), (3,), (2,))]
list(permutations([2]))
[(2,)]
Now I make permutate have the same output as permutations from itertools.
This code is written for readability, not for speed. Concatenation is slow. It would probably be faster to use the extend method of list.
def permutate(collection):
for i, item in enumerate(collection):
subcollection = collection[:i] + collection[i+1:]
if subcollection:
for permutation in permutate(subcollection):
yield (item,) + permutation
else:
yield (item,)
# Ensure that my permutate yields the same output as permutations from itertools.
# My tests are nowhere exhaustive.
test_cases = (
'RGB',
[(2,), (3,), (5,)],
[2, 3, 5],
[2],
)
def test():
for collection in test_cases:
assert list(permutate(collection)) == list(permutations(collection)), (
collection, list(permutate(collection)), list(permutations(collection)))
return 'All tests passed'
test()
'All tests passed'