### written by: aurora hiveley, rutgers university
### last updated: 6/29/25

print(`This is wordle.txt, a Maple package by Aurora Hiveley (Rutgers University)`):
print(`For a list of the functions, type Help(); for help with a specific function type: Help(FunctionName);`):
print(`For functions verifying results from Hiveley (2025), type HelpThm();`):

Help:=proc(): 

if nargs=0 then 

print(`ALL FUNCTIONS:`):
print(`bestStrats(n,setS), bestStratsIt(n,type), cyclicPerms(n), cyclicPermsGT(n), cyclicStrats(n), derange(n),`):
print(`derangeStrats(n), Exc(p), excFunc(n), excFunc2(s,type,K :=1), gf(n,s,var), gfAvg(n,s), guesser(setP,s,boolSee := false), guesserInpt(setP,iniP,s,boolSee := false),`):
print(`guesserOld(setP,s,boolsee := false), howLong(setP,s), indexAnalysis(s), indexAnalysisK(s,K), indexAverage(s), inductiveStrat(n), isCyc(p), isDer(p), isPerm(p), `):
print(`kExcPerms(n,k), kGuesses(s,k), kGuessesR(s,k,r), KS(n), KSInd(n,p), KSL(n), mostCorrect(S), nextGuess(setP,p,s,boolSee := false), nextPermTyped(p,type), nextStrat(s,type), `):
print(`permChecker(p1,p2), permInd(setP,p), rankStrats(n,setS), rankStratsIt(n,type), stratChecker(p,s), worstStrats(n,setS)`):


## GUESSERS HELP

elif nargs=1 and args[1]=guesserInpt then
print(`guesserInpt(setP, iniP, s, boolSee): starting with initial guess permutation on [n],`):
print(`uses nextGuess and strategy = s to repeatedly attempt to guess fixed permutation`):
print(`inputs: fixed permutation setP, initial guess permutation iniP, strategy s, boolean for printing each guess boolSee (default is false)`):
print(`outputs: number of turns until guesses correctly`):
print(`example: guesserInpt([1,2,3,4],[4,1,3,2],random,true); guesserInpt([1,2,3,4],[4,1,3,2],cyclic,false); `):

elif nargs=1 and args[1]=guesserOld then
print(`guesserOld(setP, s, boolSee): starting with the trivial permutation on [n],`):
print(`uses nextGuess and strategy = s to repeatedly attempt to guess fixed permutation.`):
print(`note that there is no accounting for an infinite loop, i.e. guessing the same two or more guesses in sequence repeatedly.`):
print(`inputs: fixed permutation setP, strategy s, boolean for printing each guess & incorrect indices boolSee (default is false)`):
print(`outputs: number of turns until guesses correctly`):
print(`example: guesser([4,1,3,2],random,true); guesser([4,1,3,2],cyclic,false); `):

elif nargs=1 and args[1]=guesser then
print(`guesser(setP, s, boolSee): starting with the trivial permutation on [n],`):
print(`uses nextGuess and strategy = s to repeatedly attempt to guess fixed permutation.`):
print(`returns infinity if strategy forces us to guess something that we have already guessed.`):
print(`inputs: fixed permutation setP, strategy s, boolean for printing each guess & incorrect indices boolSee (default is false)`):
print(`outputs: number of turns until guesses correctly`):
print(`example: guesser([4,1,3,2],random,true); guesser([4,1,3,2],cyclic,false); `):


## NEXT GUESS GENERATOR

elif nargs=1 and args[1]=nextGuess then
print(`nextGuess(setP, p, s, boolSee := false): starting with initial guess permutation on [n], locks in correct entries matching final permutation.`):
print(`generates next guess using strategy s, printing locations of incorrect entries if boolSee = true`):
print(`inputs: fixed permutation setP, current guess permutation p, boolean for printing guess's incorrect indices`):
print(`outputs: next permutation`):
print(`--------------------------------------------------------------------------------------------`):
print(`POSSIBLE STRATEGIES: `):
print(`random: locks in correct entries, incorrect entries are permuted randomly to generate next guess`):
print(`example: nextGuess([4,3,2,1],[1,2,3,4], random);`):
print(`cyclic: locks in correct entries, incorrect entries are are cycled one index lower from incorrect indices list (see Kutin & Smithline.)`):
print(`example: nextGuess([4,3,2,1],[1,2,3,4], cyclic);`):
print(`[[1],...]: locks in correct entries, incorrect entries are permuted according to a cyclic permutation from strategy S (a list)`):
print(`example: nextGuess([4,3,2,1],[1,2,3,4],[[1],[2,1],[2,3,1],[2,3,4,1]])`):
print(`note that the above example should produce the same next guess as the cyclic guessing method`):
# S = [[1], [2,1], [2,3,1], [2,..., k,1]] is kutin and smithline


## COMBINATORIAL TOOLS

elif nargs=1 and args[1]=gf then
print(`gf(n,s,var): produces the generating function for strategy s using variable var (default is x)`):
print(`inputs: permutation length n and strategy s`):
print(`outputs: polynomial representing generating function. coefficient a_d represents the number of permutations which took d turns to be guessed correctly.`):
print(`example: gf(4, cyclic, x);`):

elif nargs=1 and args[1]=gfAvg then
print(`gfAvg(n,s): computes the average number of guesses taken by strategy s`):
print(`on a permutation of length n `):
print(`inputs: permutation length n, generating function polynomial p, variable x used in p`):
print(`outputs: average number of guesses for strategy s`):
print(`calculated from generating function by taking weighted average of number of permutations (coefficients)`):
print(`which take N guesses (of x^N)`):
print(`example: gfAvg(4,cyclicStrats(4)[6])`):

elif nargs=1 and args[1]=cyclicPerms then
print(`cyclicPerms(n): generates a set of all cyclic permutations on [n] `):
print(`inputs: permutation length n`):
print(`outputs: set of cyclic permutations`):
print(`example: cyclicPerms(4);`):

elif nargs=1 and args[1]=cyclicPermsGT then
print(`cyclicPermsGT(n): generates all cyclic permutations of [n] using GroupTheory package (to verify validity of our code)`):
print(`inputs: permutation lenght n`):
print(`outputs: set of all cyclic permutations on [n]`):

elif nargs=1 and args[1]=derange then
print(`derange(n): constructs set of permutations on [n] which are derangements `):
print(`inputs: permutation length n`):
print(`outputs: set of derangements`):
print(`example: derange(3)`):


## EXCEDANCES

elif nargs=1 and args[1]=Exc then
print(`Exc(p): returns the set of excedances (values i such that p(i) > i) in a permutation p`):
print(`inputs: permutation p`):
print(`outputs: set of values i which are excedances`):
print(`example: Exc([2,3,1]), Exc([1,2,3])`):

