Re: Non Continuous Subsequences

On Jul 30, 11:32 am, bearophileH...@xxxxxxxxx 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]
.

Relevant Pages