Help15:=proc():print( `  inv(pi), VotesVC(V,C) , RV(V,C) , Cij(BA,i,j), Tour(BA), SV(T),  RankCon(BA) , Borda(BA), RankBor(BA)  ` ): end:

Prob14:=proc(): print(` Pr14a(V,C) , Pr14b(V,C) ,  Pr14c(V,C),  Pr14d1(V,C)  `):end:


Ex1:=proc(): [[1,2,3],[2,3,1],[3,1,2]]:end:

inv:=proc(pi) local n,i,T:
n:=nops(pi):
for i from 1 to n do
 T[pi[i]]:=i:
od:
[seq(T[i],i=1..n)  ]:
end:

with(combinat):


#VotesVC(V,C): all the possible ways that V voters can rank C candiates
VotesVC:=proc(V,C)  local P,S,pi,s:
option remember:

P:=permute(C):

if V=0 then
 RETURN({[]}):
fi:

S:=VotesVC(V-1,C):

{seq(seq([op(s),pi], s in S), pi in P)}:

end:



#RV(V,C): a random vote with V voters and C candidates. Try: RV(3,4);
RV:=proc(V,C) local i:
[seq(randperm(C),i=1..V)]:
end:


#Cij(BA,i,j): Given a ballot BA and two candidates i and j how many voters prefer i to j?
Cij:=proc(BA,i,j) local k1,co,pi:

co:=0:

for k1 from 1 to nops(BA) do
pi:=inv(BA[k1]):
if pi[i]<pi[j] then
  co:=co+1:
fi:
od:

co:

end:


#Tour(BA): Given a ballot BA, with C candidates (C=nops(BA[1])) outputs the tournament in the form of a C by C matrix, the diagonal is 0 and L[i][j]=1 if i beat j otherwise -1. It is a tie it has 0.
Tour:=proc(BA) local C,T,i,j:
C:=nops(BA[1]):

for i from 1 to C do
 T[i,i]:=0:
od:

for i from 1 to C do
 for j from i+1 to C do
 if Cij(BA,i,j)>Cij(BA,j,i) then
  T[i,j]:=1:
  T[j,i]:=-1:
 elif Cij(BA,i,j)=Cij(BA,j,i) then
  T[i,j]:=0:
  T[j,i]:=0:
 else
  T[i,j]:=-1:
  T[j,i]:=1:
fi:
od:
od:

[seq([seq(T[i,j],j=1..C)],i=1..C)]:
end:



#SV(T): The score-vector of the trournament T. Try: BA:=RV(10,10): SV(Tour(BA));
SV:=proc(T) local C,S,i,j:
C:=nops(T):

for i from 1 to C do
S[i]:=0:
od:

for i from 1 to C do
 for j from i+1 to C do
  
 if T[i][j]=1 then
   S[i]:=S[i]+1:
 elif T[i][j]=0 then
  S[i]:=S[i]+1/2:
  S[j]:=S[j]+1/2:
 else
 S[j]:=S[j]+1:
 fi:

od:

od:

[seq(S[i],i=1..C)]:

end:




#RankCon(BA): Given a ballot, a ranking of the candidates
RankCon:=proc(BA) local S,C,S1,i,L,i1,s,R:
C:=nops(BA[1]):

S:=SV(Tour(BA)):

S1:=convert(S,set):

if nops(S1)=C then

R:=inv([seq(C-S[i],i=1..C)]):
R:=[seq({R[i]},i=1..C)]:
   RETURN(R):

fi:

for s in S1 do
L[s]:={}:
od:


for i from 1 to C do
 L[S[i]]:= L[S[i]] union {i}:
od:

S1:=sort(convert(S1,list),`>`):

[seq(L[S1[i1]],i1=1..nops(S1))]:
end:


#BordaS(BA): The Borda Score of the C candidates in the Ballot BA
Borda:=proc(BA) local C,S,i,j,Vec:
C:=nops(BA[1]):

for i from 1 to C do
 S[i]:=0:
od:

for i from 1 to nops(BA) do
 Vec:=BA[i]:
 for j from 1 to C do
 S[Vec[j]]:= S[Vec[j]]+C-j:
 od:
od:

[seq(S[i],i=1..C)]:

end:



#RankBor(BA): Given a ballot, a ranking of the candidates
RankBor:=proc(BA) local S,C,S1,i,L,i1,s:
C:=nops(BA[1]):


S:=Borda(BA):

S1:=convert(S,set):

for s in S1 do
L[s]:={}:
od:


for i from 1 to C do
 L[S[i]]:= L[S[i]] union {i}:
