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