python - 没有嵌套循环的邻接矩阵

Question

我正在尝试为一组团队成员创建一个邻接矩阵。我已经像这样存储了匹配详细信息-

 x={'match1':[1,2,3],'match2':[2,3,4],'match3':[3,4,5]}

此处每个关键字都有一个值列表，其中包含为该场比赛出战的队员。

我正在尝试创建一个邻接矩阵，显示每个团队成员与另一个团队成员进行了多少场比赛

输出应该是这样的

  1 2 3 4 5
1 1 1 1 0 0
2 1 2 2 1 0
3 1 2 3 2 1
4 0 1 2 2 1 
5 0 0 1 1 1

(i,i) 矩阵中的元素是该团队成员参加的比赛总数。我已经能够使用 Counter 正确计算这些值。

from collections import defaultdict, Counter

if __name__=='__main__':
    x = {'match1': [1, 2, 3], 'match2': [2, 3, 4], 'match3': [3, 4, 5]}
    d = defaultdict(list)
    col_count = dict()
    for key, value in x.items():
        for i in value:
            d[i] += value
    for key, value in d.items():
        col_count[key] = Counter(d[key])
    print(col_count)

输出是:

{1: Counter({1: 1, 2: 1, 3: 1}), 2: Counter({2: 2, 3: 2, 1: 1, 4: 1}), 3: Counter({3: 3, 2: 2, 4: 2, 1: 1, 5: 1}), 4: Counter({3: 2, 4: 2, 2: 1, 5: 1}), 5: Counter({3: 1, 4: 1, 5: 1})}

鉴于 x 字典将包含大量键，并且每个键都有一个包含许多元素的列表，我希望避免使用嵌套的 for 循环。

是否可以将匹配详细信息存储为任何其他数据类型，以便后续计算不需要嵌套循环？

如果字典是最好的方法，是否可以通过其他方式计算矩阵？

Answer 1

在不修改输入和输出格式的情况下，我看不出如何避免嵌套循环，因为您有按比赛分组的信息，并且您想按播放器提取它。您实际上可以做的是通过在嵌套循环内创建 Counter 来避免最后一个循环:

from collections import defaultdict, Counter

if __name__=='__main__':
    x = {'match1': [1, 2, 3], 'match2': [2, 3, 4], 'match3': [3, 4, 5]}
    d = defaultdict(Counter)
    for key, value in x.items():
        for i in value:
            d[i].update(value)
    print(d)

如果可以修改输入，您可以执行以下操作:

from collections import Counter

if __name__=='__main__':
    x = {1: [{1, 2, 3}], 2: [{1, 2, 3}, {2, 3, 4}], 3: [{1, 2, 3}, {2, 3, 4}, {3, 4, 5}], 4: [{2, 3, 4}, {3, 4, 5}], 5: [{3, 4, 5}]}
    d = {player: Counter([p for match in matches for p in match]) for player, matches in x.items()}
    print(d)

将嵌套循环换成字典和列表推导式，这样效率更高。可能玩家和比赛不是 int 和 int 的 list，所以这可以做得更可读。例如:

from collections import defaultdict, Counter

def printMatrix(matrix):
    print(' '.join(['   |'] + list(map(str, matrix.keys()))))
    print('---+-' + '-'*len(matrix)*2)
    for row, values in matrix.items():
        fmt = ' {row} |'
        for col in matrix.keys():
            fmt += ' {values[' + str(col) + ']}'
        print(fmt.format(row=row, values=values))

class Entity:
    def __init__(self):
        self._id = None

    @classmethod
    def register(cls, value):
        if value in cls.ids:
            raise ValueError("The provided ID is already in use")
        cls.ids.add(value)

    @classmethod
    def unregister(cls, value):
        if value is not None:
            cls.ids.remove(value)

    @property
    def id(self):
        return self._id

    @id.setter
    def id(self, value):
        if value == self.id:
            return
        self.register(value)
        self.unregister(self.id)
        self._id = value

class Player(Entity):
    ids = set()

    def __init__(self, pid):
        super().__init__()
        self.id = pid
        self.__matches = set()

    def __repr__(self):
        return 'Player<{}>'.format(self.id)

    @property
    def matches(self):
        return set(self.__matches)

    def inscribe(self, match):
        if match not in self.__matches:
            self.__matches.add(match)

    def delist(self, match):
        self.__matches.remove(match)

class Match(Entity):
    ids = set()

    def __init__(self, mid, players):
        super().__init__()
        self.id = mid
        self.__players = set()
        self.players = players
        for player in players:
            player.inscribe(self)

    def __repr__(self):
        return 'Match<{}>'.format(self.id)

    @property
    def players(self):
        return set(self.__players)

    @players.setter
    def players(self, value):
        for player in self.__players:
            player.delist(self)
        self.__players = set(value)
        for player in self.__players:
            player.inscribe(self)

if __name__=='__main__':
    players = [Player(i) for i in range(1, 6)]
    matches = [Match(i, {players[i-1], players[i], players[i+1]}) for i in range(1, 4)]

    for player in players:
        print(player, player.matches)

    for match in matches:
        print(match, match.players)

    d = {player.id: Counter([p.id for match in player.matches for p in match.players]) for player in players}
    printMatrix(d)

printMatrix() 函数只是我用来将输出漂亮地打印到屏幕上的一个助手。

Entity 类避免了 Player 和 Match 类都需要的重复代码，因为它们都有唯一的 ID。构造函数创建一个空的 _id 属性。 register() 和 unregister() 方法处理从类属性 ids 添加和删除 ID。它还声明了 id 属性及其 getter 和 setter。子类只需要在构造函数中调用 super().__init__() 并在要强制执行 ID 唯一性的级别创建 ids 类属性，如Player 和 Match 都在做。

Player 类还具有 matches 实例只读属性，该属性使用 inscribe() 和 delist 进行填充和删除() 方法。 Match 类具有 players 属性及其 getter 和 setter 方法。

首先 players 和 matches 是用两个列表理解创建的(记住列表从位置 0 开始，所以 Player 的 ID 为 1位于players[0]) 并打印出他们的对应关系(他们为球员参加的比赛和参加比赛的球员)。

由于两者都保持对另一种类型的引用，我们可以从 players 获取构建 Counter 的 dict 所需的所有信息。