上次发过关于构票系统的分布结构以后(系统架构的设想—票仓未必需要全局唯一和实时的)，今天又构思了一套余票算法。这个算法使用二进制表示站位值（两个站的区间），将已售车票， 剩余车票，座位号和站位值拆分开来。每个站位值仅表达一个连续的可用区间。使用站位值将剩余车票分组。生成1张已售车票时同时生成0-2张剩余车票。初始状态时系统只有一个全程站位值分组， 它包含所有全程剩余车票。 订购车票流程如下：
1. 遍历站位值找到第一个符合此条件的记录
2. 产生1张已售车票，根据剩余区间产生0-2张剩余车票
3. 计算剩余车票的站位值。如果此站位值在站位值列表中不存在，则在站位值列表中加入一条记录。
4. 将剩余票加入相应的站位值分组。
站位值根据其大小排序。 这样遍历搜索时能找到座位分配的最优解。
理论上站位值会有C(n,2)中可能性。 但因为站位值列表是动态生成的，对具体某次列车， 实际产生的购票站位值数量仅仅是其取值范围的一小部分。遍历所产生的开销应可接受。甚至可以分别按照站位值的始发站和终点站在建立索引以减少遍历开销。
举例如下：
假设某列车运行区间有17个站（16个区间），列车共有3000张座位，用1表示有座， 0表示无座。
站位值表初始有且仅有1条记录， 这条记录关联剩余票表中的3000条记录，剩余票表中的记录又分别有唯一的一个座位号。
某用户购买第3站到第15站（第3-14区间）车票，其过程为：
1. 产生一条站位值为0011111111111100的查询请求
2. 系统搜索只有全程（1111111111111111）站位值组满足此请求并分配1号座
3. 将一号座剩余票从全程站位值组中移除
4. 添加1100000000000000站位值分组，并在此分组中添加1号座剩余票
5. 添加0000000000000011站位值分组，并在此分组中添加1号座剩余票
我通过完全随机生成购票请求将一列33站3000个座的列车票售罄的模拟程序得到站位值数量在70个以内。 也就是买票时最多遍历70条记录。实际生活中站位值数量应该会少一些。 这个需要分析铁路局的实际销售数据得到一列火车一般会销售多少种区间类型的票。
代码是用VS2010 C#写的。