Re: Non Continuous Subsequences

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]]
.

Relevant Pages