Xc.Li
Feb.2016
算法原理
首位交易循環(huán)機制的算法，略。
Python實現(xiàn)
學(xué)校和學(xué)生的數(shù)據(jù)結(jié)構(gòu)
-
學(xué)校 class School
- counter:計數(shù)器
- pointer：指向
- preference:偏好向量
- available:學(xué)校是未滿員
- 函數(shù)：refresh
用于每次刷新學(xué)校的指向和偏好向量
-
學(xué)生 class Student
- preference:偏好向量
- pointer：指向
- available：學(xué)生是否已經(jīng)找到學(xué)校
- result：保存學(xué)生最終去的學(xué)校
- 函數(shù)：refresh
用于每次刷新學(xué)生的指向和偏好向量
學(xué)校
class School(object):
def __init__(self, quantity, preference):
self.counter = quantity
self.pointer = preference[0]
self.preference = preference
self.available = True
print self.counter, self.pointer, preference
學(xué)生
class Student(object):
def __init__(self, preference):
self.preference = preference
self.pointer = preference[0]
self.available = True
self.result = None
學(xué)校和學(xué)生的刷新
學(xué)校
class School 里的函數(shù)：
def refresh(self):
original_preference = self.preference
self.preference = []
for item in original_preference:
if student_list[item].available is True:
self.preference.append(item)
try:
self.pointer = self.preference[0]
except:
print 'ok'
學(xué)生
class Student 里的函數(shù)：
def refresh(self):
original_preference = self.preference
self.preference = []
for item in original_preference:
if school_list[item].available is True:
self.preference.append(item)
self.pointer = self.preference[0]
窮舉構(gòu)環(huán)
從學(xué)校出發(fā)枢希，根據(jù)學(xué)校和學(xué)生的指向向circle列表中添加元素聊替。
判斷方式：
如果某元素和起始元素相同則終止程序谊娇，找到一個完整的環(huán)
處理方式是調(diào)用School.refresh和Student.refresh刷新狀態(tài)，調(diào)用Handle(circle)處理環(huán)始鱼。-
如果環(huán)的長度大于10（僅舉例），則認(rèn)為是死循環(huán)（例如s2-i1-s1-i1-s1-....)脆贵，也終止程序医清。
while True:
count = 0
for j in range(1, student_num + 1, 1): #careful
if student_list['i' + str(j)].available is False:
count += 1
if count == student_num:
breaki = 1
circle = []
while i <= school_num:
school_name = 's' + str(i)
if school_list[school_name].available is False:
continue
# circle.append(school_name)
while True:
student_name = school_list[school_name].pointer
circle.append(student_name)
school_name = student_list[student_name].pointer
circle.append(school_name)
if school_name == 's' + str(i):
flag = 1
break
if len(circle) > 10:
flag = 0
circle = 'Error'
break
if flag == 1:
handle(circle)
for j in range(1, school_num + 1, 1): # careful
school_list['s' + str(j)].refresh()
for j in range(1, student_num + 1, 1): # careful
student_list['i' + str(j)].refresh()
print circle
circle = []
i += 1
環(huán)的處理
對于每個環(huán)內(nèi)的學(xué)生i，將目前指向pointer賦值給結(jié)果result保存卖氨，把available賦值為False会烙，以示退出。
對于每個環(huán)內(nèi)的學(xué)校s筒捺，counter減1柏腻。判斷counter是否為0，如果是則把available賦值為False系吭，以示退出五嫂。
def handle(circle):
for item in circle:
if item[0] == 'i':
student_list[item].available = False
student_list[item].result = student_list[item].pointer
if item[0] == 's':
school_list[item].counter -= 1
if school_list[item].counter == 0:
school_list[item].available = False
print 'school out!'
運行
測試
number of schools:輸入0
演示：
C:\Python27\python.exe D:/OneDrive/Python/TTCM.py
number of schools:0 #這里輸入0
test
2 i1 ['i1', 'i2', 'i3', 'i4', 'i5', 'i6', 'i7', 'i8']
2 i3 ['i3', 'i5', 'i4', 'i8', 'i7', 'i2', 'i1', 'i6']
3 i5 ['i5', 'i3', 'i1', 'i7', 'i2', 'i8', 'i6', 'i4']
3 i6 ['i6', 'i8', 'i7', 'i4', 'i2', 'i3', 'i5', 'i1']
['i1', 's2', 'i3', 's3', 'i5', 's1']
Error #表示找不到環(huán)
Error
['i6', 's4']
school out!
['i2', 's1']
school out!
['i4', 's3', 'i7', 's2']
Error
ok #學(xué)校滿員
ok
ok
ok
['i8', 's4']
1 s2
2 s1
3 s3
4 s3
5 s1
6 s4
7 s2
8 s4
數(shù)據(jù)輸入
number of schools：學(xué)校個數(shù)（整數(shù)）
number of students:學(xué)生個數(shù)（整數(shù)）
quantity of school:學(xué)校招生人數(shù)（整數(shù)）
enter the preference of school:學(xué)校偏好，例如i1,i2,i3
enter the preference of student:學(xué)生偏好肯尺，例如s1,s2,s3
完整代碼
基于Python2.7
# -*- encoding:utf-8 -*-
# 首位交易循環(huán)機制
# Designed By Xc.Li @ Feb.2015
class School(object):
def __init__(self, quantity, preference):
self.counter = quantity
self.pointer = preference[0]
self.preference = preference
self.available = True
print self.counter, self.pointer, preference
def refresh(self):
original_preference = self.preference
self.preference = []
for item in original_preference:
if student_list[item].available is True:
self.preference.append(item)
try:
self.pointer = self.preference[0]
except:
print 'ok'
class Student(object):
def __init__(self, preference):
self.preference = preference
self.pointer = preference[0]
self.available = True
self.result = None
def refresh(self):
original_preference = self.preference
self.preference = []
for item in original_preference:
if school_list[item].available is True:
self.preference.append(item)
self.pointer = self.preference[0]
# input and initialize
school_num = int(raw_input("number of schools:"))
if school_num == 0:
print 'test'
school_num = 4
school_list = {
's1': School(2, ['i1', 'i2', 'i3', 'i4', 'i5', 'i6', 'i7', 'i8']),
's2': School(2, ['i3', 'i5', 'i4', 'i8', 'i7', 'i2', 'i1', 'i6']),
's3': School(3, ['i5', 'i3', 'i1', 'i7', 'i2', 'i8', 'i6', 'i4']),
's4': School(3, ['i6', 'i8', 'i7', 'i4', 'i2', 'i3', 'i5', 'i1'])
}
student_num = 8
student_list = {
'i1': Student(['s2', 's1', 's3', 's4']),
'i2': Student(['s1', 's2', 's3', 's4']),
'i3': Student(['s3', 's2', 's1', 's4']),
'i4': Student(['s3', 's4', 's1', 's2']),
'i5': Student(['s1', 's3', 's4', 's2']),
'i6': Student(['s4', 's1', 's2', 's3']),
'i7': Student(['s1', 's2', 's3', 's4']),
'i8': Student(['s1', 's2', 's4', 's3'])
}
else:
student_num = int(raw_input("number of students:"))
# school initialize
i = 1
school_list = {}
while i <= school_num:
school_name = 's' + str(i)
print school_name
quantity = int(raw_input("quantity of school:"))
preference = raw_input("enter the preference of school:")
preference = preference.split(",")
school_list[school_name] = School(quantity, preference)
i += 1
# student initialize
i = 1
student_list = {}
while i <= student_num:
student_name = 'i' + str(i)
print student_name
preference = raw_input("enter the preference of student:")
preference = preference.split(",")
student_list[student_name] = Student(preference)
i += 1
def handle(circle):
for item in circle:
if item[0] == 'i':
student_list[item].available = False
student_list[item].result = student_list[item].pointer
if item[0] == 's':
school_list[item].counter -= 1
if school_list[item].counter == 0:
school_list[item].available = False
print 'school out!'
k = 0
while True:
count = 0
for j in range(1, student_num + 1, 1): # fuck it!
if student_list['i' + str(j)].available is False:
count += 1
if count == student_num:
break
i = 1
circle = []
while i <= school_num:
school_name = 's' + str(i)
if school_list[school_name].available is False:
continue
# circle.append(school_name)
while True:
student_name = school_list[school_name].pointer
circle.append(student_name)
school_name = student_list[student_name].pointer
circle.append(school_name)
if school_name == 's' + str(i):
flag = 1
break
if len(circle) > 10:
flag = 0
circle = 'Error'
break
if flag == 1:
handle(circle)
for j in range(1, school_num + 1, 1): # careful
school_list['s' + str(j)].refresh()
for j in range(1, student_num + 1, 1): # careful
student_list['i' + str(j)].refresh()
print circle
circle = []
i += 1
for k in range(1, student_num + 1, 1):
print k, student_list['i' + str(k)].result