V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ofooo
V2EX  ›  程序员

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

  •  
  •   ofooo · 2019-10-14 11:08:13 +08:00 · 5041 次点击
    这是一个创建于 1627 天前的主题,其中的信息可能已经有所发展或是发生改变。

    元素=[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 最小

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

    37 条回复    2019-10-15 05:00:50 +08:00
    stebest
        1
    stebest  
       2019-10-14 13:20:13 +08:00
    对于原始数组,查询互斥条件,先把里面的元素互斥的元素全踢到另一个新建数组。然后对新数组递归操作,生成另一个新数组,直到新数组长度为 0。
    aijam
        2
    aijam  
       2019-10-14 13:31:44 +08:00
    1. 所有元素组成一个 complete graph。
    2. 每一对互斥的 pair 对应 graph 里面的一条 edge,一一删除。
    3. 答案是:删除 edge 之后得到的 graph 的 connected component 个数。
    arrow8899
        3
    arrow8899  
       2019-10-14 13:31:46 +08:00
    BFS
    aijam
        4
    aijam  
       2019-10-14 13:44:38 +08:00
    @aijam 发现这个不对。
    wutiantong
        5
    wutiantong  
       2019-10-14 13:51:34 +08:00
    @aijam

    1. 把(a, b) 二元组当作节点,其中 a 不等于 b,总共 n*(n-1)/2 个节点。
    2. 在(a, b) 与 (b, c) 之间连线。
    3. 从图中删掉所有互斥组合对应的节点。
    4. 答案是剩余图的 connected component 个数。
    wutiantong
        6
    wutiantong  
       2019-10-14 13:52:34 +08:00
    @wutiantong 好像还是不对呢。
    wanwenx
        7
    wanwenx  
       2019-10-14 13:54:36 +08:00 via Android
    秋招的时候遇到了这题,滴滴的笔试,背景是垃圾分类,然后垃圾互斥,问最少的垃圾车需要多少?结果不会,233333
    aijam
        8
    aijam  
       2019-10-14 14:02:04 +08:00
    aijam
        9
    aijam  
       2019-10-14 14:05:31 +08:00
    @aijam 只能蒙着眼瞎写猜测 greedy 了。。。
    wutiantong
        10
    wutiantong  
       2019-10-14 14:06:56 +08:00
    你这个 one-pass 遍历得不到最少分组呀。
    aijam
        11
    aijam  
       2019-10-14 14:09:15 +08:00
    @wutiantong 其实我也这么觉得,只是看看 greedy 分组啥效果 :D
    arrow8899
        12
    arrow8899  
       2019-10-14 14:10:34 +08:00   ❤️ 3
    # 先把每个元素的互斥元素找出来
    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
        13
    ofooo  
    OP
       2019-10-14 14:11:47 +08:00
    @wanwenx 我要写个小工具其中需要解决这个问题, 没想到真的是个算法题啊.....

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

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

    不知道这样算不算解出来了.....
    wutiantong
        14
    wutiantong  
       2019-10-14 14:13:54 +08:00
    @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
        15
    wutiantong  
       2019-10-14 14:16:40 +08:00
    @aijam 看我上一条的图解法,我觉得好像没问题了。
    ofooo
        16
    ofooo  
    OP
       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

    ```
    我上面说的计算过程的代码...如果有问题大家多指出, 谢谢
    ngc3242
        17
    ngc3242  
       2019-10-14 14:24:35 +08:00
    感觉像是极大团问题,那就有可能是 NP 问题。元素数量不多的话倒是可以考虑状态压缩动态规划或者记忆化搜索。
    necomancer
        18
    necomancer  
       2019-10-14 14:29:26 +08:00
    @arrow8899 这个正解
    ofooo
        19
    ofooo  
    OP
       2019-10-14 14:32:16 +08:00
    @wutiantong 这个图的解法挺巧妙的, 这样的算法复杂度大概是什么量级的呢?
    wutiantong
        20
    wutiantong  
       2019-10-14 14:36:46 +08:00
    @ofooo 多项式量级。
    wutiantong
        21
    wutiantong  
       2019-10-14 14:42:07 +08:00
    @ofooo 主体计算复杂度就是找出图的 conneted components。

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

    在最后一步中也包含了一次这个计算,针对的是 O(N*N) 个节点的图。
    coordinate
        22
    coordinate  
       2019-10-14 14:50:42 +08:00
    通过矩阵表示图,初始化为 1,表示所有边都连接。然后遍历互斥条件,将图中不连接的边标记为 0。最后通过并查集确定多少个集合即可。
    inu1255
        23
    inu1255  
       2019-10-14 16:52:51 +08:00
    @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
        24
    wutiantong  
       2019-10-14 17:01:01 +08:00
    @inu1255
    他这个算法额外引入了对元素顺序的依赖(从前向后遍历),仍然是一个 trivial 的贪心算法,不是最优解。
    BlackBerry999
        25
    BlackBerry999  
       2019-10-14 17:04:21 +08:00
    1.将元素作为 key,互斥条件作为值。如(“1”:“4,5”)
    2.向数组内插入元素,且要插入的元素必须经过现有数组内元素的互斥条件判定。
    3.循环执行 2,直至待插入元素都有分配的数组。
    BlackBerry999
        26
    BlackBerry999  
       2019-10-14 17:06:58 +08:00
    @BlackBerry999 步骤 1 的作用是生成一个元素的互斥条件判断列表。步骤 2 再进行判断时会使用到 1 生成的列表。
    arrow8899
        27
    arrow8899  
       2019-10-14 17:17:48 +08:00
    @inu1255 又想了想,感觉可以把元素按互斥元素个数排序,先处理互斥元素比较多的,互斥元素越多,对最终结果影响越大。
    针对你提出的用例(之前的用例仍然可以通过):
    # 排序
    3 (1,4)
    4 (2,3)
    1 (3)
    2 (4)

    # 插值
    [3]
    [3] [4]
    [3] [4, 1]
    [3, 2] [4, 1]
    # 只是一个猜想,不知道是否正确。😁
    soy
        28
    soy  
       2019-10-14 17:59:37 +08:00   ❤️ 3
    图着色问题
    问能否分成 K 组是 NP 完全
    问最小能分几组是 NP-Hard

    https://en.wikipedia.org/wiki/Graph_coloring
    ijustdo
        29
    ijustdo  
       2019-10-14 18:15:18 +08:00
    @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
        30
    zjh6  
       2019-10-14 18:18:48 +08:00
    我不能回复了吗?
    ijustdo
        31
    ijustdo  
       2019-10-14 18:29:02 +08:00
    哈哈 好像我那个不对
    alexfu
        32
    alexfu  
       2019-10-14 18:43:02 +08:00
    @wutiantong 互斥条件可以看成一个 adjacency list,也就是一个 graph 的边的一种表示形式,同时也是个 sparse matrix,可以把互斥记作 1,不互斥记作 0,这个 sparse graph 记作 A, 这样找出所有间接关系的步骤即为 A*A*...*A 直到第 N 次的结果等于前一次的结果。将此结果记作 A'。A’的 maximum connected subgraph number 即为答案
    alexfu
        33
    alexfu  
       2019-10-14 18:43:54 +08:00
    @wutiantong 这个是代码比较好写。。python 调包很容易。。时间复杂度就不一定好了。。
    alexfu
        34
    alexfu  
       2019-10-14 18:49:28 +08:00
    @wutiantong 啊漏了一步 A' = 1 - (A*A*...*A). 掉包的话直接 scipy.sparse 和 igraph.components 估计 10 行就够了。。
    ijustdo
        35
    ijustdo  
       2019-10-14 20:06:27 +08:00
    [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
        36
    ijustdo  
       2019-10-14 20:11:23 +08:00
    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
        37
    lrxiao  
       2019-10-15 05:00:50 +08:00
    图染色 register allocation (
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3146 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 12:32 · PVG 20:32 · LAX 05:32 · JFK 08:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.