Skip to main content
 首页 » 编程设计

python之从索引对创建倍数的元组

2024年12月31日9itcoder

给定一个 numpy 数组,它可以是满足给定条件的数组元素的索引的子集。如何根据生成的索引对创建三元组(或四元组、五元组等)的元组?

在下面的示例中,pairs_tuples 等于 [(1, 0), (3, 0), (3, 1), (3, 2)]。 triplets_tuples 应该是 [(0, 1, 3)] 因为它的所有元素(即 (1, 0), (3, 0), (3, 1))都有满足条件的成对值,而 (3, 2)才不是。

a = np.array([[0.        , 0.        , 0.        , 0.        , 0.      ], 
              [0.96078379, 0.        , 0.        , 0.        , 0.      ], 
              [0.05498203, 0.0552454 , 0.        , 0.        , 0.      ], 
              [0.46005028, 0.45468466, 0.11167813, 0.        , 0.      ], 
              [0.1030161 , 0.10350956, 0.00109096, 0.00928037, 0.      ]]) 
 
pairs = np.where((a >= .11) & (a <= .99)) 
pairs_tuples = list(zip(pairs[0].tolist(), pairs[1].tolist())) 
# [(1, 0), (3, 0), (3, 1), (3, 2)] 

如何到达下面?

triplets_tuples = [(0, 1, 3)] 
quadruplets_tuples = [] 
quintuplets_tuples = [] 

请您参考如下方法:

这有一个简单的部分和一个 NP 部分。这是简单部分的解决方案。

假设您有完整的相关矩阵:

>>> c = a + a.T 
>>> c 
array([[0.        , 0.96078379, 0.05498203, 0.46005028, 0.1030161 ], 
       [0.96078379, 0.        , 0.0552454 , 0.45468466, 0.10350956], 
       [0.05498203, 0.0552454 , 0.        , 0.11167813, 0.00109096], 
       [0.46005028, 0.45468466, 0.11167813, 0.        , 0.00928037], 
       [0.1030161 , 0.10350956, 0.00109096, 0.00928037, 0.        ]]) 

您正在做的是将其转换为 adjacency matrix :

>>> adj = (a >= .11) & (a <= .99) 
>>> adj.astype(int)  # for readability below - False and True take a lot of space 
array([[0, 1, 0, 1, 0], 
       [1, 0, 0, 1, 0], 
       [0, 0, 0, 1, 0], 
       [1, 1, 1, 0, 0], 
       [0, 0, 0, 0, 0]]) 

这现在表示一个图表,其中列和行对应于节点,1 是它们之间的线。我们可以使用 networkx 将其可视化:

import networkx 
g = networkx.from_numpy_matrix(adj) 
networkx.draw(g) 

您要在此图中寻找最大的全连接子图或“团”。这是 the Clique problem , 并且是 NP 部分。值得庆幸的是,networkx 也可以解决这个问题:

>>> list(networkx.find_cliques(g)) 
[[3, 0, 1], [3, 2], [4]] 

这里 [3, 0, 1] 是你的三胞胎之一。