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]]
--
http://mail.python.org/mailman/listinfo/python-list
