原创算法题: 把有互斥条件的多个元素分组, 如何保证组的数量最少

[ofooo]

元素=[1,2,3,4,5,6,7,8,9] 互斥=[(1,4),(2,5),(1,5),(5,6),(7,8),(3,9),(2,8),(4,5)]

把元素组成 N 个组, 保证互斥元素不在同一个组里, 并且 N 最小

算法渣渣求解, 这种问题应该怎么做呢?

[stebest]

对于原始数组，查询互斥条件，先把里面的元素互斥的元素全踢到另一个新建数组。然后对新数组递归操作，生成另一个新数组，直到新数组长度为 0。

[aijam]

1. 所有元素组成一个 complete graph。
2. 每一对互斥的 pair 对应 graph 里面的一条 edge，一一删除。
3. 答案是：删除 edge 之后得到的 graph 的 connected component 个数。

[arrow8899]

BFS

[aijam]

@aijam 发现这个不对。

[wutiantong]

@aijam

1. 把(a, b) 二元组当作节点，其中 a 不等于 b，总共 n*(n-1)/2 个节点。
2. 在(a, b) 与 (b, c) 之间连线。
3. 从图中删掉所有互斥组合对应的节点。
4. 答案是剩余图的 connected component 个数。

[wutiantong]

@wutiantong 好像还是不对呢。

[wanwenx]

秋招的时候遇到了这题，滴滴的笔试，背景是垃圾分类，然后垃圾互斥，问最少的垃圾车需要多少？结果不会，233333

[aijam]

https://gist.github.com/czheo/09c2a95b54e9a96f000f31f310373dbd

[aijam]

@aijam 只能蒙着眼瞎写猜测 greedy 了。。。

[wutiantong]

你这个 one-pass 遍历得不到最少分组呀。

[aijam]

@wutiantong 其实我也这么觉得，只是看看 greedy 分组啥效果 :D

[arrow8899]

# 先把每个元素的互斥元素找出来
1 (4, 5)
2 (5, 8)
3 (9)
4 (1, 5)
5 (1, 2, 4, 6)
6 (5)
7 (8)
8 (2, 7)
9 (3)

# 新建一个空数组，检测数组中是否存在互斥的元素，不存在就放进去
[1] # 1 直接放进去
[1, 2] # 2 和 1 不互斥，放进去
[1, 2, 3] # 3 之和 9 互斥，放进去
[1, 2, 3] [4] # 4 和 1 互斥，新建一个数组
[1, 2, 3] [4] [5] # 5 和 1，4 都互斥，再新建数组
[1, 2, 3, 6, 7] [4, 8, 9] [5] # 然后 6789 同理
answer = 3
# 如果元素是连续的话，可以直接通过数组下标判断是否互斥，会快很多

[ofooo]

@wanwenx 我要写个小工具其中需要解决这个问题, 没想到真的是个算法题啊.....

我的解法是
先循环每个元素 a, 把全部元素分成 2 组, A 组=包含元素 a 的最多的元素, B 组是其他元素
然后其他元素递归调用这个函数, 这样就获得的以 a 元素为核心的组, 找到数量最少的成组, 返回

然后加了一个临时变量, 保存每一组计算过的元素和最佳成组, 减少计算量

不知道这样算不算解出来了.....

[wutiantong]

@wutiantong 我觉得我这个思路还可以抢救一下：

0. 首先我们要扩展补充 (complete) 所有（显式或隐含定义的）互斥二元组。
0-1. 比如说，假如给定(1, 2), (2, 3) 为互斥关系，那么(2, 3) 也是一个(隐含的)互斥关系。
0-2 从图的角度来说，任何两个元素只要有路径(path)连接，就应确保它们之间有一条直接的边(edge)。

1. 把(a, b) 二元组当作节点，其中 a 不等于 b，总共 n*(n-1)/2 个节点。

2. 在(a, b) 与 (b, c) 之间连线。

3. 从图中删掉所有（显式或隐含定义的）互斥二元组对应的节点。

4. 答案是剩余图的 connected component 个数。

[wutiantong]

@aijam 看我上一条的图解法，我觉得好像没问题了。

[ofooo]

```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

```
我上面说的计算过程的代码...如果有问题大家多指出, 谢谢

[ngc3242]

感觉像是极大团问题，那就有可能是 NP 问题。元素数量不多的话倒是可以考虑状态压缩动态规划或者记忆化搜索。

[necomancer]

@arrow8899 这个正解

[ofooo]

@wutiantong 这个图的解法挺巧妙的, 这样的算法复杂度大概是什么量级的呢?

[wutiantong]

@ofooo 多项式量级。

[wutiantong]

@ofooo 主体计算复杂度就是找出图的 conneted components。

在第 0 步中包含了一次这个计算，针对的是 N 个节点的图。

在最后一步中也包含了一次这个计算，针对的是 O(N*N) 个节点的图。

[coordinate]

通过矩阵表示图，初始化为 1，表示所有边都连接。然后遍历互斥条件，将图中不连接的边标记为 0。最后通过并查集确定多少个集合即可。

[inu1255]

@arrow8899
试试这个测试用例
元素=[1,2,3,4,5,6] 互斥=[(1,3),(2,4),(3,4)]
1 (3)
2 (4)
3 (1,4)
4 (2,3)

