Is there an alternative to python's permutations for generator input?

Question

I am trying to use an unbounded generator in itertools.permutations but it doesn't seem to be working. The return generator is never created because the function just runs forever. To understand what I mean, consider:

from itertools import count, permutations
all_permutations = permutations(count(1), 4)

How I imagine this working is that it generates all possible 4-length permutations of the first 4 natural numbers. Then it should generate all possible 4-length permutations of the first 5 natural numbers, with no repeats so 5 must be included in all of these. What happens though is that python is hung on creating all_permutations.

Before I go off and create my own function from scratch, I am wondering if there is another library that might be able to do what I'm looking for? Also, shouldn't the built-in function here be able to handle this? Is this perhaps a bug that should be worked out?

EDIT: For some iterations...

1 2 3 4
1 2 4 3
...
4 3 2 1
1 2 3 5
1 2 5 3
...
5 3 2 1
1 2 4 5
1 2 5 4
...

Answer 1

Nice question! Here's an efficient method that generates them systematically, without repetitions (and without any need to check):

1. First the permutations of the first n elements;
2. then the permutations involving the n+1st element and n-1 of the previous ones;
3. then those involving the n+2nd element and n-1 of the previous ones, etc.

In other words, the last element drawn is always included in the current batch. This only keeps around a tuple of the consumed source elements (unavoidable, since we'll keep using all of them in permutations).

As you can see, I simplified the implementation a little: Instead of step 1, I initialize the base with n-1 elements and go straight to the main loop.

from itertools import islice, permutations, combinations

def step_permutations(source, n):
    """Return a potentially infinite number of permutations, in forward order"""

    isource = iter(source)
    # Advance to where we have enough to get started
    base = tuple(islice(isource, n-1))

    # permutations involving additional elements:
    # the last-selected one, plus <n-1> of the earlier ones
    for x in isource:
        # Choose n-1 elements plus x, form all permutations
        for subset in combinations(base, n-1):
            for perm in permutations(subset + (x,), n):
                yield perm

        # Now add it to the base of elements that can be omitted 
        base += (x,)

Demonstration:

>>> for p in step_permutations(itertools.count(1), 3):
    print(p)

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
(1, 2, 4)
(1, 4, 2)
(2, 1, 4)
(2, 4, 1)
(4, 1, 2)
(4, 2, 1)
(1, 3, 4)
(1, 4, 3)
(3, 1, 4)
(3, 4, 1)
(4, 1, 3)
(4, 3, 1)
(2, 3, 4)
(2, 4, 3)
(3, 2, 4)
...