quixey.py

quixey.py

'''
1. Write a (stateless) function nextPermutation that takes a permutation (as a 
list) on the elements of the set {1, ..., n} and returns the "next" permutation, 
so that chaining n! calls to nextPermutation([1, ..., n]) results in the generation 
of every permutation on the set {1, ..., n}.
'''

def nextPermutation(l):
  # select subset of l to use as digits of next
  for i in range(len(l)-2,-1,-1):
    for j in range(len(l[i:])):
      lslice=sorted(l[i:])
      lcandidate=list(l[:i])      
      lcandidate.append(lslice.pop(j))
      lcandidate.extend(lslice)
      if lcandidate>l: return lcandidate      
  print "Highest permutation reached."

def testNextPermutation():
  p=[1,2,3,4,5]
  for n in range(120):
    print p
    p=nextPermutation(p)
    
# testNextPermutation()

'''
2. A client connects to a server which will stream it N 32-bit integers and then disconnect,
where N is a-priori unknown to the client. Describe an O(log N)-space algorithm you could 
run on the client that would return any of the N integers with probability 1/N. 
(The algorithm only gets run once.)

'''

'''
We need to separate the integers into N/log(N) bins. So that each one bin contains log(N) integers.
Since we run this algorithm after N is known, otherwise the probability of selecting out of the N won't
be = 1/N. 

First, get max and min of the stream while streaming it in. Then get the size of a bin = (max-min)*log(N)/N
Reject all stream data except those that fall into a randomly selected bin out of all bins by
looping through the stream data and saving only those which fall into that bin.
Then uniform randomly select an element from that bin. This gives us approximately a 1/N chance of selecting
any of the integers with space log(N).
'''
  
'''
3. A quine is a program that outputs its own code. Write a Python function counted_quine 
with docstring "This function has been quined 0 times." The function should output a string 
that exactly matches its code except that the 0 in the docstring should be 1. The outputted 
function should output the same thing but with the 1 replaced with 2, et cetera ad infinitum. 
The real challenge of a quine is that a function has to output its source code without ever 
being inputted its source code – so please don't rely on something like __file__.
'''

def counted_quine():
  '''This function has been quined 0 times.'''
  q=39
  code=['def counted_quine():','  %c%c%cThis function has been quined %d times.%c%c%c','  q=39','  code=[%c%s%c,%c%s%c,%c%s%c,%c%s%c,%c%s%c,%c%s%c,%c%s%c,%c%s%c,%c%s%c,%c%s%c]','  args=[(),(q,q,q,%d,q,q,q),(),(q,code[0],q,q,code[1],q,q,code[2],q,q,code[3],q,q,code[4],q,q,code[5],q,q,code[6],q,q,code[7],q,q,code[8],q,q,code[9],q),(),(),(),(37),(),(37)]','  for i in range(10):','    if i==4:','      print code[4] %c (args[1][3]+1)','    else:','      print code[i] %c args[i]']
  args=[(),(q,q,q,1,q,q,q),(),(q,code[0],q,q,code[1],q,q,code[2],q,q,code[3],q,q,code[4],q,q,code[5],q,q,code[6],q,q,code[7],q,q,code[8],q,q,code[9],q),(),(),(),(37),(),(37)]
  for i in range(10):
    if i==4:
      print code[4] % (args[1][3]+1)
    else:
      print code[i] % args[i]