ofooo
2019-10-14 14:20:43 +08:00
```python3
class Test:
def get_groups(self, items, reject_pairs):
"""
生成由 items 组成的 N 个组, 保证每个组里的元素不互相排斥, 且 N 最小
:param items: [item1, item2, item3, ...] 要成组的全部元素
:param reject_pairs: {(item1, item3), (item2, item9) } 二元组集合, 每个二元组表示一个排斥条件
:return: [ [item1], [item2, item3], [...] ] 二维数组
"""
self.sub_groups = {} # {排序的 item 元组: 最佳成组二维数组} 保存临时结果, 减小计算量
groups = self._get_groups(items, reject_pairs)
return groups
def _get_groups(self, items, reject_pairs):
if len(items) == 1:
return [[items[0]]]
sort_types = tuple(sorted(items))
if sort_types in self.sub_groups:
return self.sub_groups[sort_types]
best_groups = None
for t1 in items:
now_group = [t1] # 可以和 t1 成组的元素组成的组
others = [] # 不能和 t1 成组的元素组成的组
for t2 in items:
if t1 == t2:
continue
for tt in now_group:
if self.is_cross(tt, t2, reject_pairs):
others.append(t2)
break
else:
now_group.append(t2)
if len(others) == 0:
best_groups = [now_group]
self.sub_groups[sort_types] = best_groups
return best_groups
else:
groups = self._get_groups(others, reject_pairs) + [now_group]
if best_groups is None or len(best_groups) > len(groups):
best_groups = groups
self.sub_groups[sort_types] = best_groups
return best_groups
def is_cross(self, t1, t2, cross_pairs):
if (t1, t2) in cross_pairs:
return True
if (t2, t1) in cross_pairs:
return True
return False
```
我上面说的计算过程的代码...如果有问题大家多指出, 谢谢