elif nargs=1 and args[1]=excFunc then
print(`excFunc(n): returns a polynomial sum_{p in Der(n)} t^|Exc(p)| `):
print(`where for a term a_k t^k, a_k is the number of derangements of [n] with k excedances`):
print(`inputs: permutation length n`):
print(`outputs: polynomial in t`):
print(`example: excFunc(4):`):

elif nargs=1 and args[1]=excFunc2 then
print(`excFunc2(s,type,var:=t,K:=1): returns a generating function using excedances of derangements which had either at least one `):
print(`or no correct entries (depending on input parameter "type") after one (or K) iteration(s) of guesser using s := S[n]`):
print(`inputs: strategy component s = S[n], type (either correct or incorrect) of locations to look for, optional parameter for gen func variable (default t)`):
print(`and optional parameter K for number of guesses attempted if type = incorrect`):
print(`outputs: polynomial in t`):
print(`example: excFunc2([4,3,2,1],correct):`):

elif nargs=1 and args[1]=kExcPerms then
print(`kExcPerms(n,k): returns the set of permutations of length n with k excedances (note: there should be A(n,k) of them.)`):
print(`inputs: permutation length n, number of excedances k`):
print(`outputs: set of permutations`):
print(`example: kExcPerms(3,1)`):


## STRATEGIES GENERATORS

elif nargs=1 and args[1]=cyclicStrats then
print(`cyclicStrats(n): generates a collection of strategies for permutations of length n using cyclic permutations`):
print(`inputs: permutation length n`):
print(`outputs: set of strategies (as lists of cyclic permutations)`):
print(`example: cyclicStrats(3);`):

elif nargs=1 and args[1]=derangeStrats then
print(`derangeStrats(n): generates a collection of strategies for permutations of length n using derangements`):
print(`inputs: permutation length n`):
print(`outputs: set of strategies (as lists of derangements)`):
print(`example: derangeStrats(3);`):


## STRATEGIES ANALYSIS

elif nargs=1 and args[1]=rankStrats then
print(`rankStrats(n,setS): ranks all strategies on permutations of length n in setS according to average number of guesses until correct `):
print(`inputs: permutation length n`):
print(`outputs: list L of lists l of form [average, {set of strategies with that average number of guesses}] in increasing order by average`):
print(`example: rankStrats(4, cyclicStrats(4))`):

elif nargs=1 and args[1]=bestStrats then
print(`bestStrats(n,setS): identifies optimal strategies on permutations of length n (those with the smallest number of average guesses)`):
print(`out of possible strategies in setS`):
print(`inputs: permutation length n`):
print(`outputs: list of optimal strategies, i.e. those with the minimum number of average guesses`):
print(`example: bestStrats(5)`):

elif nargs=1 and args[1]=worstStrats then
print(`worstStrats(n): identifies least optimal strategies on permutations of length n (those with the highest number of average guesses)`):
print(`out of possible strategies in setS`):
print(`inputs: permutation length n`):
print(`outputs: list of least optimal strategies, i.e. those with the maximum number of average guesses`):
print(`example: worstStrats(5)`):

elif nargs=1 and args[1]=inductiveStrat then 
print(`inductiveStrat(n): returns set of strategies on [n] that are optimal for n-1 and smaller`):
print(`using an inductive approach to identification of the best strategies (mostly to save computation time/memory.)`):
print(`inputs: permutation length n`):
print(`outputs: set of strategies S (note: should have nops(S) = 2*(n-1)!)`):
print(`example: inductiveStrat(6);`):

elif nargs=1 and args[1]=nextStrat then
print(`nextStrat(s,type): returns the next strategy of a certain type (either cyclic or derangement)`):
print(`inputs: strategy s, permutation type (cyclic or der)`):
print(`outputs: next strategy, or FAIL if none`):
print(`example: nextStrat([[1], [2, 1], [2, 3, 1], [2, 1, 4, 3]],der);`):

elif nargs=1 and args[1]=nextPermTyped then
print(`nextPermTyped(p,type): returns the next permutation of a certain type (either cyclic or derangement)`):
print(`inputs: permutation p, permutation type (cyclic or der)`):
print(`outputs: next permutation, or FAIL if none`):
print(`example: nextPermTyped([1,2,3,4],cyclic); nextPermTyped([4,1,3,2],der)`):

elif nargs=1 and args[1]=rankStratsIt then
print(`rankStratsIt(n,type): ranks all strategies on permutations of length n of a given type according to average number of guesses until correct `):
print(`inputs: permutation length n, strategy type (cyclic or der)`):
print(`outputs: list L of lists l of form [average, {set of strategies with that average number of guesses}] in increasing order by average`):
print(`example: rankStratsIt(4, cyclic)`):

elif nargs=1 and args[1]=bestStratsIt then
print(`bestStratsIt(n,type): identifies optimal strategies on permutations of length n (those with the smallest number of average guesses)`):
print(`out of possible strategies of a given type `):
print(`inputs: permutation length n, strategy type (cyclic or der)`):
print(`outputs: list of optimal strategies, i.e. those with the minimum number of average guesses`):
print(`example: bestStratsIt(5, der)`):


### KUTIN-SMITHLINE & MODIFICATIONS

elif nargs=1 and args[1]=KS then 
print(`KS(n): returns Kutin-Smithline's strategy on permutations of length n.`):
print(`formatted as a list of permutations of lengths 1 to n`):
print(`inputs: permutation length n`):
print(`outputs: strategy [[1],[2,1],...[2,3,...,n,1]]`):
print(`example: KS(5);`):

elif nargs=1 and args[1]=KSInd then 
print(`KSInd(n,p): returns strategy which right shifts for components 1 through n-1, but whose n-th component is the input permutation p`):
print(`inputs: strategy length n, permutation p to become S[n]`):
print(`outputs: strategy [[1],[2,1],...[2,3,...,n-1,1],p]`):
print(`example: KSInd(5,[5,1,2,3,4]);`):

elif nargs=1 and args[1]=KSL then 
print(`KSL(n): returns strategy which right shifts for components 1 through n-1 and left shifts for component n`):
print(`inputs: strategy length n`):
print(`outputs: strategy [[1],[2,1],...[2,3,...,n-1,1],[n,1,2,...,n-1]]`):
print(`example: KSL(5);`):


## INDEX ANALYSIS

