#OK to post
#Homework 16, Rebecca Embar

read `C16.txt`:

#2
IsCondorcet := proc(P) local i:
	not EqualEntries({op(SV(Tour(P)))},{seq(i,i=0..nops(P[1])-1)}):
end:

#3
ExactCond := proc(n,v) local ListP,co,P:
	ListP := RP(n,v):
	co := 0:
	for P in ListP do
		if IsCondorcet(P) then
			co := co+1:
		fi:
	od:
	co/nops(ListP):
end:

#4
EstCond := proc(n,v,K) local co,i,P:
	co := 0:
	for i from 1 to K do
		P := RandP(n,v):
		if IsCondorcet(P) then
			co := co+1:
		fi:
	od:
	co/K:
end:

#Observation: when given an even number of voters where half the voters prefer
#candidate i over candidate j and the other half candidate j over candidate i, 
#our SV procedure does not count this as a tie. I decided to stick to odd numbers
#of voters to avoid this.

#ExactCond(3,3) outputs 1/18 (approx 0.0556)
#evalf(EstCond(3,3,10000)) outputted (over 3 trials) 0.0563, 0.0536, 0.0548
#ExactCond(3,5) outputs 5/72 (approx 0.0694)
#evalf(EstCond(3,5,10000)) outputted (over 3 trials) 0.0693, 0.0669, 0.0685

#I ran n=3,4,5 and v=21,31,41 to avoid even numbers of voters
#evalf(EstCond(3,21,10000)) outputted 0.0831, 0.0892, 0.0811
#evalf(EstCond(3,31,10000)) outputted 0.0877, 0.0901, 0.0828
#evalf(EstCond(3,41,10000)) outputted 0.0881, 0.0844, 0.0848
#evalf(EstCond(4,21,10000)) outputted 0.2449, 0.2467, 0.2511
#evalf(EstCond(4,31,10000)) outputted 0.2593, 0.2603, 0.2433
#evalf(EstCond(4,41,10000)) outputted 0.2625, 0.2560, 0.2548
#evalf(EstCond(5,21,10000)) outputted 0.4669, 0.4609, 0.4610
#evalf(EstCond(5,31,10000)) outputted 0.4524, 0.4621, 0.4599
#evalf(EstCond(5,41,10000)) outputted 0.4589, 0.4697, 0.4554

#5
Borda := proc(P) local n,S,i,j:
	n := nops(P[1]):
	S := [seq(0, i=1..n)]:
	
	for i from 1 to nops(P) do
		for j from 1 to n do 
			S[P[i][j]] := S[P[i][j]]+n-j:
		od:
	od:
	
	S:
end:

#6
CondorcetRank := proc(P) local Rank,S,m,i,s,j:
	Rank := []:
	S := SV(Tour(P)): 
	m := max(S):
		
	for i from 0 to m do 
		s := {}:
		for j from 1 to nops(S) do 
			if S[j] = m-i then 
				s := s union {j}:
			fi:
		od:
		if not nops(s) = 0 then 
			Rank := [op(Rank),s]:
		fi:
	od:
	
	Rank:
end:

#7
BordaRank := proc(P) local Rank,S,m,i,s,j:
	Rank := []:
	S := Borda(P):
	m := max(S):
	
	for i from 0 to m do
		s := {}:
		for j from 1 to nops(S) do 
			if S[j] = m-i then 
				s := s union {j}:
			fi:
		od:
		if not nops(s) = 0 then 
			Rank := [op(Rank),s]:
		fi:
	od:
	
	Rank:
end: