如何找到和组合/组数组好友值一起成几个数组?

Question

我有一个大数组命名为whoHasMe如下:

whoHasMe:  [[0], [1], [0, 2, 3], [1, 2, 3, 4, 5], [4], [5], [6, 7, 8], [7], [6, 8]]

我们可以注意到，这些

whoHasMe[0]与whoHasMe[2]有关系

whoHasMe[1]与whoHasMe[3]有关系

whoHasMe[2]与whoHasMe[3]有关系

whoHasMe[4]与whoHasMe[3]有关系

whoHasMe[5]与whoHasMe关系[3]

whoHasMe[6]与whoHasMe[7]有关系

whoHasMe[8]有关系whoHasMe [7]

如何将它分组成另一个新的大数组?

finalBigArray = [[0,1,2,3,4,5]， [6,7,8]]

注意:whoHasMe数组的值可能会改变。寻求帮助如何找到它的关系和建立一个最终的大数组。

谢谢你,祝你有美好的一天。

Answer 1

我能想到的方法是使用disjoint set。这是一个简单的实现:

class DisjointSet:
def __init__(self, n):
self.root = list(range(n))
def __getitem__(self, k):    # find root
return k if self.root[k] == k else self[self.root[k]]
def union(self, a, b):
x, y = self[a], self[b]
if x != y:
self.root[y] = x

首先，将给定列表中的每个列表转换为一个集合:

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

然后判断每对组合之间是否存在关系。如果是，将它们的索引联合:

length = len(lst)
ds = DisjointSet(length)
for i in range(length):
for j in range(i + 1, length):
if lst[i] & lst[j]:
ds.union(i, j)

上一步的两层环可以通过itertools.combinations:

简化

from itertools import combinations
for (i, s1), (j, s2) in combinations(enumerate(lst), 2):
if s1 & s2:
ds.union(i, j)

在defaultdict的帮助下，我们得到了同一集合中的并集:

from collections import defaultdict
d = defaultdict(set)
for i in range(length):
d[ds[i]] |= lst[i]

最后，将字典值转换为列表:

print(list(map(sorted, d.values())))

输出:

[[0, 1, 2, 3, 4, 5], [6, 7, 8]]

---

更新:

我稍微修改了不相交集，将递归转换为循环，并通过__getitem__方法和__len__方法使其支持迭代。最后的代码如下:

from collections import defaultdict
from itertools import combinations

class DisjointSet:
def __init__(self, n):
self.root = [None] * n
def __getitem__(self, k):
root = self.root
while (r := root[k]) is not None:
k = r
return k
def __len__(self):
return len(self.root)
def union(self, a, b):
x, y = self[a], self[b]
if x != y:
self.root[y] = x

def my_merge(lists):
lists = list(map(set, lists))
ds = DisjointSet(len(lists))
for (i, s1), (j, s2) in combinations(enumerate(lists), 2):
if s1 & s2:
ds.union(i, j)
d = defaultdict(set)
for r, s in zip(ds, lists):
d[r] |= s
return list(map(sorted, d.values()))

一些测试:

import random
for _ in range(3):
lst = [sorted(random.randint(0, 50) for _ in range(random.randint(1, 6))) for _ in range(5)]
print(f'lists:  {lst}')
print(f'result: {my_merge(lst)}')

输出:

lists:  [[21, 26, 42, 44, 47], [4, 27, 40, 49], [5, 20, 39, 50], [14, 40, 47], [6]]
result: [[4, 14, 21, 26, 27, 40, 42, 44, 47, 49], [5, 20, 39, 50], [6]]
lists:  [[14, 26], [22], [4], [18, 22, 33, 37], [4, 5, 13, 19, 38, 46]]
result: [[14, 26], [18, 22, 33, 37], [4, 5, 13, 19, 38, 46]]
lists:  [[9, 9, 21, 31, 41], [7, 9, 28, 35, 43], [13, 23, 37, 42, 45], [4, 14, 21, 25], [0, 12, 14, 39, 50]]
result: [[0, 4, 7, 9, 12, 14, 21, 25, 28, 31, 35, 39, 41, 43, 50], [13, 23, 37, 42, 45]]

Answer 2

之前的答案有问题，以下是新的更正版本，如有问题请纠正我指定一个变量项作为嵌套列表的第一项,嵌套列表遍历,将他们组合分配给第一个项目如果有一个列表,可以结合,然后删除符合条件的项目,直接进入下一个循环,这将确保每个循环可以合并一次,如果没有找到有效的组合这个循环结束时,项目是独立的,如果没有找到有效组合的循环,然后项目是独立的，可以添加到结果列表中并依次重复(这种方法对于大量数据可能不有效，寻找其他有效的解决方案)

def merge(intervals):
res = []
while len(intervals):
is_new = True
item = intervals[0]
for index in range(1, len(intervals)):
if set(item) & set(intervals[index]):
intervals[0] = list(set(item + intervals[index]))
intervals.pop(index)
is_new = False
break
if is_new:
res.append(intervals[0])
intervals = intervals[1:]
return res

print(merge([[0], [1], [0, 2, 3], [1, 2, 3, 4, 10], [4], [5], [6, 7, 8], [7], [6, 3], [9, 10]]))
print(merge([[0], [1], [0, 2, 3], [1, 2, 3, 4, 5], [4], [5], [6, 7, 8], [7], [6, 8]]))

# Output
# [[0, 1, 2, 3, 4, 6, 7, 8, 9, 10], [5]]
# [[0, 1, 2, 3, 4, 5], [8, 6, 7]]