elif nargs=1 and args[1]=indexAnalysis then
print(`indexAnalysis(s): for a strategy component s = S[n], outputs set of derangements of [n] which have nonempty correct index sets after one guess`):
print(`note that we use derangements to ensure that the first guess (trivial perm) has no correct entries`):
print(`inputs: permutation s corresponding to S[n] (strategy component of length n)`):
print(`outputs: set of derangements on [n] which result in at least one correct entry after generating new guess` ):
print(`example: indexAnalysis([4,1,2,3])`):

elif nargs=1 and args[1]=indexAnalysisK then
print(`indexAnalysisK(s,K): for a strategy component s = S[n] and a number of guesses K, outputs set of derangements of [n] `):
print(`which have empty correct index sets after K guesses using s`):
print(`note that we use derangements to ensure that the first guess (trivial perm) has no correct entries`):
print(`inputs: permutation s corresponding to S[n] (strategy component of length n), number of trials K`):
print(`outputs: set of derangements on [n] which result in at zero correct entries after generating new guess K times` ):
print(`example: indexAnalysisK([4,1,2,3],2)`):

elif nargs=1 and args[1]=indexAverage then
print(`indexAnalysis(s): for a strategy component s = S[n], computes average number of correct indices after one guess`):
print(`note that we use derangements to ensure that the first guess (trivial perm) has no correct entries`):
print(`inputs: permutation s corresponding to S[n] (strategy component of length n)`):
print(`outputs: average number of correct entries after generating new guess` ):
print(`example: indexAverage([4,1,2,3])`):

elif nargs=1 and args[1]=mostCorrect then
print(`mostCorrect(S): identifies strategy components S[n] (permutations of length n) that produce a nonempty set of correct entries`):
print(`for the largest number of derangements of [n]`):
print(`inputs: set of strategy components S[n] (all of same length)`):
print(`outputs: list of strategies with the best performance in indexAnalysis(s)`):
print(`i.e. the strategies that result in correct indices the most frequently for permutations in der(n)`):
print(`example: mostCorrect(cyclicPermsGT(4))`):


## NUMBER OF GUESSES

elif nargs=1 and args[1]=kGuesses then
print(`kGuesses(s,k): the set of permutations guessed in exactly k guesses by strategy s `):
print(`inputs: strategy s and number of guesses k`):
print(`outputs: set of permutations of length n guessable in exactly k guesses`):
print(`example: kGuesses(KS(3),1)`):

elif nargs=1 and args[1]=kGuessesR then
print(`kGuessesR(s,k,r): the set of permutations guessed in exactly k guesses by strategy s and which have a correct entry in exactly r guesses `):
print(`inputs: strategy s, number of guesses k for game to finish, and number of guesses r before something is correct `):
print(`outputs: set of permutations which have something correct after r guesses and are guessed completely in k guesses by strategy s `):
print(`example: kGuesses(KS(4),3,2)`):

elif nargs=1 and args[1]=howLong then
print(`howLong(setP,s): how many guesses until at least one index is correct?`):
print(`inputs: permutation setP which we are trying to guess, strategy s`):
print(`outputs: number of guesses before at least one index is correct in our guess according to strategy S` ):
print(`example: howLong([1,2,3],KS(3)) or howLong([2,3,1], KS(3))`):


## HELPERS HELP

elif nargs=1 and args[1]=permInd then
print(`permInd(setP, p): compares permutations to check at which indices they agree`):
print(`inputs: fixed permutation setP, guessed permutation p`):
print(`outputs: a list [L1,L2] where L1 is the list of indices where setP and p agree`):
print(`and L2 is the list of indices where setP and p disagree.`):

elif nargs=1 and args[1]=permChecker then
print(`permChecker(p1,p2): checks that two permutations p1 and p2 have same length and are both valid permutations`):
print(`inputs: permutations p1 and p2`):
print(`outputs: if triggered, FAIL returned`):


## ERROR CHECKERS

elif nargs=1 and args[1]=stratChecker then
print(`stratChecker(p,s): checks that strategy list has same length as permutation length,`):
print(`and that each list entry is a permutation of the proper length`):
print(`inputs: permutation p and strategy (list) s`):
print(`outputs: if triggered, FAIL returned`):

elif nargs=1 and args[1]=isPerm then
print(`isPerm(p): checks whether a list p is a permutation of {1,...,nops(p)} `):
print(`inputs: list p`):
print(`outputs: boolean (is p a permutation?)`):
print(`example: isPerm(randperm(4)); isPerm([1,2,3,2])`):

elif nargs=1 and args[1]=isDer then
print(`isDer(p): checks whether a permutation is a derangement (i.e. there are no fixed points) `):
print(`inputs: permutation p`):
print(`outputs: boolean (is p a derangement?)`):
print(`example: isDer([1,2,3]), isDer([3,4,1,2])`):

elif nargs=1 and args[1]=isCyc then
print(`isCyc(p): checks whether a permutation is a cyclic permutation `):
print(`inputs: permutation p`):
print(`outputs: boolean (is p cyclic?)`):
print(`example: isCyc([1,2,3,4]), isDer([3,4,2,1])`):

else
print(`no function of name `, args[1], ` exists.`):

fi:

end:




with(combinat):
with(GroupTheory):

##############################################
### GUESSER PROCEDURES AND GUESSER HELPERS ###
##############################################

## GUESSER (GENERAL, WITH INFINITY)
#
# input setP fixed permutation to guess, s strategy
# guesses random permutations, fixing correct entries, until correct
# or until strategy forces an already seen guess
# output is number of turns taken to guess correctly

guesser := proc(setP, s, boolSee := false) local turns,p,P,i:
turns := 1:
p := [seq(i, i=1..nops(setP))]:
P := {p}: # set of already seen guesses

if type(s,list) then 
    stratChecker(setP,s):
fi:

while not p = setP do
    p := nextGuess(setP,p,s,boolSee):

    if boolSee = true then 
        print(p);
    fi:

    if p in P and not s = random then       # note that a random strategy allows us to break out of a guessing "loop"
        turns := infinity:
        p := setP: # causes break out of while loop
    fi:

    P := P union {p}:
    turns ++ :
od:

return turns:
end:


## GUESSER (GENERAL, OLD VERSION)
# NO ALLOWANCE FOR INFINITY/LOOPING CASE
#
# input setP fixed permutation to guess, s strategy
# guesses random permutations, fixing correct entries, until correct
# output is number of turns taken to guess correctly

guesserOld := proc(setP, s, boolSee := false) local turns,p,i:
turns := 1:
p := [seq(i, i=1..nops(setP))]:

if type(s,list) then 
    stratChecker(setP,s):
fi:

while not p = setP do
    p := nextGuess(setP,p,s,boolSee):
    if boolSee = true then 
        print(p);
    fi:
    turns ++ :
od:

return turns:
end:


## GUESSER (GENERAL, WITH INPUT)
#
# input setP fixed permutation to guess, iniP first guessed permutation, s strategy
# guesses random permutations, fixing correct entries, until correct
# output is number of turns taken to guess correctly

guesserInpt := proc(setP, iniP, s, boolSee) local turns,p:
turns := 1:
p := iniP:

if type(s,list) then 
    stratChecker(setP,s):
fi:

while not p = setP do
    p := nextGuess(setP,p,s,boolSee):
    # if boolSee = true then 
    #     print(p);
    # fi:
    turns ++ :
od:

return turns:
end:


## NEXT GUESS (GENERAL)
#
# inputs setP fixed permutation to guess
# inputs current guess p 
# output is the permutation representing the next guess, generated using strategy s

nextGuess := proc(setP,p,s,boolSee := false) local nextP, loc,corrLoc,incorrLoc, i,j, locPerm, n,st:

loc := permInd(setP,p):
corrLoc := loc[1]:
incorrLoc := loc[2]:
nextP := [0$nops(setP)]:

for i from 1 to nops(corrLoc) do
    nextP[corrLoc[i]] := setP[corrLoc[i]]:
od:


## generate next guess using appropriate strategy

if args[3]=random then
    # randomly permute the incorrect entries
    locPerm := randperm(nops(incorrLoc)): 
    
    # make sure the permutation is not trivial, so the next guess will be different from current
    while locperm = permute(nops(setP))[1] do
        locPerm := randperm(nops(incorrLoc)): 
    od:

    for j from 1 to nops(incorrLoc) do
        nextP[incorrLoc[j]] :=  p[incorrLoc[locPerm[j]]]:
    od:

elif args[3]=cyclic then
    for j from 1 to nops(incorrLoc)-1 do
        nextP[incorrLoc[j+1]] :=  p[incorrLoc[j]]:
    od:
    nextP[incorrLoc[1]] := p[incorrLoc[nops(incorrLoc)]]:

elif type(args[3],list) then 

    if type(args[3][1],list) then   # strategy consists of a list of lists, i.e. a general strategy
        locPerm := s[nops(incorrLoc)]:
        for j from 1 to nops(incorrLoc) do
            nextP[incorrLoc[locPerm[j]]] :=  p[incorrLoc[j]]:
        od:
    
    else    # strategy consists of only a permutation
        if nops(incorrLoc)<>nops(args[3]) then 
            error `Strategy is a single permutation with length not equal to number of incorrect entries. Check length of strategy, or that starting guess is a derangement.`
        fi: 

        st := args[3]:
        for j from 1 to nops(incorrLoc) do
            nextP[incorrLoc[j]] :=  p[incorrLoc[st[j]]]:
        od:
    fi:

else 
    error `No such strategy exists.`:
fi:

# if boolSee = true then 
#     print(`Incorrect Locations:`, incorrLoc):
# fi:

return nextP:
end:




## PERMUTATION INDEX CLASSIFICATION
#
# inputs setP fixed permutation to guess
# inputs p the current guessed permutation
# outputs lists of indices where entries agree, and also disagree

permInd := proc(setP, p) local corrLoc, incorrLoc, i:
permChecker(setP,p):

corrLoc:=[]:
incorrLoc:=[]:

for i from 1 to nops(setP) do
    if setP[i] = p[i] then
        corrLoc := [op(corrLoc), i]:
    else 
        incorrLoc := [op(incorrLoc), i]:
    fi:
od:

[corrLoc, incorrLoc]:
end:



## PERMUTATION COMPARE ERROR CHECKER
#
# inputs two permutations
# checks if both are same length and valid permutations

permChecker := proc(p1, p2) local n:

if not nops(p1) = nops(p2) then 
    error `input permutations have differing lengths.`:
fi:

n := nops(p1):

# if (not p1 in permute(n)) or (not p2 in permute(n)) then 
if (not isPerm(p1)) or (not isPerm(p2)) then 
    error `at least one of input permutations not a true permutation`:
fi:

end:


## PERMUTATION TYPE CHECKER
# 
# inputs list
# checks if list is a permutation on {1,..,nops(p)}

isPerm := proc(p) local n,i:
n := nops(p):

for i from 1 to n do
    if not member(i,p) then
        false:
    fi:
od:

true:
end:


##################################################
### STRATEGY GENERATING PROCEDURES AND HELPERS ###
##################################################

## STRATEGY ERROR CHECKER
# 
# inputs a potential strategy
# checks that it is a valid strategy
# i.e. s is a list of length n each with a permutation of length equal to position in list

stratChecker := proc(p,s) local i:

if not nops(p) = nops(s) then 
    error `strategy length is not equal to length of permutation`:
fi:

for i from 1 to nops(s) do
    if not nops(s[i])=i then 
        error `strategy component has improper length. Error at index`, i:
    fi:
od:

end:


## CYCLIC PERMUTATION GENERATOR - USING GROUP THEORY PACKAGE
# note: this method is much faster for n >= 6
cyclicPermsGT := proc(n) local p,P,C:
C := {}:
P := permute(n):

for p in P do
    if PermCycleType(Perm(p)) = [n] then 
        C := C union {p}:
    fi:
od:

if n = 1 then 
    C := {[1]}:
fi:

C:
end:


## CYCLIC PERMUTATION GENERATOR - ORIGINAL CODE
cyclicPerms := proc(n) local c,C,p,P,i:

# generate cycles representing all cyclic permutations
C := {}:    # set of cycles

for p in permute([seq(2..n)]) do
    C := C union {[1,op(p)]}:   
od:

# turn them into permutations again
P := {}:    # set of permutations

for c in C do
    p := [0$n]:
    for i from 2 to n do
        p[c[i]] := c[i-1]:   # transform each cycle into a permutation
    od:
    p[c[1]] := c[n]:    # "loop around" case in the cycle, i.e. send last entry to first position

    P := {op(P), p}:
od:

P:
end:


## DERANGEMENTS GENERATOR
# 
# inputs permutation length n
# outputs collection (set) of permutations which are derangements on [n]
# i.e. there are no fixed points 

derange := proc(n) local p,P:
P := {}:     # set of derangements

p := firstperm(n):
while not p = FAIL do
    if isDer(p) then 
        P := P union {p}:
    fi:

    p := nextperm(p):
od:

P:
end:


## DERANGEMENT CHECKER
# 
# inputs permutation 
# outputs boolean for if permutation is a derangement 

isDer := proc(p) local n,i:
n := nops(p):

for i from 1 to n do 
    if p[i] = i then 
        return false:
    fi:
