Wrapping around a list

[rusi]

On Wednesday, November 27, 2013 4:16:50 PM UTC+5:30, Amjad Syed wrote:
> Hello,
> 
> I am working on a problem (Bioinformatics domain) where all possible combinations of input string needs to be printed as sublist

If we take the standard combinations (Pascal triangle) result
nCr + nCr-1 = n+1Cr
and make it into a recursive python function we get:

def c(n,r):
    return (1 if r == 0 else
           0 if n == 0 else
           c(n-1,r) + c(n-1,r-1))

(yeah the base cases are tricky)

Now instead of enumerating the *number* of combinations if we want the 
combinations *themselves* we can do almost isomorphically:
[Writing d analogous to c]

def d(l,r):
    if r == 0: return [[]]
    if not l: return []   
    x  = l[0]
    xs = l[1:]
    return d(xs,r) + [[x]+c for c in d(xs,(r-1))]

Note the difference in types:

>>> c(4,2)
6
>>> d("LEQN", 2)
[['Q', 'N'], ['E', 'N'], ['E', 'Q'], ['L', 'N'], ['L', 'Q'], ['L', 'E']]
>>> 

Now we can generator-ize it like so:

def e(l,r):
    if r == 0:
        yield []
    elif l:
        x  = l[0]
        xs = l[1:]
        for y in chain(e(xs,r),([x]+c for c in e(xs,(r-1)))):
            yield y
# python 3: yield from chain(e(xs,r),([x]+c for c in e(xs,(r-1))))


called as
>>> list(e("LEQN", 2))
[['Q', 'N'], ['E', 'N'], ['E', 'Q'], ['L', 'N'], ['L', 'Q'], ['L', 'E']]
>>> 

BTW: This is neater in Haskell than in Python.

c n 0 = 1
c 0 r = 0
c n r = c (n-1) r + c (n-1) (r-1) 

   
d l      0 = [[]]
d []     r = [] 
d (x:xs) r = d xs r ++ [x:c | c <- d xs (r-1)]

In particular the 'd' has list elegance of the python 'd' and generator 
efficiency of python 'e'