# 新建一个空数组，检测数组中是否存在互斥的元素，不存在就放进去
[1]
[1,2]
[1,2],[3]
[1,2],[3],[4]

按照这个算法得到 answer=3
而实际可以 [1,4], [2,3] answer=2

[wutiantong]

@inu1255
他这个算法额外引入了对元素顺序的依赖（从前向后遍历），仍然是一个 trivial 的贪心算法，不是最优解。

[BlackBerry999]

1.将元素作为 key，互斥条件作为值。如（“1”：“4,5”）
2.向数组内插入元素，且要插入的元素必须经过现有数组内元素的互斥条件判定。
3.循环执行 2，直至待插入元素都有分配的数组。

[BlackBerry999]

@BlackBerry999 步骤 1 的作用是生成一个元素的互斥条件判断列表。步骤 2 再进行判断时会使用到 1 生成的列表。

[arrow8899]

@inu1255 又想了想，感觉可以把元素按互斥元素个数排序，先处理互斥元素比较多的，互斥元素越多，对最终结果影响越大。
针对你提出的用例（之前的用例仍然可以通过）：
# 排序
3 (1,4)
4 (2,3)
1 (3)
2 (4)

# 插值
[3]
[3] [4]
[3] [4, 1]
[3, 2] [4, 1]
# 只是一个猜想，不知道是否正确。😁

[soy]

图着色问题
问能否分成 K 组是 NP 完全
问最小能分几组是 NP-Hard

https://en.wikipedia.org/wiki/Graph_coloring

[ijustdo]

@arrow8899 正解 我第一反应也是这么干
可能油更好的方法
但是这个起码可行

a = [1,2,3,4,5,6,7,8,9]
x = [(1,4),(2,5),(1,5),(5,6),(7,8),(3,9),(2,8),(4,5)]

x_info = {}

# 根据互斥信息 找到 每个元素的互斥集合
for i in x:
for j in i:
if j not in x_info:
x_info[j] = set()
x_info[j] = x_info[j] | (set(i) - set([j]))


In [65]: x_info
Out[65]:
{1: {4, 5},
4: {1, 5},
2: {5, 8},
5: {1, 2, 4, 6},
6: {5},
7: {8},
8: {2, 7},
3: {9},
9: {3}}


In [63]: groups = []

In [64]: while a:
...: x = a.pop()
...: rr = []
...: rr.append(x)
...: for i in a:
...: if i not in x_info.get(x, set()):
...: rr.append(i)
...: a.remove(i)
...: groups.append(rr)
...:


In [61]: groups
Out[61]: [[9, 1, 4, 6, 8], [7, 2, 5], [3]]


In [72]: len(groups)
Out[72]: 3

[zjh6]

我不能回复了吗?

[ijustdo]

哈哈 好像我那个不对

[alexfu]

@wutiantong 互斥条件可以看成一个 adjacency list，也就是一个 graph 的边的一种表示形式，同时也是个 sparse matrix，可以把互斥记作 1，不互斥记作 0，这个 sparse graph 记作 A， 这样找出所有间接关系的步骤即为 A*A*...*A 直到第 N 次的结果等于前一次的结果。将此结果记作 A'。A’的 maximum connected subgraph number 即为答案

[alexfu]

@wutiantong 这个是代码比较好写。。python 调包很容易。。时间复杂度就不一定好了。。

[alexfu]

@wutiantong 啊漏了一步 A' = 1 - (A*A*...*A). 掉包的话直接 scipy.sparse 和 igraph.components 估计 10 行就够了。。

[ijustdo]

[code]
a = [1,2,3,4,5,6]
x = [(1,3),(2,4),(3,4)]

a = [1,2,3,4,5,6,7,8,9]
x = [(1,4),(2,5),(1,5),(5,6),(7,8),(3,9),(2,8),(4,5)]

x_info = {}

# 根据互斥信息 找到 每个元素的互斥集合
for i in x:
for j in i:
if j not in x_info:
x_info[j] = set()
x_info[j] = x_info[j] | (set(i) - set([j]))

groups = []
all_is = {}.fromkeys(a)


while a:
ci = a.pop()
rr = []
rr.append(ci)
b = a.copy()
while b:
i = b.pop()
can_in = True
for j in rr:
if i in x_info.get(j, set()):
can_in = False
break
if can_in:
rr.append(i)
a.remove(i)
groups.append(rr)

print(x_info)
print(groups)
[/code]

[ijustdo]

a = [1,2,3,4,5,6]
x = [(1,3),(2,4),(3,4)]

{1: {3}, 3: {1, 4}, 2: {4}, 4: {2, 3}}
[[6, 5, 4, 1], [3, 2]]

----------------------------
a = [1,2,3,4,5,6,7,8,9]
x = [(1,4),(2,5),(1,5),(5,6),(7,8),(3,9),(2,8),(4,5)]

{1: {4, 5}, 4: {1, 5}, 2: {8, 5}, 5: {1, 2, 4, 6}, 6: {5}, 7: {8}, 8: {2, 7}, 3: {9}, 9: {3}}
[[9, 8, 6, 4], [7, 5, 3], [2, 1]]

看结果没有错
图分割的方法 就。。。。

[lrxiao]

图染色 register allocation (