#OK to post
#Soham Palande, Assignment 14, 10/25/2020




#PART 1

CountRuns:=proc(L,k) local count,i:
count:=0:
for i from 1 to (nops(L)-k+1) do
       if nops({op(i..i+k-1,L)})=1 then
           count:=count+1:
       fi:
od:
count:
end:

#EXAMPLE
L:=[1,2,2,2,1,1,1,1,2,2,2]
L := [1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2]
CountRuns(L,3)
4




# PART 2

with(Statistics):
AvePathRuns:=proc(m,n,k,N) local runs,path,avg,i,run,std_dev:
runs:=[]:
path:=[]:
avg:=0:
std_dev:=0:
run:=0:
for i from 1 to N do
     path:=RPath(m,n):
     run:=CountRuns(path,k):
     runs:=[op(runs),run]:
od:
avg:=Mean(runs):
std_dev:=StandardDeviation(runs):
[avg,std_dev]:
end:



seq(AvePathRuns(200,200,5,3000),i=1..10)
[24.1936666666667, 7.41236405850842], [24.1833333333333, 7.38037118636353], [24.1336666666667, 7.67624744349912], [24.2533333333333, 7.41346581435988], [24.0440000000000, 7.50436556284631], [24.1063333333333, 7.45834446707972], [23.9666666666667, 7.57302267568050], [24.1233333333333, 7.28270564346696], [24.1436666666667, 7.61877342217073], [24.2373333333333, 7.40958659755980]


The average and standard deviations are consistent.



#PART 3

with(Statistics):
AveGPathRuns:=proc(m,n,k,N) local runs,path,avg,i,run,std_dev:
runs:=[]:
path:=[]:
avg:=0:
std_dev:=0:
run:=0:
for i from 1 to N do
     path:=RGPath(m,n):
     run:=CountRuns(path,k):
     runs:=[op(runs),run]:
od:
avg:=Mean(runs):
std_dev:=StandardDeviation(runs):
[avg,std_dev]:
end:



seq(AveGPathRuns(200,200,5,3000),i=1..10)
[24.2216666666667, 7.64355972201196], [24.0206666666667, 7.28161476093944], [24.0966666666667, 7.37225240959318], [24.1183333333333, 7.27511555401908], [24.0470000000000, 7.46395971082742], [24.2466666666667, 7.50257189795052], [24.1300000000000, 7.48254164549000], [24.1063333333333, 7.32640784920413], [24.2370000000000, 7.44768333078585], [24.1340000000000, 7.66896222839529]


The average and std deviation are very similar to the ones for all paths.


#PART 5


#We will the property of Dyck Path that the partial sum of the path must be non-negative


GoodBrother:=proc(L)local S,s,y,i,sum,len:
#get the set of all cycle shifts
S:=CycShi(L):
sum:=0:
for s in S do
    for i from 1 to nops(s) do
          sum:=sum+s[i]:
          if (sum<0) then
             break
          fi:
    od:
    if sum>=0 and s[nops(s)]=1 then
       RETURN(s):
    fi:
    sum:=0:
od:
end:


GoodBrother([1,-1,-1,1,1,1,1,-1,-1,-1,1])
[1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1]


#PART 6


Let w be a word using the alphabet {1,-1} that adds up to 1.

We want to show that all the cyclic shifts of w are distinct.

#PROOF:

Let w be [1]. Then w adds up to one and uses alphabet (1,-1) and has no identical cyclic shifts.

Now lets arbitrarily add an element from the alphabet to w. If we add 1, then we must add a -1 as well so that w adds up to 1. Similarly, if we add -1 then we must add 1. Then,

w=[1,1,-1] -> this also has all unique cyclic shifts 

Now let us add another element from the alphabet {1,-1} to w. By the above reasoning, we must add both a -1 and 1 to satisfy the requirement that w adds up to 1.

w=[1,1,-1,1,-1] -> all the cyclic shifts are unique.

By principle of mathematical induction, 

If we suppose that w adds up to one and has all unique cyclic shifts, then if we add an element from the alphabet, we must add the other elements as well (i.e. we must add both elements 1,-1).

Adding 1,-1 still satisfies the property that w adds up to 1 and also has unique cyclic shifts.

Thus, all the cyclic shifts of a word in {1,-1} that adds up to 1 are distinct.



# PART 7

RandSetPartition1:=proc(n,k) local S,res:
#k must be between 1 and n
res:=LDie([Snk(n-1,k-1), k*Snk(n-1,k)]):
if n=0 then
  RETURN():
fi: 
if k=0 then
  RETURN():
fi:
if res=Snk(n-1,k-1) then 
   S:=RandSetPartition1(n-1,k-1):
   S:={op(S),{n}}:

else
   S:=RandSetPartition1(n-1,k):
   S:={op(S[rand(1..k)]),n}:
fi:
S:
end:

RandSetPartition:=proc(n) local k:
k:=LDie([seq(Snk(n,k),k=1..n)]):
RandSetPartition1(n,k)
end: