从 matrix/list 创建距离矩阵

Question

我已经根据输入创建了一个列表，我还从该列表创建了一个矩阵。列表-

('A', 'B', 3)
('A', 'D', 4)
('B', 'D', 4)
('B', 'H', 5)
('C', 'L', 2)
('D', 'F', 1)
('F', 'H', 3)
('G', 'H', 2)
('G', 'Y', 2)
('I', 'J', 6)
('I', 'K', 4)

矩阵-

 ['A' 'B' '3']
 ['A' 'D' '4']
 ['B' 'D' '4']
 ['B' 'H' '5']
 ['C' 'L' '2']
 ['D' 'F' '1']
 ['F' 'H' '3']
 ['G' 'H' '2']
 ['G' 'Y' '2']
 ['I' 'J' '6']
 ['I' 'K' '4']

但是我想从上面的矩阵或列表创建一个距离矩阵，然后打印距离矩阵。实施它的正确方法是什么。在上面的矩阵中，前两个节点代表起始节点和结束节点，第三个节点是距离。如果 required.A 样本距离矩阵是 -

，我准备好进一步说明

[[0, 10, 15, 20], 
 [10, 0, 35, 25],
 [15, 35, 0, 30], 
 [20, 25, 30, 0]]

Answer 1

由于您没有表现出任何尝试，这里有一些帮助您入门的想法。

将字符转换为数字，例如索引位置： ord('C') - ord('A')
创建矩阵：如果你想要一个固定大小的 pre-allocated 矩阵，而不是具有灵活大小的列表中的列表，库 numpy 可以帮助你。然后您可以在循环访问数据时访问字段并设置值。
如果你真的对分析网络感兴趣，你可以看看networkx。

请以这些想法为出发点，并根据您在尝试解决问题时遇到的更精确的障碍来完善您的问题。

Answer 2

我认为这道题不能作为家庭作业，因为它有一个特定的格式，比如 ("A" , "B" , 3) 对我来说不是正交的，所以我决定帮助你。但是最好实现另一个解决它的想法来帮助自己编码。一种方法是为每个字符分配一个数字，然后您可以使用与字母关联的数字指定距离矩阵的行和列！例如，将 'A' 估算为 1，将 'B' 估算为 2，依此类推：

A┌ 0 3 0 ┐      1┌ 0 3 0 ┐
B| 3 0 0 |────► 2| 3 0 0 |
C└ 0 0 1 ┘      3└ 0 0 0 ┘

所以在这个例子中，1代表“A”等等。那么这有什么帮助呢？示例：我们有一个像 ('A', 'B', 3) 这样的模式，我认为它是 (1, 2, 3) 然后我可以使用每个元组的前两个值在距离矩阵中进行索引寻址：

                                                       2
                                                    ┌─────────────┐
                                 Distance Matrix   1│  3   ...    │
('A', 'B', 3)─────► (1, 2, 3)    ───────────────►   │.     .      │
                                                    │.      .     │
                                                    │.       .    │
                                                    └─────────────┘

首先，我将按照您提到的那样创建一个输入列表。我将其命名为 lis:

lis = [('A', 'B', 3),
        ('A', 'D', 4),
        ('B', 'D', 4),
        ('B', 'H', 5),
        ('C', 'L', 2),
        ('D', 'F', 1),
        ('F', 'H', 3),
        ('G', 'H', 2),
        ('G', 'Y', 2),
        ('I', 'J', 6),
        ('I', 'K', 4)]

然后我使用 set 和 set.union 检测 lis 中的唯一字母。考虑我们在每个元组的第一个和第二个参数中都有字母：

items = set.union(set([item[0].upper() for item in lis]) , set([item[1].upper() for item in lis]))

然后我会制作一个字典，根据英文字母的顺序为每个字母赋值：

value = dict(zip(sorted(items), range(26)))

然后我将使用 numpy.zeros:

创建一个零矩阵

import numpy as np

dist_matrix = np.zeros((len(items) , len(items)))

最后一步是将每个元组的第三个值分配给距离矩阵中的相关位置：

for i in range(len(lis)):

    # for Upper triangular 
    dist_matrix[value[lis[i][0]] , value[lis[i][1]]] = lis[i][2]
    # for lower triangular
    dist_matrix[value[lis[i][1]] , value[lis[i][0]]] = lis[i][2]

    """
    Example:
    [0 3 0]
    [3 0 0]
    [0 0 0]
    """

dist_matrix

这给了我：

array([[0., 3., 0., 4., 0., 0., 0., 0., 0., 0., 0., 0.],
       [3., 0., 0., 4., 0., 0., 5., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 2., 0.],
       [4., 4., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 1., 0., 0., 3., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 2., 0., 0., 0., 0., 2.],
       [0., 5., 0., 0., 3., 2., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 6., 4., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 6., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 4., 0., 0., 0., 0.],
       [0., 0., 2., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 2., 0., 0., 0., 0., 0., 0.]])

附录

所有代码一览：

import numpy as np

lis = [('A', 'B', 3),
        ('A', 'D', 4),
        ('B', 'D', 4),
        ('B', 'H', 5),
        ('C', 'L', 2),
        ('D', 'F', 1),
        ('F', 'H', 3),
        ('G', 'H', 2),
        ('G', 'Y', 2),
        ('I', 'J', 6),
        ('I', 'K', 4)]

items = set.union(set([item[0].upper() for item in lis]) , set([item[1].upper() for item in lis]))
value = dict(zip(sorted(items), range(26)))
dist_matrix = np.zeros((len(items) , len(items)))

for i in range(len(lis)):

    # for Upper triangular 
    dist_matrix[value[lis[i][0]] , value[lis[i][1]]] = lis[i][2]
    # for lower triangular
    dist_matrix[value[lis[i][1]] , value[lis[i][0]]] = lis[i][2]

    """
    Example:
    [0 3 0]
    [3 0 0]
    [0 0 0]
    """

dist_matrix

从 matrix/list 创建距离矩阵

Creating a distance matrix from a matrix/list

euclidean-distance

python-3.x

distance-matrix

附录