前言
【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。
问题描述
公司在情人节的晚上为单身员工举办活动，参与活动的员工根据到达会场的顺序排成一排等待入场。而活动的主办人员，想把员工从队列的某个位置分成两组，想要让分开的两组里每一组的男女人数都均等。但如果到场顺序不对，可能出现无论怎么分，两组都不能出现男女均等的情况。
举个例子，有3位男性、3位女性以“男男女男女女”的顺序到达，如图所示，无论从队列的哪个位置分开，两组的男女人数都不均等。但如果到场的顺序为“男男女女男女”，那么只需要在第4个人处分组就可以令分开的两组男女人数均等了。
求男性20人、女性10人的情况下，有多少种到场顺序会导致无论怎么分组都没有任何一组的组内男女人数能够均等？（书中表述的有问题，这里写的是正确的表述）
粗暴法思路
假如知道了到场顺序，如“男男女男女女”，arrange = ['男','男','女','男','女','女']，对这个队列至多要分5次，如图中所示，才能确定这个到场顺序无论怎么分组，都没有任何一组的组内人数能够相等。
至于怎么分组，可以借用列表的属性，长度为6的arrange，可以分为arrange[:1]和arrange[1:]、arrange[:2]和arrange[2:]、...、arrange[:5]和arrange[5:] 这5种分组。
分组后，如何来确定组内人数是否相等呢？例如在第2个人处分开，则分为ahead = ['男','男']，behind = ['女','男','女','女']，对列表元素的统计，我们想到了字典，判断下字典的值是否相等即可。
另外，对于到场总人数是偶数而言，分组分成两组都是奇数人，那么每组的男女人数肯定不等，因此分组的时候只要分成两边都是偶数人再来判断即可。
现在又有个问题，对于指定的男女人数，有多少种到场顺序呢？具体有哪些？
这个就想到了数学学习组合时常用的例子：现在有6个空盒子，并分别标注1-6，盒子外面有3个红球，3个白球，（红球和白球形状大小都一样）现要把6个求分别放入这6个盒子，且每个盒子仅能放一个球，问有多少种方法，具体怎么放？
如此，我就构造6个带有索引的位置，6个位置中其中有3个位置站的是男性，选出男性站的位置索引，没选出的就是站女性的位置了。
然后就可以来封装函数了。
粗暴法python实现
def grouping(total,male_count):
import itertools
from collections import Counter;
person_place = range(total) # 共有total个位置，并对每个位置索引
count = 0
for item in itertools.combinations(person_place, male_count): # 选出其中的male_count个位置索引，每个位置上站着男性
# 遍历total个位置的索引号，如果索引号在item里，则是男性，否则是女性
arrange = ['男' if i in item else '女' for i in person_place ]
flag = True
if total % 2 == 0: #如果总人数是偶数，只要分成两组都为偶数的情况来判断就好
for i in range(2,total-1,2):
ahead_dict = dict(Counter(arrange[:i]))
behind_dict = dict(Counter(arrange[i:]))
if ahead_dict.get('男')==ahead_dict.get('女') or behind_dict.get('男')==behind_dict.get('女'):
flag = False
break
else:
for i in range(1,total-1):
if i % 2 == 0:
ahead_dict = dict(Counter(arrange[:i]))
if ahead_dict.get('男')==ahead_dict.get('女'):
flag = False
break
else:
behind_dict = dict(Counter(arrange[i:]))
if behind_dict.get('男')==behind_dict.get('女'):
flag = False
break
if flag:
count = count + 1
print(count)
但是！但是！注意！这只适用于数据比较小的情况，像该题共30人，其中20人为男性这种属于比较大的数据了，不适合用这种方法。我这里运行跑了整整一个小时。
为什么？
因为这里要遍历30C20 （组合，这里打不出来，即30045015）条数据，每条数据还要遍历1-15次，运行时间很长了。
优雅版思路（最短路径问题）
用二维表格来表示男女到场的顺序。这里假设向横轴方向移动表示男性到场，向纵轴方向移动表示女性到场，那么到场顺序可以表示为一条路径。因为求的是人数不均等的情况，所以要把男女人数相等的情况（红色点）先排除掉，用图表示的话见下图所示。
问题就转化为：从A点到B点的最短路径有多少条？且不经过红色的点。
优雅版python实现
def get_ary(male,female):
import numpy as np
ary = np.zeros((female+1,male+1)) # 生成 (female+1) 行 (male+1)列的零矩阵
ary[0][0] = 1
for i in range(female+1):
for j in range(male+1):
if i!=j and (male+1-j)!=(female+1-i) :
if j>0:
ary[i][j] = ary[i][j-1]+ary[i][j]
if i>0:
ary[i][j] = ary[i-1][j]+ary[i][j]
print(ary[female][male-1]+ary[female-1][male])
return ary
关于最短路径问题相关的将会另起文章...