od:

S1:=sort(convert(S1,list),`>`):

[seq(L[S1[i1]],i1=1..nops(S1))]:
end:

##Start Problem 14

Pr14a:=proc(V,C) local gu,co,C1,B1,i:
gu:=VotesVC(V,C):
co:=0:

for i from 1 to nops(gu) do
B1:=RankBor(gu[i]):
C1:=RankCon(gu[i]):
#print(`The Borda rank is`, B1):
#print(`The Condorcet rank is`,C1):

if nops(B1[-1])=1 and B1[-1]=C1[1] then
print(`For the ballot `, gu[i]):
print(``):
print(`The condorcet ranking is`, C1):
print(``):
print(`The Borda ranking is`, B1):
print(``):
co:=co+1:
fi:
od:
print(`There are `, co, `ballots where the least Borda is the top Condorcet `):
co:
end:



Pr14b:=proc(V,C) local gu,co,C1,B1,i:
gu:=VotesVC(V,C):
co:=0:

for i from 1 to nops(gu) do
B1:=RankBor(gu[i]):
C1:=RankCon(gu[i]):
#print(`The Borda rank is`, B1):
#print(`The Condorcet rank is`,C1):

if nops(B1[-1])=1 and member(B1[-1][-1],C1[1]) then
print(`For the ballot `, gu[i]):
print(``):
print(`The condorcet ranking is`, C1):
print(``):
print(`The Borda ranking is`, B1):
print(``):
co:=co+1:
fi:
od:
print(`There are `, co, `ballots where the least Borda is the top cycle of Condorcet `):
co:
end:



Pr14c:=proc(V,C) local gu,co,C1,B1,i:
gu:=VotesVC(V,C):
co:=0:

for i from 1 to nops(gu) do
B1:=RankBor(gu[i]):
C1:=RankCon(gu[i]):
#print(`The Borda rank is`, B1):
#print(`The Condorcet rank is`,C1):

if nops(B1)=4 and nops(B1[3])=1 and member(B1[3][1],C1[1]) then
print(`For the ballot `, gu[i]):
print(``):
print(`The condorcet ranking is`, C1):
print(``):
print(`The Borda ranking is`, B1):
print(``):
co:=co+1:
fi:
od:
print(`There are `, co, `ballots where the sole member who is ranked  third in Borda is the top Condorcet winner `):
co:
end:





Pr14d1:=proc(V,C) local gu,co,C1,B1,i:
gu:=VotesVC(V,C):
co:=0:

for i from 1 to nops(gu) do
B1:=RankBor(gu[i]):
C1:=RankCon(gu[i]):
#print(`The Borda rank is`, B1):
#print(`The Condorcet rank is`,C1):

if nops(C1[1])=1 and B1[1]<>C1[1] then
print(`For the ballot `, gu[i]):
print(``):
print(`The condorcet ranking is`, C1):
print(``):
print(`The Borda ranking is`, B1):
print(``):
co:=co+1:
fi:
od:
print(`There are `, co, `ballots where the top Condorcet  winner is NOT the top Borda winner`):
co:
end:



Pr14d2:=proc(V,C) local gu,co,C1,B1,i:
gu:=VotesVC(V,C):
co:=0:

for i from 1 to nops(gu) do
B1:=RankBor(gu[i]):
C1:=RankCon(gu[i]):
#print(`The Borda rank is`, B1):
#print(`The Condorcet rank is`,C1):

if nops(C1[1])=1 and not member(C1[1][1],B1[1]) then
print(`For the ballot `, gu[i]):
print(``):
print(`The condorcet ranking is`, C1):
print(``):
print(`The Borda ranking is`, B1):
print(``):
co:=co+1:
fi:
od:
print(`There are `, co, `ballots where the top Condorcet  winner is among the top Borda winners`):
co:
end:




Pr14e:=proc(V,C) local gu,co,C1,B1,i:
gu:=VotesVC(V,C):
co:=0:

for i from 1 to nops(gu) do
B1:=RankBor(gu[i]):
C1:=RankCon(gu[i]):
#print(`The Borda rank is`, B1):
#print(`The Condorcet rank is`,C1):

if nops(B1[1])=3 and nops(C1[1])=1 then
print(`For the ballot `, gu[i]):
print(``):
print(`The condorcet ranking is`, C1):
print(``):
print(`The Borda ranking is`, B1):
print(``):
co:=co+1:
fi:
od:
print(`There are `, co, `ballots where there is a three-way tie for top Borda winner and yet there is a Condorcet winner`):
co:
end: