Recursive DFS implementation of itertools.permutations

permutations.py

from collections.abc import Iterable, Sized

def cycle_last_n(items: Sized, n: int):
    prefix, to_cycle = items[:-n], items[-n:]
    for _ in range(n):
        yield prefix + to_cycle
        to_cycle = to_cycle[1:] + to_cycle[:1] 

def _permutations(items: Sized, n: int):
    if n == 1:
        yield items
    else:
        for node in cycle_last_n(items, n):
            yield from _permutations(node, n-1)

def permutations(items: Iterable):
    if not isinstance(items, Sized):
        items = tuple(items)
    yield from _permutations(items, len(items))

list(permutations([1,2,3,4]))
"""
Out:
[[1, 2, 3, 4],
 [1, 2, 4, 3],
 [1, 3, 4, 2],
 [1, 3, 2, 4],
 [1, 4, 2, 3],
 [1, 4, 3, 2],
 [2, 3, 4, 1],
 [2, 3, 1, 4],
 [2, 4, 1, 3],
 [2, 4, 3, 1],
 [2, 1, 3, 4],
 [2, 1, 4, 3],
 [3, 4, 1, 2],
 [3, 4, 2, 1],
 [3, 1, 2, 4],
 [3, 1, 4, 2],
 [3, 2, 4, 1],
 [3, 2, 1, 4],
 [4, 1, 2, 3],
 [4, 1, 3, 2],
 [4, 2, 3, 1],
 [4, 2, 1, 3],
 [4, 3, 1, 2],
 [4, 3, 2, 1]]
"""