当前位置: 首页 > 面试题库 >

我想基于相似的属性对元组进行分组

黄毅
2023-03-14
问题内容

我有一个元组列表。[(1、2),(2、3),(4、3),(5、6),(6、7),(8、2)]

我想根据连接的元组将它们分组为列表(具有相关值)。

因此最终结果是两个相关元组值的列表= [[1、2、3、4、8],[5、6、7]]

如何编写一个函数来做到这一点?这是工作面试的问题。我试图在Python中执行此操作,但是我很沮丧,只是想看看答案背后的逻辑,所以即使是伪代码也可以帮助我,所以我可以看看我做错了什么。

我当时只有几分钟的时间来做,但是这是我尝试过的:

def find_partitions(connections):
 theBigList = []     # List of Lists
 list1 = []          # The initial list to store lists
 theBigList.append(list1)

 for list in theBigList:
 list.append(connection[1[0], 1[1]])
     for i in connections:
         if i[0] in list or i[1] in list:
             list.append(i[0], i[1])

         else:
             newList = []
             theBigList.append(newList)

本质上,这家伙想要一个相关值的列表。我尝试使用for循环,但是意识到它不起作用,然后时间用完了。


问题答案:

在填写组件时,在每个阶段都需要考虑三种情况(因为您 必须 匹配重叠的组):

  1. x或y都没有在已找到的任何组件中。
  2. 两者已经在 不同的集合中 ,x在set_i中,y在set_j中。
  3. 一个或两个都在一个组件中,x在set_i中或y在set_i中。

我们可以使用内置的set帮助。 (请参阅@jwpat和@DSM的更复杂的示例

def connected_components(lst):
    components = [] # list of sets
    for (x,y) in lst:
        i = j = set_i = set_j = None
        for k, c in enumerate(components):
            if x in c:
                i, set_i = k, c
            if y in c:
                j, set_j = k, c

        #case1 (or already in same set)
        if i == j:
             if i == None:
                 components.append(set([x,y]))
             continue

        #case2
        if i != None and j != None:
            components = [components[k] for k in range(len(components)) if k!=i and k!=j]
            components.append(set_i | set_j)
            continue

        #case3
        if j != None:
            components[j].add(x)
        if i != None:
            components[i].add(y)

    return components

lst = [(1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2)]
connected_components(lst)
# [set([8, 1, 2, 3, 4]), set([5, 6, 7])]
map(list, connected_components(lst))
# [[8, 1, 2, 3, 4], [5, 6, 7]]

connected_components([(1, 2), (4, 3), (2, 3), (5, 6), (6, 7), (8, 2)])
# [set([8, 1, 2, 3, 4]), set([5, 6, 7])] # @jwpat's example

connected_components([[1, 3], [2, 4], [3, 4]]
# [set([1, 2, 3, 4])] # @DSM's example

这当然不是最有效的方法,但是可能与他们期望的方法类似。 正如乔恩·克莱门茨(Jon Clements)所指出的那样,有一个用于这些类型的计算的库:
networkx
,在该库中它们会更加高效。



 类似资料:
  • 我如何使用“insref”和“pref”对下面的元素进行分组,我在xslt版本1中使用了生成密钥id。 期望的结果: 这是我所拥有的。我也在使用密钥生成函数。任何想法这个xslt有什么问题。至于计数,我正在考虑获得唯一的密钥计数。

  • 按多个属性对数组中的元素进行分组最符合我的问题,因为它确实是按数组中的多个键对对象进行分组的。问题是,这种解决方案不求和属性值,然后删除重复项,而是将所有重复项嵌套在二维数组中。 预期行为 我有一个对象数组,必须按和分组。 此数组中的对象只有在它们的和相同时才被认为是重复的。如果是,我想分别总结它们的和值,然后删除重复项。 因此,在这个示例中,结果数组可能只包含四种组合:,,, 问题 我在这里尝试

  •     1号  1号      1号     10号                                                                                                   10号                                         5号        5号        5号         

  • 以下是XML输入、想要的输出、我拥有的代码和我得到的错误结果的最小但完整的示例。 这是我的输入XML 这是我当前的XSLT 这是我目前的输出 如果您查看输出,输出中缺少Ccy="GBP"。请查看预期输出。 预期产出 小提琴:https://xsltfiddle.liberty-development.net/ej9EGbG/31

  • 问题内容: 我不知道如何很好地解释这一点,所以请多多包涵。 我试图对彼此相邻的相似行进行分组,如果相同,则基本上忽略第n + 1行。我不确定这在MySQL中是否容易实现。这些行除描述外不共享其他任何属性。如果还有其他不重复的“描述”,我仍然希望将它们返回。 我有一张桌子,上面满是这样的条目: 问题答案: 您可以使用巧妙的技巧来做到这一点。诀窍是计算与特定id 不同 的描述的数量。对于序列中的值,此

  • 例如,我有以下数据集: 我需要根据数组中的条件对数组进行排序。我最终得出了这样的解决方案: 但我无法理解如何使用数组而不是硬编码的和属性。数组可以有许多属性。