#OK to post homework 
#Natalya Ter-Saakov, March 27, Assignment 16
read "C16.txt":

with(combinat):

#Problem 2
#IsCondorcet(P): inputs a voting profile P with v:=nops(P) voters and n:=nops(P[1]) candidates, and outputs true iff you have an instance of the Condorcet paradox. 
IsCondorcet:=proc(P) local i,S:
S:=SV(Tour(P)):
if S in permute({seq(i,i=0..nops(P[1])-1)}) then return(false): 
fi:
return(true):
end:

#Problem 3
#ExactCond(n,v): inputs positive integres n and v and outputs the EXACT ratio of voting profiles that are Condorcet.
ExactCond:=proc(n,v) local co,P:
co:=0:
for P in RP(n,v) do
	if IsCondorcet(P) then co+=1: fi:
od:
co/((n!)^v):
end:

#Problem 4
#EstCond(n,v,K): inputs a large positive integer K, and integers n and v , and generates K random voting profiles with v voters and n candidates, and oututs the ratio (in floating points) of those that happen to be Condorcet.
EstCond:=proc(n,v,K) local i,co, P:
co:=0:
for i from 1 to K do:
	P:=RandP(n,v):
	if IsCondorcet(P) then co+=1: fi:
od:
evalf(co/K):
end:

ExactCond(3,3);
#Output: 1/18
EstCond(3,3,1000);
#0.058
ExactCond(3,4);
#Output: 5/72
EstCond(3,4,1000);
#0.054
ExactCond(3,5);
#Output: 5/72
EstCond(3,5,1000);
#0.054

#Approximate outputs for the following:
EstCond(3,20,10000);
#0.085
EstCond(3,30,10000);
#0.085
EstCond(3,40,10000);
#0.085
EstCond(4,20,10000);
#0.25
EstCond(4,30,10000);
#0.25
EstCond(4,40,10000);
#0.25
EstCond(5,20,10000);
#0.46
EstCond(5,30,10000);
#0.46
EstCond(5,40,10000);
#0.46


#Problem 5
#Borda(P): inputs a voting profile P and outputs the Borda score of the n candidates.
Borda:=proc(P) local i,n,B,ranking:
n:=nops(P[1]):
for i from 1 to n do
	B[i]:=0:
od:
for ranking in P do
	for i from 1 to n do
		B[ranking[i]]+=n-i:
	od:
od:
return([seq(B[i],i=1..n)]):
end:

#Problem 6:
#CondorcetRank(P): inputs a voting profile P and outputs the ranking according to the Condorcet criterion
CondorcetRank:=proc(P) local n, j, S, R, i, r, bigger, added:
n:=nops(P[1]):
S:=SV(Tour(P)):
R:=[{1}]:
for i from 2 to n do
	bigger:=0:
	added:=false:
	for j from 1 to nops(R) do
		if S[i]=S[R[j][1]] then
			R[j]:=R[j] union {i}:
			added:=true:
		elif S[i]<S[R[j][1]] then
			bigger:=j:
		fi:
	od:
	if not added then	
		R:=[seq(R[j],j=1..bigger), {i},seq(R[j],j=bigger+1..nops(R))]:
	fi:
od:
R:
end:

#Problem 7
#BordaRank(P): inputs a voting profile P and outputs the ranking according to the Condorcet criterion.
BordaRank:=proc(P) local n, j, S, R, i, r, bigger, added:
n:=nops(P[1]):
S:=Borda(P):
R:=[{1}]:
for i from 2 to n do
	bigger:=0:
	added:=false:
	for j from 1 to nops(R) do
		if S[i]=S[R[j][1]] then
			R[j]:=R[j] union {i}:
			added:=true:
		elif S[i]<S[R[j][1]] then
			bigger:=j:
		fi:
	od:
	if not added then	
		R:=[seq(R[j],j=1..bigger), {i},seq(R[j],j=bigger+1..nops(R))]:
	fi:
od:
R:
end: