Minority Opinions

Not everyone can be mainstream, after all.

Infinitely Iterable Permutations

leave a comment »

For some crazy reason that didn’t end up needing it, I decided to write a permutation generator that could accept an infinite sequence.  After a bit of experimentation, I managed something based on the second sample permutations() implementation in the itertools documentation.  It will still chew up unbounded amounts of memory and time, but always spits out as many permutations as it can before collecting a new element from the input sequence.

from itertools import product

def iperms(iterable, r):
    r'''Permutation generator.
        Differs from itertools.permutations() in that it accepts infinite iterables;
        that also causes it to return results in a different order, and require r.

        >>> ' '.join(map(''.join, iperms('ABCD', 2)))

        >>> from itertools import count, imap, islice
        >>> ' '.join(map(''.join, islice(iperms(imap(str, count(3)), 2), 20)))
        '34 43 35 45 53 54 36 46 56 63 64 65 37 47 57 67 73 74 75 76'

        >>> from itertools import count, imap, islice
        >>> ' '.join(map(''.join, islice(iperms(imap(str, count(3)), 3), 18)))
        '345 354 435 453 534 543 346 356 364 365 436 456 463 465 536 546 563 564'
    n = 0
    pool = []
    for item in iterable:
        n += 1
        for indices in product(range(n), repeat=r):
            iset = set(indices)
            if len(iset) == r and n-1 in iset:
                yield tuple(pool[i] for i in indices)

Yes, it could be optimized; there are a whole lot of product() results that are simply thrown out.  If I were using it for something important, I would work on it some more, but I just don’t care enough right now.  The two-item case in particular displays a pattern that looks easily optimizable, but the addition of more elements seems to defeat that.


Written by eswald

20 Dec 2011 at 8:08 pm

Posted in Python, Technology

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s