Non Continuous Subsequences

[Mensanator]

On Jul 30, 11:32 am, bearophileH... at lycos.com 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.
>

That's equivalent to asking which n-bit binary numbers have
at least one 0 bracketed by 1s, isn't it?

import gmpy
import re

for i in xrange(32):
  s = gmpy.digits(i,2).zfill(5) # convert to base 2 (padded)
  m = re.search('10+1',s)       # at least one 0 between 1s
  if m:
    z = [j+1 for j,i in enumerate(s) if i=='1']
    print z

##  [3, 5]
##  [2, 5]
##  [2, 4]
##  [2, 4, 5]
##  [2, 3, 5]
##  [1, 5]
##  [1, 4]
##  [1, 4, 5]
##  [1, 3]
##  [1, 3, 5]
##  [1, 3, 4]
##  [1, 3, 4, 5]
##  [1, 2, 5]
##  [1, 2, 4]
##  [1, 2, 4, 5]
##  [1, 2, 3, 5]