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

[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 最小

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

[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 (