【Python算法】某银行运管部凭证号分配需求难点解决
需求片段描述
如图1所示，同一个凭证种类下会有多个连续的待分配的凭证起始号到终止号。另外，由于具体业务需要，提供了一张凭证禁用号段表格，其中记录了每一种凭证种类下多个连续的不可以使用的凭证起始号到终止号。将待分配的减去禁用的得到的就是可以分配的凭证数量。
图片1
凭证禁用号段
对于图2中的每一笔已经审批的凭证预约记录，会有如图3所示的一种或多种凭证种类需要分配的凭证数量，当这个需要分配的凭证数量小于等于可以分配的凭证数量时，进行凭证号分配操作。分配时，按顺序填写每一个可以分配凭证的起始号到终止号，直到需要分配的凭证数量用完为止。
图片2
图片3
具体操作
凭证号分配操作步骤的一个假设案例如下：
为方便起见，待分配和禁用号段都保存为集合的结构。假设多个连续的待分配的凭证起始号到终止号分别为{1, 2, 3, 4, 5}, {11, 12, 13, 14, 15}, {21, 22, 23, 24, 25}，禁用号段分别为{9, 10, 11, 12}, {15, 16, 17, 18, 19, 20, 21}, {24, 25, 26}，那么可分配的凭证为[[1, 2, 3, 4, 5], [13, 14], [22, 23]]，总共9张可以分配的凭证，假设现在需要分配6张，那么按顺序分配的结果就是[[1, 2, 3, 4, 5], [13, 14]]，在业务系统中的起始和终止分别填写1和5，13和14即可。
算法分解
从后往前推，我们可以设计两个算法来解决以上问题。分别命名为集合分块算法和分块填入算法。
集合分块算法
图1尾箱凭证表中同一个凭证种类的多个起始终止号作为一个集合，比如集合a,b,c，每一个集合内的值是可以连续的
相同凭证种类的每一个需要排除的凭证起始终止号作为一个集合，比如集合d,e,f，每一个集合内的值是可以连续的
对于集合a,b,c中的每一个集合，都减去每一个排除集合，之后转为列表并排序，按连续情况分为多个列表，最后统一放在列表set_list中
代码如下：
from functools import reduce
def split_unconsecutive_list(given_list):
'''
将给定非连续列表分割为一个个连续列表
并存放在一个列表中
'''
if len(given_list) == 1:
return [given_list]
else:
index_list = [0]
for index, item in list(enumerate(given_list))[1:]:
if item - given_list[index - 1] > 1:
index_list.append(index)
index_list.append(len(given_list))
return [
given_list[index_list[i] : index_list[i + 1]]
for i in range(0, len(index_list) - 1)]
def set_split(given_set_list, eliminate_set_list):
'''
集合分块算法
输入为一个给定集合组组成的列表
和一个给定排除集合组组成的列表
输出为从每一个给定集合组排除所有给定排除集合组之后得到的多个连续列表组成的列表
'''
tem_list = []
for each_set in given_set_list:
each_set = split_unconsecutive_list(
sorted(
list(
reduce(lambda x, y: x - y,
[each_set] + eliminate_set_list))))
if len(each_set) == 1:
tem_list.append(each_set[0])
else:
for every_set in each_set:
tem_list.append(every_set)
return tem_list
if __name__ == "__main__":
print(
set_split([{1, 2, 3, 4, 5}, {10, 11, 12, 13, 14, 15, 16},
{21, 22, 23, 24, 25}],
[{9, 10}, {13}, {16, 17, 18, 19, 20, 21}, {24, 25, 26}]))
分块填入算法
对于多个连续列表组成的列表，例如[[11-20]，[31-40]，[51-60]]，给定一个不超过所有连续列表元素数量之和的一个数，假设是29
返回数量总和为这个数的连续列表，这个例子中的返回结果为[11-20]，[31-40]，[51-59]
def split_insert1(set_list, num):
'''
分块填入算法
输入为多个连续列表（且数从小到大排列）组成的列表
以及一个不超过所有连续列表元素数量之和的数
返回数量总和为这个数的连续列表
'''
for index, item in enumerate([len(i) for i in set_list]):
num -= item
if num <= 0:
return set_list[:index] + [set_list[index][:num + item]]
def split_insert2(set_list, num):
'''
分块填入算法，解法二
输入为多个连续列表（且数从小到大排列）组成的列表
以及一个不超过所有连续列表元素数量之和的数
返回数量总和为这个数的连续列表
'''
ini_length = 0
for i in range(len(set_list)):
ini_length += len(set_list[i])
if ini_length >= num:
break
return set_list[:i] + [set_list[i][:len(set_list[i]) - ini_length + num]]
if __name__ == "__main__":
print(split_insert1([list(range(11, 21)), list(range(31, 41)), list(range(51, 61))], 29))
2019/10/21更新
考虑这样一种情况：当凭证起始号到终止号的跨度范围很大时，生成集合所花费的内存开销会变得非常大，因此用上述的集合分块算法很可能会报内存错误，此时我们需要考虑另一种算法。这种算法只比较起始号和终止号两端的值，因此对内存空间的占用之和给的区间个数有关，和区间跨度无关。
from functools import reduce
def del_wrong(li):
"""
对于列表li中的每一个元组
把前一个元素大于后一个元素的元组删掉
"""
i = 0
while i <= len(li) - 1:
if li[i][0] > li[i][-1]:
del li[i]
else:
i += 1
return li
def set_split(given_tuple_list, eliminate_tuple):
"""
给定所有可配号区间和一个排除区间
返回去除排除区间后的所有区间元组组成的列表
"""
tem_li = []
for given_tuple in given_tuple_list:
if eliminate_tuple[0] > given_tuple[-1] or eliminate_tuple[
-1] < given_tuple[0]:
tem_li.append(given_tuple)
else:
tem_li.extend(
del_wrong([(given_tuple[0], eliminate_tuple[0] - 1),
(eliminate_tuple[-1] + 1, given_tuple[-1])]))
return tem_li
def split_insert(given_tuple_list, eliminate_tuple_list):
"""
时间复杂度最高为len(given_tuple_list)*len(eliminate_tuple_list)
例如，可配号区间为10个，需排除区间为5个
则最多需要运算10*5=50次
空间复杂度与区间覆盖面积无关，和区间个数成正比
"""
tem_li = []
tem_li.extend(reduce(set_split, [given_tuple_list] + eliminate_tuple_list))
return tem_li
if __name__ == "__main__":
print(
split_insert([(1, 5), (10, 15), (20, 25), (27, 28)], [(2, 3), (9, 12),
(15, 21),
(24, 30)]))
# 以下例子显示了在区间范围很大时此算法相对集合相减运算的优势，集合运算最终会报内存错误，而此算法时间复杂度为1*1*1=1，空间复杂度为几个字节
print(
split_insert([(1, 10000000000000000000000000000000000000000000000000)],
[(100, 200), (300, 400), (500,)]))
