Peer Pairing Algorithm

Problem Statement

A class has N number of students. When the students submit an assignment, they are assigned K peers to review their assignments and provide feedback such that 0 < K = N

Example:

Input: N=3, K=1

Output:

{
    0: [1],
    1: [2],
    2: [0]
}

Input: N=3, K=2

{
    0: [1,2],
    1: [2,0],
    2: [0,1]
}

Solution

def generate_peer_pairs(N, K):
    """A function that provides unique peers for reviewing.
    The generated matches follow the following rules:
        1. The no.of reviews/rounds of review is less than total no.of users.
        2. The user won't be reviewing his/her own work
        3. All the reviewers assigned would be unique.
        4. Each user will have equal no.of reviews to give and receive.

    :param N: Total no.of student for whom the matching is to be done.
    :param K: The no.of reviews each student is supposed to receive.
    :returns: a dictionary of graders and their peers { grader_id: [peer_1, peer_2, ...]}
    """
    if K >= N:
        return False

    available_offsets = list(range(1, N))
    offsets = []

    while len(offsets) < rounds:
        offset = random.choice(available_offsets)
        offsets.append(offset)
        available_offsets.remove(offset)

    students = list(range(N))
    random.shuffle(students)

    allocations = {}
    for idx, student in enumerate(students):
        allocations[student] = [students[(idx + offset) % N] for offset in offsets])

    return allocations

Notes

The problem is an interesting one. I started out with the idea that the peers should be arranged in a random way and wrote an algorithm by selecting a random recipient while looping over each grader. It was completely non-roboust and failed to make the right pairs more times that it worked.

The solution if you had noticed, is completely a position shifting algorithm. What appears a non-repeating random order for the grader and the recipient is not really that random.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.