Non Continuous Subsequences

[Kay Schluehr]

Here is an evil imperative, non-recursive generator:

def ncsub(seq):
    n = len(seq)
    R = xrange(n+1)
    for i in xrange(1,2**n):
        S  = []
        nc = False
        for j in R:
            k = i>>j
            if k == 0:
                if nc:
                    yield S
                break
            elif k%2 == 1:
                S.append(seq[j])
            elif S:
                nc = True

And here is a cython version without yield expression which won't work
with cython:

def ncsub(seq):
    n = len(seq)
    cdef int i,j,k,nc
    res = []
    R = xrange(n+1)
    for i in xrange(1,2**n):
        S  = []
        nc = False
        for j in R:
            k = i>>j
            if k == 0:
                if nc:
                    res.append(S)
                break
            elif k%2 == 1:
                S.append(seq[j])
            elif S:
                nc = True
    return res


Application: list(ncsub(range(19)))

On my 1.5GHz notebook your original version needed 11.2s ( psyco
version = 9.5s), my pure Python generator got it in 7.75s and the
cython version in 2.3s.

[Yes, I have too much time...]