Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I'm currently learning Python and having a great time so far (coming from PHP, I have a feeling of suddenly seeing the light).

At the same time, I'm studying voting algorithms. So, for training purposes, I made this little class which determines the Condorcet winner of a rank voting election (basically, a Condorcet winner is a candidate that would beat every other candidate in a head-to-head election).

This code does work, but I'd like to learn two-three things by posting it here:

  1. Is this class written in a correct Pythonic way?
  2. Do you see any ways to improve this code?
  3. (bonus) If there are voting specialists among you, could you tell if that way of going through a Condorcet algorithm seems correct?

Condorcet.py:

import itertools


class Condorcet:
    """
    Gives Concorcet winner from a list of votes
    """
    def __init__(self, filename):
        self.candidates = set()
        self.scores = dict() # score for each permutation of two candidates
        self.results = dict() # winner of each pair of candidates
        self.winner = None # Condorcet winner of the election
        self.voters = list() # ranking of each voter
        self.filename = filename

    def process(self):
        self._get_data_from_file()
        self._build_dict()
        self._matches_candidates()
        self._elect_winner()
        return self.winner

    def _get_data_from_file(self):
        with open(self.filename, encoding='utf-8') as file:
            for lines in file:
                # currently hard-coding the number of candidates at 4
                # needs fixing but it's not my point here
                # (more a question for StackOverflow actually)
                (one, two, three, four) = lines.split(None, 4)
                self.voters.append((one, two, three, four))

    def _build_dict(self):
        """
        Builds a dictionary of scores
        for each permutation of two candidates
        """
        for voting in self.voters:
            for candidate in voting:
                self.candidates.add(candidate)
            for pair in list(itertools.permutations(voting, 2)):
                if pair not in self.scores:
                    self.scores[pair] = 0
                if voting.index(pair[0]) < voting.index(pair[1]):
                    self.scores[pair] += 1

    def _matches_candidates(self):
        """
        Analyses the dictionary of scores and
        gives the winner of every pair of candidates
        """
        for match in list(itertools.combinations(self.candidates, 2)):
            reverse = tuple(reversed(match))
            if self.scores[match] > self.scores[reverse]:
                self.results[match] = match[0]
            else:
                self.results[match] = match[1]

    def _elect_winner(self):
        """
        If a candidates is the winner against
        every other candidate, declares him the winner
        (Note: does not detect Condorcet cycles yet)
        """
        for candidate in self.candidates:
            candidate_score = 0
            for result in self.results:
                if candidate in result and self.results[result] == candidate:
                    candidate_score += 1
            if candidate_score == len(self.candidates) - 1:
                self.winner = candidate

execute_condorcet.py:

import Condorcet

condorcet = Condorcet.Condorcet('condorcet.txt')
winner = condorcet.process()
print(winner)

condorcet.txt:

# each line represents the ranking
# of candidates A, B, C and D
# by a unique voter

A B C D # this voter ranked A first, B second, C third, D fourth
C B D A
A B D C
C A D B
C B A D
C A B D

# and it goes on

and the winner could be C, beating :

  • A 4 votes to 2
  • B 4 votes to 2
  • D 5 votes to 1
share|improve this question
    
Please fix your indentation. Indentation is crucial in Python. –  Joel Cornett Feb 21 at 5:19
    
Looks good. There are some places where you could use list comprehensions instead of loops, but that's not a "must" e.g. self.voters = [lines.split(None, 4) for lines in file]. Some of your other loops could be turned into list comprehensions by pulling out a helper function. But that's absolutely an impression rather than a prescription. –  Rob Y Feb 21 at 8:12

2 Answers 2

up vote 3 down vote accepted

Taking into account Janne Karila's comment as a basis :

#!/usr/bin/python3

import itertools

def condorcet_winner(filename):
    voters = get_data_from_file(filename)
    candidates, scores = build_dict(voters)
    results = matches_candidates(candidates, scores)
    return elect_winner(candidates, results)

def get_data_from_file(filename):
    voters = []
    with open(filename, encoding='utf-8') as file:
        for lines in file:
            # currently hard-coding the number of candidates at 4
            # needs fixing but it's not my point here
            # (more a question for StackOverflow actually)
            (one, two, three, four) = lines.split(None, 4)
            voters.append((one, two, three, four))
    return voters

def build_dict(voters):
    """
    Builds a dictionary of scores
    for each permutation of two candidates
    """
    candidates = set()
    scores = dict()
    for voting in voters:
        for candidate in voting:
            candidates.add(candidate)
        for pair in list(itertools.permutations(voting, 2)):
            if pair not in scores:
                scores[pair] = 0
            if voting.index(pair[0]) < voting.index(pair[1]):
                scores[pair] += 1
    return candidates, scores

def matches_candidates(candidates, scores):
    """
    Analyses the dictionary of scores and
    gives the winner of every pair of candidates
    """
    results = dict()
    for match in list(itertools.combinations(candidates, 2)):
        reverse = tuple(reversed(match))
        if scores[match] > scores[reverse]:
            results[match] = match[0]
        else:
            results[match] = match[1]
    return results


def elect_winner(candidates, results):
    """
    If a candidates is the winner against
    every other candidate, declares him the winner
    (Note: does not detect Condorcet cycles yet)
    """
    for candidate in candidates:
        candidate_score = 0
        for result in results:
            if candidate in result and results[result] == candidate:
                candidate_score += 1
        if candidate_score == len(candidates) - 1:
            return candidate

print(condorcet_winner('condorcet.txt'))

Now, in get_data_from_file, if you want to handle any number of candidates, just use lines.split(None). It will use a list instead of a tuple but it doesn't make any difference to you because of the way you use it afterwards.

You function now becomes :

def get_data_from_file(filename):
    voters = []
    with open(filename, encoding='utf-8') as file:
        for lines in file:
            voters.append(lines.split(None))
    return voters

which can be rewritten using list comprehension :

def get_data_from_file(filename):
    with open(filename, encoding='utf-8') as file:
        return [l.split(None) for l in file]
    return []

Now, the whole code could be simplified by using the right data structure : for each pair of candidates C1 and C2, instead of having the counts of victories of C1 over C2 and the count of victories of C2 over C1, you could just count positively the former and negatively the latter. In order to do so, you could store the results in a dictionnary mapping pairs of (different) candidates to (signed) results. In order to keep things simple, we can assume that the first element of the pair is the smallest.

Then, abusing all the good things from Python : set comprehension, itertools, tuple unpacking, generator expression, etc, one could write :

def short_solution(voters):
    results = defaultdict(int)
    for voter in voters:
        for c1,c2 in itertools.combinations(voter, 2):
            assert(c1!=c2)
            mini,maxi,res = (c1,c2,1) if c1 < c2 else (c2,c1,-1)
            results[mini,maxi] += res
    for c in {c for voter in voters for c in voter}:
        if (all((res>0 if c==mini else res<0) for (mini,maxi),res in results.items() if c in [mini,maxi])):
            return c
    return None
share|improve this answer
    
I'm quite impressed with your "one could write..." section. Thanks for that. –  Jivan Feb 23 at 18:12

The purpose of your class is to perform a single computation: given filename, determine winner. That's a task for a function; there is no need for a class. You can turn each method to an independent function that takes one or two arguments and returns one or two values instead of accessing instance attributes, and provide this function to orchestrate the whole computation:

def concordet_winner(filename):
    voters = _get_data_from_file(filename)
    candidates, scores = _build_dict(voters)
    results = _matches_candidates(candidates, scores)
    return _elect_winner(candidates, results)

Now, reading this code gives a clear picture how the data flows through the computation.


For the purpose of learning OOP, you could consider a slightly different exercise: instead of having all votes in a file, create a class with a vote method that takes in an individual voter's vote, and a winner property that updates automatically after every vote.

share|improve this answer
    
Thanks for your answer. I upvoted you because you advised interesting alternatives. –  Jivan Feb 23 at 18:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.