#Dr. Yuxuan Yang's brilliant implentation of  Sasa Radomirovic's construction in his paper:
#"A Construction of Short Sequences Containing All Permutations of a Set as Subsequences"
#Elec. J. Combin. 19(4) (2012) #P31
#https://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i4p31/pdf
#As promised I am donating $100 in memory of Jerrold Tunnell, credited to Dr. Yuxuan Yang
#4
#The main theorem of Sasa has a typo, sigma_i should be (3-i,4-i,...n+1-i) instead of (3-i,4-i,...n+2-i), 
#which gave me a hard time when debugging 

#Completeseq(m) implements the clever construction of Jerrold Tunnell's brilliant academic son Sasa Radomirovic
#and outputs the complete sequence with all permuations of [0,1,2,...,m-1] as a subsequence.
#Completeseq(13) will give the Example 9 in the paper.
Completeseq:=proc(m) local n,sig,i,j,k,x,y,med,tau,tau1,tau2,k0:
if m<7 then 
print(`m needs to be at least 7.`):
RETURN(FAIL):
fi:
n:=3*ceil((m-1)/3)-1:
sig:=[[seq(0..n-1)],[seq(0..n-1)],seq([seq(j-i mod n,j=3..n+1)],i=3..n-1),[seq(3..n-1),0,1,2],[seq(3..n-1),0,1,2]]:
x:=n:
y:=n+1:
med:=[seq(
op([   op(ins(sig[3*j-2],n-1,y)),   x,   op(sig[3*j-1]),   x,   op(ins(sig[3*j],2,y)),   x])
,j=2..(n+1)/3-1)]:
tau:=[x,op(sig[1]),y,x,op(sig[2]),x,y,op(sig[3]),x,op(med),op(sig[n-1]),y,x,op(sig[n]),x,y,op(sig[n+1]),x]:
#main theorem case (m=3k+1)
if m mod 3=1 then RETURN(tau): fi:
#one less element case (m=3k)
tau1:=[]:k0:=1:
for k from nops(tau) by -1 to 1 do
if tau[k]>n-1 then
 tau1:=[tau[k]-1,op(tau1)]:
elif tau[k]<n-1 then 
 tau1:=[tau[k],op(tau1)]:
else
 k0:=k:
fi:
od:
tau1:=[op(k0..-1,tau1)]:
if m mod 3=0 then RETURN(tau1): fi:
#two less elements case (m=3k-1)
tau2:=[]:k0:=1:
for k from nops(tau1) by -1 to 1 do
if tau1[k]>n-2 then
 tau2:=[tau1[k]-1,op(tau2)]:
elif tau1[k]<n-2 then 
 tau2:=[tau1[k],op(tau2)]:
else
 k0:=k:
fi:
od:
tau2:=[op(k0..-1,tau2)]:
if m mod 3=2 then RETURN(tau2): fi:
end:
#ins(sq,k,n):input a sequence sq, a position k and a number n, output the sequence obtained by inserting n to the position k
#of the sequence sq. e.g. ins([1,3,5],2,6)=[1,6,3,5]:
ins:=proc(sq,k,n) local i: [op(1..k-1,sq),n,op(k..nops(sq),sq)]:end:

#http://oeis.org/A062714 has more information

#Checkcomplete(sq,m):This is n! algorithm!!! Check sq is a complete sequence with all permuations of [0,1,2,...,m-1] as a subsequence
Checkcomplete:=proc(sq,m) local i,per:
for per in permute([seq(0..m-1)]) do
if not Checkperm(sq,per) then
RETURN(false):
fi:
od:
true:
end:
#Checkperm(sq,per):Check sq has per as a subsequence
Checkperm:=proc(sq,per) local i,j:
j:=1:
for i from 1 to nops(sq) do
 if sq[i]=per[j] then
  j:=j+1:
 fi:
 if j>nops(per) then
  RETURN(true):
 fi:
od:
false:
end: