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

user_7471403 0
Viewed 1313

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
...
infinite permutation itertools generator python
2 Answers

Something like this:

from itertools import count, permutations

def my_permutations(gen, n=4):
    i = iter(gen)
    population = []
    seen = set()
    while True:
        for p in permutations(population, n):
            if p not in seen:
                yield p
                seen.add(p)
        population.append(next(i))

Beware, the memory usage is growing forever, but as far as I can see there is no way around that.

More efficient version:

def my_permutations(gen, n=4):
    i = iter(gen)
    population = []
    while True:
        population.append(next(i))
        *first, last = population
        perms = permutations(first, n-1)
        yield from (p[:i] + (last,) + p[i:] for p in perms for i in range(n))
user_6740390

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)
...
user_6993050
Related