Non Continuous Subsequences

[Bruce Frederiksen]

On Wed, 30 Jul 2008 09:32:25 -0700, bearophileHUGS wrote:

> This post is not about practical stuff, so if you have little time,
> you may ignore it.
> 
> This is a task of the rosettacode.org site:
> http://www.rosettacode.org/wiki/Non_Continuous_Subsequences
> 
> A subsequence contains some subset of the elements of this sequence,
> in the same order. A continuous subsequence is one in which no
> elements are missing between the first and last elements of the
> subsequence. The task is to enumerate all non-continuous subsequences
> for a given sequence.
> 
> Translating the Scheme code to Python was easy (and I think this is
> quite more readable than the Scheme version):
> 
> def ncsub(seq, s=0):
>     if seq:
>         x = seq[:1]
>         xs = seq[1:]
>         p2 = s % 2
>         p1 = not p2
>         return [x + ys for ys in ncsub(xs, s + p1)] + ncsub(xs, s +
> p2)
>     else:
>         return [[]] if s >= 3 else []
> 
> Output:
> 
>>>> ncsub(range(1, 4))
> [[1, 3]]
>>>> ncsub(range(1, 5))
> [[1, 2, 4], [1, 3, 4], [1, 3], [1, 4], [2, 4]]
>>>> ncsub(range(1, 6))
> [[1, 2, 3, 5], [1, 2, 4, 5], [1, 2, 4], [1, 2, 5], [1, 3, 4, 5], [1,
> 3, 4], [1, 3, 5], [1, 3], [1, 4, 5], [1, 4], [1, 5], [2, 3, 5], [2, 4,
> 5], [2, 4], [2, 5], [3, 5]]
> 
> <snip>
> 
> But in many cases you can create a lazy code in Python too, even if
> that may be harder. So I have tried to create a lazy version for
> Python, hoping to speed up the code avoiding the creation and joining
> of most/all sublists, but I have failed so far (once I have created a
> lazy Python version, I can probably create a short lazy version in D
> too, my D libs contain most of itertools module too).
> 
> In my failed attempts I have used chain() to join the sublists,
> islice() to slice their items, and iter() to make the management more
> uniform when the input seq is a Python list instead of an xrange, etc.

Try this:

import itertools

def ncsub(seq, s = 0):
    if seq:
        x = seq[:1]
        xs = seq[1:]
        p2 = s % 2
        p1 = 1 - p2
        return itertools.chain(
                   itertools.imap(lambda ys: x + ys, ncsub(xs, s + p1)),
                   ncsub(xs, s + p2))
    else:
        return [[]] if s >= 3 else []

>>> ncsub(range(1, 4))
<itertools.chain object at 0xb7de528c>
>>> list(ncsub(range(1, 4)))
[[1, 3]]
>>> list(ncsub(range(1, 5)))
[[1, 2, 4], [1, 3, 4], [1, 3], [1, 4], [2, 4]]
>>> list(ncsub(range(1, 6)))
[[1, 2, 3, 5], [1, 2, 4, 5], [1, 2, 4], [1, 2, 5], [1, 3, 4, 5], [1, 
3, 4], [1, 3, 5], [1, 3], [1, 4, 5], [1, 4], [1, 5], [2, 3, 5], [2, 4, 
5], [2, 4], [2, 5], [3, 5]]