##### Permutations

# A permutation of the number 0 to n-1 can be represented by an Array containing
# only the number 0 to n-1, each number occurring only once in the array.

P1=[0,2,1]  # is permutation
P2=[4,2,1,3] #is not 
P3=[0,1,2,3]  # identity permutation  P3[i]==i
P4 = [5,2,2,0]  # is not

def counts(x,A): # returns number of times that x is found in A
   cx = 0
   for y in A:
      if (x==y): cx += 1
   return cx
#

def isperm1(P):  # return True/False depending on if P is a permutation
  n = len(P)
  # check each number from 0 to n-1 occurs once in P
  answer = True
  i = 0
  while answer and i<=n-1:
     if count(i,P)!= 1: answer = False
     i += 1
  #
  return answer
#isperm1  - O(n**2), not very efficient

def isperm2(P):
   n = len(P)
   B = []
   i = 0
   answer = True
   while answer and i < n:
      if P[i] < 0 or P[i] >=n: answer = False
      elif P[i] in B: answer = False
      else:
         B.append(P[i])
      i += 1
   #while
   return answer
#isperm2,  better than isperm1 but still O(n**2)

def isperm(P):
   n = len(P)
   C = [0]*n
   answer = True
   i = 0
   while answer and i<n:
      if P[i]<0 or P[i]>=n: answer=False
      else: C[ P[i] ] += 1
      i += 1
   #while
   i = 0
   while answer and i<n:
      if C[i]!=1: answer = False
      i += 1
   #while
   return answer
#isperm
print(isperm([3,2,0,1,4]))
print(isperm([3,0,2,3]))
#  isperm is a O(n) or 'linear time' algorithm
# O(1), O(log n), O(n), O(n*log n), O(n**2), O(n**3), .... O(2**n)

MS = "abcdefghi"
Perm=[3,1,7,5,0,8,6,2,4]
def permute(s,P):  # permute s by permutation P
   if (len(s)!=len(P)): raise Exception("string and perm must have same length")
   ps = "" # permuted string
   i = 0
   while i<len(s):
      ps = ps + s[ P[i] ]
      i += 1
   #while
   return ps
#permute

MS2 = permute(MS,Perm)
print(MS2)

# Given P, build the "inverse permutation" Q:  Q[ P[i] ] == i

def inverseperm(P): # returns an array Q representing the inverse of perm P.
   Q = [0]*len(P)
   i = 0
   while i<len(Q):
      Q[ P[i] ] = i
      i += 1
   #
   return Q
#inverseperm
print(permute(MS2,inverseperm(Perm)))

# generating a random permutation
from random import randint
def genperm(n): 
    P = [0]*n
    i = 1
    while i<n:  # create identity permutation with P[i]==i
        P[i] = i;
        i += 1
    # first while
    i = 0
    while i<n-1:  # permute identity permutation via random swaps
        r = randint(i,n-1)  # don't write this as randint(0,n-1)
        P[i],P[r] = P[r],P[i]
        i += 1
    # second while
    return P
#genperm
# Each possible sequence of n-1 random numbers used by this function will
# generate one of n! permutations that are possible, with an even
# probability distribution (every permutation will have an equal chance 
# of being generated)