light
BAN USERwe maintain an auxiliary array that holds the result upto a given value. rest is straight forward, very simple code
#!/usr/bin/python
def noncons(lst):
n=len(lst)
res=[0]*(n+2)
for i in range(n):
l,r=res[i]+lst[i],res[i+1]
res[i+2]=max(l,r)
return res[n+1]
if __name__=='__main__':
lst=[1,2,3,4,5,6]
print noncons(lst)
#!/usr/bin/python
def permute(s,cur,pos,n):
#prints all permutation of a given string O(n*n!)
#assuming unique characters present it prints the lexicographic-unique sequence
#but it fails to print unique sequence if there are repeating characters
global visited
if pos==n:
print ''.join(cur)
return
for i in range(n):
if not visited[i]:
cur[pos]=s[i]
visited[i]=True
permute(s,cur,pos+1,n)
visited[i]=False
def permutations(s): #solution to the above problem
#prints all unique permutation of a given string in lexicographic order TIME:O(n*n!)
n=len(s)
def next():
k,l=-1,-1
for i in range(n-1):
if s[i]<s[i+1]: k=i
if k==-1: return None
for i in range(k+1,n):
if s[k]<s[i]: l=i
cur=list(s[k:])
cur[0],cur[l-k]=cur[l-k],cur[0]
return s[:k]+'%c%s'%(cur[0],''.join(cur[:0:-1]))
while s:
print s
s=next()
if __name__=='__main__':
s='aabcd'
n=len(s)
#visited=[False]*n
#permute(s,[0]*n,0,n)
permutations(s)
#!/usr/bin/python
def partition(cur,pos,m,n):
#prints all unique partitions of a number (lexicographic order)
if n==0:
print cur[:pos]
return
for i in range(m,n+1):
cur[pos]=i
partition(cur,pos+1,i,n-i)
def apart(cur,pos,n): #this solves the given question
#prints all paritions of a number (no order)
if n==0:
print cur[:pos]
return
for i in range(1,n+1):
cur[pos]=i
apart(cur,pos+1,n-i)
if __name__=='__main__':
n=5
#partition([0]*n,0,1,n)
apart([0]*n,0,n)
found one small bug in the code!
- light February 23, 2013updated = splits[0].strip()+'- ('+splits[1].strip()+')'
is the correct update and not
updated = splits[0].strip()+'- '+splits[1].strip()