Random Parentheses Sequence

import random

# Quadric algorithm

def correct(seq):
  balance = 0
  for c in seq:
    balance += 1 if c == '(' else -1
    if (balance < 0):
      return False
  return True

def tryAndCheck(n):
  seq = [')', '('] * n
  while (not correct(seq)):
    random.shuffle(seq)
  return seq

# Linear algorithm

def tryAndFix(n):
  seq  = ['(', ')'] * n
  random.shuffle(seq)

  stack   = []
  result  = []

  balance = 0
  prev    = 0
  for pos in range( len(seq) ):
    balance += 1 if seq[pos] == '(' else -1
    if balance == 0:
      if seq[prev] == '(':
        result.extend( seq[ prev : pos + 1 ] )
      else:
        result.append('(')
        stack.append( [ ')' if v == '(' else '(' for v in seq[ prev + 1 : pos ] ] )
      prev = pos + 1

  for lst in reversed(stack):
    result.append(')')
    result.extend(lst)

  return result

print "".join( tryAndCheck(50) )
print "".join( tryAndFix(50) )