Advertisement
Guest User

Random Parentheses Sequence

a guest
Sep 2nd, 2013
509
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.93 KB | None
  1. import random
  2.  
  3. # Quadric algorithm
  4.  
  5. def correct(seq):
  6.   balance = 0
  7.   for c in seq:
  8.     balance += 1 if c == '(' else -1
  9.     if (balance < 0):
  10.       return False
  11.   return True
  12.  
  13. def tryAndCheck(n):
  14.   seq = [')', '('] * n
  15.   while (not correct(seq)):
  16.     random.shuffle(seq)
  17.   return seq
  18.  
  19. # Linear algorithm
  20.  
  21. def tryAndFix(n):
  22.   seq  = ['(', ')'] * n
  23.   random.shuffle(seq)
  24.  
  25.   stack   = []
  26.   result  = []
  27.  
  28.   balance = 0
  29.   prev    = 0
  30.   for pos in range( len(seq) ):
  31.     balance += 1 if seq[pos] == '(' else -1
  32.     if balance == 0:
  33.       if seq[prev] == '(':
  34.         result.extend( seq[ prev : pos + 1 ] )
  35.       else:
  36.         result.append('(')
  37.         stack.append( [ ')' if v == '(' else '(' for v in seq[ prev + 1 : pos ] ] )
  38.       prev = pos + 1  
  39.  
  40.   for lst in reversed(stack):
  41.     result.append(')')
  42.     result.extend(lst)
  43.  
  44.   return result
  45.  
  46. print "".join( tryAndCheck(50) )
  47. print "".join( tryAndFix(50) )
Advertisement
RAW Paste Data Copied
Advertisement