od:

true:
end:


## CYCLIC CHECKER
# 
# inputs permutation 
# outputs boolean for if permutation is a derangement 
# requires GroupTheory package

isCyc := proc(p) 
evalb(PermCycleType(Perm(p)) = [nops(p)]):
end:


## CYCLIC STRATEGY COLLECTION GENERATOR
# 
# inputs length n 
# outputs a collection (set) of all strategies (lists) consisting of cyclic permutations

cyclicStrats := proc(n) local c,C,CC,p,P,s:
if n=1 then 
    RETURN({[[1]]}):
fi:

# recursion:
C := cyclicStrats(n-1):
CC := {}:

P := cyclicPermsGT(n):
for c in C do 
    for p in P do 
        s := [op(c),p]:
        CC := CC union {s}:
    od:
od:

CC:
end:


## DERANGEMENT STRATEGY COLLECTION GENERATOR
# 
# inputs length n 
# outputs a collection (set) of all strategies (lists) consisting of permutations which are derangements

derangeStrats := proc(n) local c,C,CC,p,P,s:
if n=1 then 
    RETURN({[[1]]}):    # needed for completeness, doesn't make sense as a derangement
fi:

# recursion:
C := derangeStrats(n-1):
CC := {}:

P := derange(n):
for c in C do 
    for p in P do 
        s := [op(c),p]:
        CC := CC union {s}:
    od:
od:

CC:
end:


## NEXT PERMUTATION (TYPED)
# 
# inputs permutation
# outputs the next permutation with a certain type
# e.g. the next cyclic permutation
# like nextperm, returns FAIL after exhausting list

nextPermTyped := proc(p, type) local n, pp:
if p = FAIL then
    error `Permutation is FAIL.`:
fi:

n := nops(p):
pp := nextperm(p):

if type = cyclic then 
    while not pp = FAIL and not isCyc(pp) do
        pp := nextperm(pp):
    od:

elif type = der then 
    while not pp = FAIL and not isDer(pp) do
        pp := nextperm(pp):
    od:

else 
    error `Permutation type not valid. Try cyclic or der instead. Permutation type given was`, type:
fi:

return pp:
end:


## NEXT STRATEGY
# 
# inputs strategy of length n with type either cyclic or derangement
# outputs next strategy of that type 

nextStrat := proc(s, type) local n,i,j,p,t:
n := nops(s):

# i is the index of the strategy's permutation which is shifted
# note that i is taken from the end of the strategy and walks back
# start by trying to shift last entry
p := nextPermTyped(s[-1],type):
i := n:

# handle reaching "end" of a "next loop"
while p = FAIL and i > 1 do
    i := i-1:
    p := nextPermTyped(s[i], type):
od:

if i = 1 then 
    return FAIL:    # no next strategy exists!
fi:

# build next strat according to type
t := [op(s[1..i-1]), p, seq(nextPermTyped( [seq(1..j)] ,type),j=i+1..n)]:

t:
end:


###############################################
### STRATEGY COLLECTION ANALYSIS PROCEDURES ###
###############################################

## RANK STRATEGIES
# 
# inputs permutation length n and strategy set setS
# outputs list of strategies in setS which have the lowest average number of guesses
# computed from the generating function

rankStrats := proc(n, setS) local L,A,a,s,i,j:

A:= []: # running list of averages
L:= []: # entry l in L is of the form [avg, {set of strategies with that avg}]

for s in setS do
    a := gfAvg(n,s);

    if not a in A then
        A := sort([op(A),a]);
        member(a,A,'i'):
        L:= [seq(L[j], j=1..i-1), [a,{s}], seq(L[j], j=i..nops(A)-1)]:

    elif a in A then
        member(a,A,'i'):
        L[i][2] := L[i][2] union {s}:

    fi:

od:


L:
end:


## BEST STRATEGIES
# 
# inputs permutation length n and strategy set setS
# outputs list of strategies in setS which have the lowest average number of guesses
# computed from the generating function
# separate from rankStrats(n, setS) since this is faster -- doesn't order ALL (n-1)! strategies

bestStrats := proc(n, setS) local L,s,m,M:
# initialize using trivial strategy
L := []:
m := gfAvg(n,setS[1]):

# check all other strategies
for s in setS do
    M := gfAvg(n,s):

    if M = m then 
        L := [op(L), s]:

    elif M < m then 
        m := M:
        L := [s]:
    fi:
od:

L:
end:


## WORST STRATEGIES
# 
# inputs permutation length n and strategy set setS
# outputs list of strategies in setS which have the highest average number of guesses
# computed from the generating function
# separate from rankStrats(n,setS) since this is faster -- doesn't order ALL (n-1)! strategies

worstStrats := proc(n, setS) local L,s,m,M:
# initialize 
L := []:
m := gfAvg(n,setS[1]):

# check all other strategies
for s in setS do
    M := gfAvg(n,s):

    if M = m then 
        L := [op(L), s]:

    elif M > m then 
        m := M:
        L := [s]:
    fi:
od:

L:
end:


## BEST STRATEGIES - INDUCTIVELY
# 
# input length n
# output is set of strategies on [n] which are optimal for n-1 and smaller

inductiveStrat := proc(n) local S,SInd,s,ss,p:
S := {}:
SInd := bestStrats(n-1, cyclicStrats(n-1)):   # can hard code Kutin-Smithline to save computation time

for s in SInd do 
    for p in cyclicPermsGT(n) do
        ss := [op(s),p]:
        S := S union {ss}:
    od:
od:

S:

end:


## RANK STRATEGIES ITERATIVELY
# USES LESS MEMORY THAN rankStrats, BUT USES MORE COMPUTATION TIME
# NOTE ALSO ONLY WORKS FOR STRATEGIES OF A CERTAIN TYPE FROM A LARGE COLLECTION
# WILL NOT WORK ON GENERAL SUBSETS, UNLIKE OLD PROC
# 
# inputs permutation length n and strategy type
# outputs list of strategies with that characteristic which have the lowest average number of guesses
# computed from the generating function

rankStratsIt := proc(n, type) local L,A,a,s,i,j,m:

A:= []: # running list of averages
L:= []: # entry l in L is of the form [avg, {set of strategies with that avg}]

# initialize first strategy of a given type
s := [ [1], [2,1], seq( nextPermTyped([seq(1..m)],type), m=3..n ) ]:

while not s = FAIL do
    a := gfAvg(n,s);

    if not a in A then
        A := sort([op(A),a]);
        member(a,A,'i'):
        L:= [seq(L[j], j=1..i-1), [a,{s}], seq(L[j], j=i..nops(A)-1)]:

    elif a in A then
        member(a,A,'i'):
        L[i][2] := L[i][2] union {s}:

    fi:

    s := nextStrat(s,type):
od:

L:
end:


## BEST STRATEGIES - ITERATIVELY
# SAME LIMITATIONS AS ITERATIVE RANKING
# 
# inputs permutation length n and strategy type
# outputs list of strategies with that characteristic which have the lowest average number of guesses
# computed from the generating function
# separate from rankStratsIt(n, type) since this is faster -- doesn't order ALL (n-1)! strategies

bestStratsIt := proc(n, type) local L,s,m,M:
L := []:

# initialize first strategy of a given type
s := [ [1], [2,1], seq( nextPermTyped([seq(1..m)],type), m=3..n ) ]:
m := gfAvg(n,s):

# check all other strategies
while not s = FAIL do
    M := gfAvg(n,s):

    if M = m then 
        L := [op(L), s]:

    elif M < m then 
        m := M:
        L := [s]:
    fi:

    s := nextStrat(s,type):
od:

L:
end:



###########################################
### SINGLE STRATEGY ANALYSIS PROCEDURES ###
###########################################


## GENERATING FUNCTION 
# 
# inputs permutation length n, strategy s, variable var
# outputs the polynomial representing the generating function of strategy s in terms of variable x
# i.e. the coefficient a_d is the number of permutations in [n] which take d turns to guess using strategy s
# sanity check: gf evaluated at x=1 should yield n! (total number of permutations of [n])

gf := proc(n,s,var := x) local P,p: 
# Sn := permute(n): 
# add(var^guesser(p,s), p in Sn):
P := 0: # polynomial

p := firstperm(n):
while not p = FAIL do
    P := P + var^guesser(p,s):
    p := nextperm(p):

od:

P:
end:


## GEN FUNC TO AVERAGE
# 
# inputs length of permutation n and generating function polynomial for a strategy
# outputs the average number of guesses for that strategy

gfAvg := proc(n,s) local p,d,i,A: 
p := gf(n,s,x):
d := degree(p,x):   # note that infinite degree is not a polynomial, so causes d := FAIL

if d = FAIL then 
    A := infinity:
else 
    A := add(i*coeff(p,x,i), i=1..d)/n!:
fi: 

A:
end:


###########################################
### KUTIN-SMITHLINE STRATEGY PROCEDURES ###
###########################################


## KUTIN-SMITHLINE STRATEGY
#
# inputs length n 
# outputs kutin-smithline strategy as a list of lists (permutations) up to length n
# [[1], [2,1], [2,3,1],...]

KS := proc(n) local S,i,j:
S := []:

for i from 1 to n do
    S := [op(S), [seq(j, j=2..i),1]]:
od:

S:
end:


## INDUCTIVE KUTIN-SMITHLINE STRATEGY
#
# input strategy length n
# output KS strategy for strategy components 1..n-1, but whose nth component is permutation p

KSInd := proc(n,p) local i:
if nops(p)<>n then 
    error `length of p must be equal to n`:
fi:

[op(KS(n - 1)), p] :
end:


## INDUCTIVE KUTIN-SMITHLINE STRATEGY - LEFT SHIFT AT END
#
# input strategy length n
# output right shift for strategy components 1..n-1, left shift for component n 

KSL := proc(n) :
[op(KS(n - 1)), [n,seq(1..n-1)]] :
end:



###############################################
### EXCEDANCE AND INDEX ANALYSIS PROCEDURES ###
###############################################

## EXCEDANCES SET 
# 
# inputs permutation p 
# outputs set of excedances (values i in [n] where p(i) > i)
# is i mapped to an index smaller than itself, aka is j in p larger than its index

Exc := proc(p) local i,j,E:
E := {}:

for j from 1 to nops(p) do 
    if p[j] > j then 
        E := E union {p[j]}:
    fi:
od:

E:
end:


## EXCEDANCE FUNCTION
# 
# inputs permutation length n
# outputs function of form a_k t^k where k is the number of excedances 
# and a_k is the number of derangements of [n] with k excedances

excFunc := proc(n) local p,P:
P := derange(n):  # set of all derangements of [n]
add(t^nops(Exc(p)), p in P):
end:


## PERMUTATIONS WITH K EXCEDANCES
#
# inputs permutation length n and number of excendances k (1 <= k <= n)
# outputs set of permutations of length n with k excedances
# remark: the number of such permutations should be A(n,k)

kExcPerms := proc(n,k) local p,P,Q:
P := permute(n):
Q := {}:

for p in P do 
    if nops(Exc(p)) = k then 
        Q := Q union {p}:
    fi:
od:

Q:
end:


## (INDUCTIVE) INDEX ANALYSIS
# 
# input permutation corresponding to S[n] (strategy component of length n)
# output set of derangements on [n] which result in at least one correct entry after generating new guess 
# note that we use derangements to ensure that the first guess (trivial perm) has no correct entries

indexAnalysis := proc(s) local n,P,p,pp,H,corrLoc:
n := nops(s):
P := derange(n):    # ensures that trivial guess will have no locked positions
H := {}:

for p in P do   # note each derangement will act as the set permutation to guess, i.e. first argument of guesser procs
    pp := nextGuess(p,[seq(1..n)],s):

    corrLoc := permInd(p,pp)[1]:
    # incorrLoc := permInd(p,pp)[2]:

    if nops(corrLoc) > 0 then 
        H := H union {p}:
    fi:
od:

H:
end:


## INDEX AVERAGE
# same idea as indexAnalysis, but averages the number of correct positions 
# so output is a number quantifying performance, not a set of permutations
#
# input permutation corresponding to S[n] (strategy component of length n)
# output average number of correct entries after one guess for each derangement of [n]
# note that we use derangements to ensure that the first guess (trivial perm) has no correct entries

indexAverage := proc(s) local n,P,p,pp,total,corrLoc:
n := nops(s):
P := derange(n):    # ensures that trivial guess will have no locked positions
total := 0:

for p in P do   # note each derangement will act as the set permutation to guess, i.e. first argument of guesser procs
    pp := nextGuess(p,[seq(1..n)],s):

    corrLoc := permInd(p,pp)[1]:
    # incorrLoc := permInd(p,pp)[2]:

    total := total + nops(corrLoc):
od:

total/nops(P):
end:


## MOST CORRECT ENTRIES
#
# inputs set of strategy components S[n] (all of same length)
# outputs list of strategies with the best performance in indexAnalysis(s)
# i.e. the strategies that result in correct indices the most frequently for permutations in der(n)

