1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2004
Posts
1
Rep Power
0

Creating Random Match Lists

Ok this is going to take some explaining so you might wanna grab a coffee.
First off let me point out this is a piece of coursework for college, but I'm not asking for anyone to do it for me, I just got a bit stuck and need help. I would ask my tutors but they don't know Python.

First off I'll give an explanation of the problem before I put the code I have already created:

Part of the program I need to create is creating a match list of students for a schools games competition (entirely fiction and entirely pointless)

The students are split into classes, and houses. There are 6 classes and two houses (Yellow and Green) classes contain an even number of students between 4 and 8 students in each class. The classes contain an equal mix of students from both houses.

The match list will match the students against each other in four games: Snap, Cribbage, Spillikins, and Scrabble (I have a feeling they came up with this over a 15 minute lunch break)

The houses are competing against each other, but students cannot play students from the same class, they can only play another student once, and they will only take part in one match for each game.

A list of the students, their class numbers and houses can be found here: http://notacake.com/students.txt

So far I have this code to create a shelve object to store a series of Student classes for each student:

Code:
```#!/usr/local/bin/python

import shelve, random

class Student:
pass

students = shelve.open('students')

for line in studentList:
splitted = ''
student = ''

splitted = line.split(',')
student = Student()
student.name = splitted[0]
student.classNo = splitted[1]
student.house = splitted[2]
student.matched = [False, False, False, False]
student.opponents = ['', '', '', '']
student.scores = [0,0,0,0,0,0,0,0,0,0,0,0]

students[student.name] = student

students.close()```
This is code to create the match list:

Code:
```#!/usr/local/bin/python

import shelve, random

class Student:
pass

# Return a random student that hasn't been matched for the given gameType
# Returns: Student class type
def getUnmatched(gameType):
student = random.choice(studentListGroup2)
while student.matched[gameType]:
student = random.choice(studentListGroup2)
return student

students = shelve.open('students')

# Game Types:
# 0 = Snap
# 1 = Cribbage
# 2 = Spillikins
# 3 = Scrabble
games = ['Snap', 'Cribbage', 'Spillikins', 'Scrabble']

# Create two lists so the students can be split into 2 equal amounts
# this should make matching easier
studentListGroup1 = []
studentListGroup2 = []

# Splits the students into the two lists by classes, since Classes 1, 2 and 4
# are equal to classes 3, 5 and 6
for studentName in students.keys():
student = students[studentName]
if student.classNo == '1' or student.classNo == '2' or student.classNo == '4':
studentListGroup1.append(student)
else:
studentListGroup2.append(student)

# Goes through each student in the first group, and picks a random opponent
# from the second list
for student in studentListGroup1:
# This make sure it does it for each gameType
for gameType in range(0, 4):
# Just to make sure they haven't been matched in this gameType
# Note: this came from an earlier method and now seems to be
# redundant, but it is a useful check anyway
if not student.matched[gameType]:
# Pick random student
unmatchedStudent = getUnmatched(gameType)

# Check this random student is not in the same house or class
# The commented bit is supposed to check that they are not
# already playing this student in another match, but this
# causes the program to enter an infinite loop
# ==== This is where the problem is ====
# or at least this is where a flaw in my method becomes apparent
while (unmatchedStudent.house == student.house) or (unmatchedStudent.classNo == student.classNo): # or (unmatchedSudent.name not in student.opponents):
unmatchedStudent = getUnmatched(gameType)

# Set the students as matched and sets the name of the student
# they are matched with
student.matched[gameType] = True
student.opponents[gameType] = unmatchedStudent.name

unmatchedStudent.matched[gameType] = True
unmatchedStudent.opponents[gameType] = student.name

# Prints the match list to the console
print '%s is matched with %s for %s' % (student.name, unmatchedStudent.name, games[gameType])

# Puts the student types back into the shelve
for student in studentListGroup1:
students[student.name] = student

for student in studentListGroup2:
students[student.name] = student

students.close```
Now it's either one of two things:

I've come up with a stupid way of doing it -or-

Any ideas?
2. I haven't ran your code, but based on the fact that you're getting an infinite loop i'd suggest a different algorithm, or at least a modified one.

Without putting too much thought into this (sorry =P ) I'm suggesting a brute force method similar to the following.

Code:
```#(pseudo pythonish code)
def GenerateMatchlist (YellowHouse, GreenHouse)
matchlist = None
while GenerateNewMatchList(YellowHouse, GreenHouse, matchlist, 'snap') :
while GenerateNewMatchList(YellowHouse, GreenHouse, matchlist, 'scrabble') :
while GenerateNewMatchList (YellowHouse, GreenHouse, matchlist, 'Cribbage') :
if GenerateNewMatchList ( YellowHouse, GreenHouse, matchlist, 'Spillikins') :
return matchlist```
where GenerateMatchlist does the following :

1.) looks at the current matchlist items for the game type
2.) if there is no entries in the matchlist for the game type adds the first logical valid entry (ex. Green 1 playes Yellow 1... G2 vs Y2 etc assuming there's no one in the same class)
3.) If there is a current entry it finds the next valid logical entry (if the current entry is G1Y1 G2Y2 G3Y3 G4Y4 the next entry would be G1Y1 G2Y2 G3Y4 G4Y3)

4.) If it's at it's last valid entry (G1Y4 G2Y3 G3Y2 G4Y1) return False

If it makes it all the way to the end return the current match list

It's brute force but it should work, I don't really know of an easy way to make it more intelligent though.

Note: If possible I would use recursion on GenerateMatchList to generate the matches easier.

-MBirchmeier