mostCorrect := proc(S) local L,m,M,s,n:
if not isPerm(S[1]) then 
    error `Input of incorrect form. Procedure requires a permutation of length n (corresponding to S[n] for strategy S.) `
fi:

# initialize using trivial strategy
L := []:
m := nops(indexAnalysis(S[1])):
n := nops(S[1]):

# check all other strategies' S[n] permutations
for s in S do
    # error checking
    if not isPerm(s) then 
        error `Input of incorrect form. Procedure requires a permutation of length n (corresponding to S[n] for strategy S.)`
    elif nops(s)<>n then 
        error `Input permutations not all of same length.`
    fi:

    M := nops(indexAnalysis(s)):

    if M = m then 
        L := [op(L), s]:

    elif M < m then 
        m := M:
        L := [s]:
    fi:
od:

L:
end:


## INDEX ANALYSIS (K TRIALS)
# 
# input permutation corresponding to S[n] (strategy component of length n) and number of trials K
# output set of derangements on [n] which result zero correct entries after generating new guess K times according to S[n]
# note that we use derangements to ensure that the first guess (trivial perm) has no correct entries

indexAnalysisK := proc(s,K) local n,P,p,pp,H,corrLoc,i:
n := nops(s):
P := derange(n):    # ensures that trivial guess will have no locked positions
H := {}:

for p in P do   # note each derangement will act as the set permutation to guess, i.e. first argument of guesser procs
    pp := nextGuess(p,[seq(1..n)],s):
    i := 1:
    corrLoc := permInd(p,pp)[1]:

    while i < K and nops(corrLoc)=0 do 
        pp := nextGuess(p,pp,s):
        corrLoc := permInd(p,pp)[1]:
        i++:
    od:
    
    if nops(corrLoc) = 0 then 
        H := H union {p}:
    fi:
od:

H:
end:


## EXCEDANCE FUNCTION (INDEX VERSION)
# 
# inputs a permutation s of length n corresponding to S[n] for some strategy and analysis type 
# for incorrectLoc analysis, also input an optional parameter K for indexAnalysisK 
# using indexAnalysis or indexAnalysisK (based upon analysis type), 
# creates generating function using the excedances of derangements 
# which had at least one correct entry after one iteration of guesser using s := S[n]

excFunc2 := proc(s,type,var:=t,K:=1) local H,p:
if type = correct then 
    H := indexAnalysis(s):
elif type = incorrect then 
    H := indexAnalysisK(s,K):
else
    error `Input analysis type not recognized. Try correct or incorrect.`
fi:

add(var^nops(Exc(p)), p in H):
end: 




####################################
### NUMBER OF GUESSES PROCEDURES ###
####################################


## PERMS IN K GUESSES
#
# inputs strategy S and a number of guesses k 
# outputs the set of permutations which are guessed in exactly k guesses by S

kGuesses := proc(s,k) local n,P,p:
n := nops(s):
P := {}:

for p in permute(n) do 
    if guesser(p,s,false) = k then 
        P := P union {p}:
    fi:
od:

P:
end:



### HOW LONG BEFORE CORRECT INDEX 
# 
# inputs permutation p and strategy s
# outputs the number of guesses before set of correct entries is nonempty 

howLong := proc(setP,s) local r,p:
r := 1: 
p := [seq(1..nops(setP))]:     # first guess is trivial permutation 

while permInd(setP,p)[1]=[] do 
    p := nextGuess(setP,p,s):
    r++:
od:

r:
end:


### HOW LONG IF K GUESSES
# 
# inputs strategy s, num guesses k for game to finish, num guesses r before something correct 
# outputs set of permutations which have something correct after r guesses and are guessed completely in k guesses by strategy s 

kGuessesR := proc(s,k,r) local T,t: 
T := {}:
for t in kGuesses(s,k) do 
    if howLong(t,s)=r then 
        T := T union {t}:
    fi:
od:

T:
end:




##############################
### PAPER THEOREM CHECKERS ###
##############################

# each of the following procedures verifies (experimentally) the specified theorem from Hiveley (2025)

HelpThm:=proc(): 

if nargs=0 then 

print(`ALL VERIFICATION FUNCTIONS:`):
print(`prop31(n), thm41(n), conj42(n), thm43(n), thm44(n), thm46(n), thm47(n), thm48(n), thm410(n), thm411(n)`):

## GUESSERS HELP

elif nargs=1 and args[1]=prop31 then
print(`prop31(n): verifies Proposition 3.1`):
print(`inputs: n`):
print(`outputs: set containing, for all derangement strategies, the average number of correct indices across all permutations of length n`):
print(`example: prop31(5) `):


elif nargs=1 and args[1]=thm41 then
print(`thm41(n): verifies Theorem 4.1`):
print(`inputs: n`):
print(`outputs: a two element list [S1,S2] where S1 is the set of all linear coefficients for the generating functions`):
print(`of strategies of length n, and S2 is the same for quadratic coefficients.`):
print(`example: thm41(4) `):


elif nargs=1 and args[1]=conj42 then
print(`conj42(n): verifies Conjecture 4.2`):
print(`inputs: n`):
print(`outputs: set of {[x^3](f_{CS}(x)), [[x^3](f_S(x)) for all cyclic strategies S ]}`):
print(`example: conj42(4) `):


elif nargs=1 and args[1]=thm43 then
print(`thm43(n): verifies Theorem 4.3`):
print(`inputs: n`):
print(`outputs: set of {[x^3](f_{CS}(x)), [[x^3](f_S(x)) for all inductive strategies S ]}`):
print(`example: thm43(5) `):


elif nargs=1 and args[1]=thm44 then
print(`thm44(n): verifies Theorem 4.4`):
print(`inputs: n`):
print(`outputs: [1 - 2^(n+1) + 3^n + n^2/2 + (5/2)*n - n*2^n, S] where S is the set containing, for all inductive strategies S,`):
print(`the number of permutations guessed in exactly 3 guesses such that the first correct entry is obtained on guess 1.`):
print(`example: thm44(5) `):


elif nargs=1 and args[1]=thm46 then
print(`thm46(n): verifies Theorem 4.6`):
print(`inputs: n`):
print(`outputs: set containing the counts of permutations guessed in exactly 3 guesses`):
print(`whose first correct entry is obtained on guess 3 across all cyclic strategies of length n. `):
print(`example: thm46(5) `):


elif nargs=1 and args[1]=thm47 then
print(`thm47(n): verifies Theorem 4.7`):
print(`inputs: n`):
print(`outputs: boolean for whether |{pi : rho_CS (pi) = 2}| = 2^n - 2*n - 2`):
print(`example: thm47(4) `):


elif nargs=1 and args[1]=thm48 then
print(`thm48(n): verifies Theorem 4.8`):
print(`inputs: n`):
print(`outputs: set {m,L} where L is the list containing, for all inductive strategies S,`): 
print(`the number of permutations guessed in exactly 3 guesses such that the first correct entry is obtained on guess 2, `):
print(`and m is the same for KS, specifically.`):
print(`example: thm48(4) `):


elif nargs=1 and args[1]=thm410 then
print(`thm410(n): verifies Theorem 4.10`):
print(`inputs: n`):
print(`outputs: boolean for whether |{pi : rho_CSL (pi) = 2}| = L_n - n - 1`):
print(`example: thm410(5) `):



elif nargs=1 and args[1]=thm411 then
print(`thm411(n): verifies Theorem 4.11`):
print(`inputs: n`):
print(`outputs: set of {[x^3](f_{CSL}(x)), [[x^3](f_S(x)) for all inductive strategies S ]}`):
print(`example: thm43(5) `):


else
print(`no function of name `, args[1], ` exists.`):

fi:

end:



###############################
### VERIFICATION PROCEDURES ###
###############################


# verification of Proposition 3.1 for input n 
# expected output is a singleton set (since all strategies have the same performance)
# containing the element (n+1)/n

prop31 := proc(n) local D,d:
D := derangeStrats(n):
{seq(indexAverage(d),d in D)};
end:



# verification of Theorem 4.1 for input n 
# output is a two element list [S1,S2] where S1 is the set of all linear coefficients for the generating functions 
# of deranged strategies of length n, and S2 is the same for quadratic coefficients.
# we expect S1 and S2 to each be singleton sets, where S1 = {1} and S2 = {A(n,1)} which can be calculated using eulerian1(n,1)

thm41 := proc(n) local D,d,S,p:
D := derangeStrats(n):
S := [{},{}]:   # initialize set of C1 and C2 coefficients

for d in D do 
    p := gf(n,d,x):

    # handle infinite looping case, the old fashioned way 
    if degree(p,x) = FAIL then 
        p := p - coeff(p,x^infinity)*x^infinity:
    fi:

    S[1] := S[1] union {coeff(p,x,1)}:
    S[2] := S[2] union {coeff(p,x,2)}:
od:

S:
end:



# (experimental) verification of Conjecture 4.2 for input n
# output is a list [m,C] where m = [x^3](f_CS(x)) 
# and C is the set of all cubic coefficients for the generating functions of deranged strategies of length n 
# we expect C to be a set of elements all smaller than m 

conj42 := proc(n) local D,d,m,p,C,i:
D := derangeStrats(n) minus {KS(n), [seq(  [i, seq(1..i-1)], i=1..n )]}:    # non-KS strategies:
m := coeff(gf(n,KS(n),x),x,3):
C := {}:   # initialize set of C3 coefficients

for d in D do 
    p := gf(n,d,x):

    # handle infinite looping case, the old fashioned way 
    if degree(p,x) = FAIL then 
        p := p - coeff(p,x^infinity)*x^infinity:
    fi:

    C := C union {coeff(p,x,3)}:
od:

[m,C]:
end:



# verification of Theorem 4.3 for input n 
# output is a set of {[x^3](f_{CS}(x)), [[x^3](f_S(x)) for all inductive strategies S ]}
# expecting the set {m, [list of numbers smaller than m]}

thm43 := proc(n) local C,c,m,i:
C := cyclicPerms(n) minus {[seq(2..n),1]}:   
m := coeff(gf(n,KS(n),x),x,3):

{m, [seq( coeff(gf(n,KSInd(n,c),x),x,3) , c in C)]}:
end:



# verification of Theorem 4.4 for input n 
# output is list of [1 - 2^(n+1) + 3^n + n^2/2 + (5/2)*n - n*2^n, S]
# where S is the set containing, for all inductive strategies S, 
# the number of permutations guessed in exactly 3 guesses such that the first correct entry is obtained on guess 1.
# expecting the list [m,{m}] where m = 1 - 2^(n+1) + 3^n + n^2/2 + (5/2)*n - n*2^n

thm44 := proc(n) local C,c,m:
C := cyclicPermsGT(n):
m := 1 - 2^(n+1) + 3^n + n^2/2 + (5/2)*n - n*2^n:
[m, {seq( nops(kGuessesR(KSInd(n,c),3,1)), c in C)}];
end:



# verification of Theorem 4.6 for input n 
# output is the set containing the counts of permutations guessed in exactly 3 guesses whose first correct entry 
# is obtained on guess 3 across all cyclic strategies of length n. 
# expecting the set {1}

thm46 := proc(n) local C,c:
C := cyclicStrats(n):
{seq(nops(kGuessesR(c,3,3)), c in C)}:
end:



# verification of Theorem 4.7 for input n 
# expecting a boolean "true"

thm47 := proc(n) :
evalb(nops(kGuessesR(KS(n),3,2)) = 2^n - 2*n - 2);
end:



# verification of Theorem 4.8 for input n 
# output is set of {m, L} where L is the list containing, for all inductive strategies S, 
# the number of permutations guessed in exactly 3 guesses such that the first correct entry is obtained on guess 2, 
# and m is the same for KS, specifically. 
# expecting m > l for all l in L

thm48 := proc(n) local C,c,m,i:
C := cyclicStrats(n) minus {KS(n),[seq(  [i, seq(1..i-1)], i=1..n )]}:    # non-KS cyclic strategies
m := nops(kGuessesR(KS(n),3,2)):
{m,[seq( nops(kGuessesR(c,3,2)) , c in C)]}:
end:



# verification of Theorem 4.10 for input n 
# expecting a boolean "true"

thm410 := proc(n) local Ln:
Ln := fibonacci(n-1) + fibonacci(n+1): # nth Lucas number
evalb(nops(kGuessesR(KSL(n),3,2)) = Ln - n - 1);
end:



# verification of Theorem 4.11
# output is a set of {[x^3](f_{CSL}(x)), [[x^3](f_S(x)) for all cyclic strategies S ]}
# note that we removed both left and right shifting strategies from the comparison set, for obvious reasons. 
# and furthermore this verification is trivial for n <= 3 since the only strategies of those lengths *are* cyclic shift.
# expecting the set {m, [list of numbers larger than m]}

thm411 := proc(n) local C,c,m,i:
C := cyclicStrats(n) minus {KSL(n), [seq(  [i, seq(1..i-1)], i=1..n-1 ), [seq(2..n),1]]}:    # non-KSL cyclic strategies
m := coeff(gf(n,KSL(n),x),x,3):

{m, [seq( coeff(gf(n,c,x),x,3) , c in C)]}:
end: