基于关系的矩阵分组

本文介绍了基于关系的矩阵分组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我陷入了根据矩阵关系来解决矩阵分组问题的问题.

I got into problem to solve matrix grouping problem based on its relation.

问题

请考虑一群互相提供书籍的人.更正式地说，小组由彼此认识的所有人组成，无论是直接认识还是传递.

Consider a group of people giving books to each other. More formally, group is composed of all the people who know one another, whether directly to transitively.

示例

考虑输入矩阵 M

Consider a matrix of input M

输入

输出:

有n = 4个人编号为related [0]至related [3].
有两对彼此直接认识的:( related [0]，相关[ 1 ])和(相关[ 1 ]，相关[2]).因为关系是可传递的，一组人{related [0]，相关[ 1 ]，相关[2]}是被认为是一个单一的群体.
与[3]相关的其余人不认识任何其他人，并且是一个单独的组:{related [3]}
共有2个小组.

There are n = 4 people numbered related[0] through related[3].
There are 2 pairs who directly know each other: (related[0],related[1]) and (related[1], related[2]). Because a relation istransitive, the set of people {related[0], related[1], related[2]} isconsidered a single group.
The remaining person, related[3], does not know any other people andis a separate group: {related[3]}
There are a total of 2 groups.

示例

输入:

输出:

未显示直接关系，因此有5组:{相关[0]，相关的[ 1 ]，相关的[2]，相关的[3]，相关[4]}

No direct relationship are shown so there are 5 groups: {related[0], related[1], related[2], related[3], related[4]}

示例

输入

输出

有两对彼此直接认识的:( related [0]，相关[ 1 ])和(相关[ 1 ]，相关[2]).因为关系是可传递的，一组人{related [0]，相关[ 1 ]，相关[2]}是被认为是一个单一的群体.
有一对直接互相认识的对:(相关[4]，相关[5]).因此，它们被视为单个组{related [4]，related [5]}
与[3]，[6]相关的其余人不认识任何其他人，并且是一个单独的组:{related [3]}，{related [6]}
共有4个组:{{related [0]，related [ 1 ]，相关[2]}，{相关[4]，相关[5]}，{相关[3]}，{相关[6]}}

There are 2 pairs who directly know each other: (related[0],related[1]) and (related[1], related[2]). Because a relation istransitive, the set of people {related[0], related[1], related[2]} isconsidered a single group.
There is 1 pair who directly know each other: (related[4], related[5]). So they are considered as single group {related[4], related[5]}
The remaining person, related[3], related[6] does not know any other people andis a separate group: {related[3]}, {related[6]}
There are total 4 group : {{related[0], related[1], related[2]}, {related[4], related[5]}, {related[3]}, {related[6]} }

我需要有关如何解决此类问题的帮助.

I need help with how to approach with this kind of problems.

代码(我尝试未完成)

def countGroup(matrix):
    people = set()
    group1 = set()
    for i in range(len(matrix)):
        people.add(i) 
        for j in range(len(matrix)):
            if i == j:
              # next
              continue
            if matrix[i][j]:
                group1.add((i,j))
                people.discard(i)
                people.discard(j)
                # group1.add(i)
                # group1.add(j)
    print(people, "people")
    print(group1, "group1")
    count = len(people)
    if group1:
        count += 1

    return count

推荐答案

您几乎在那里，问题是if不太正确，您需要更多地使用集合.尚未测试代码，但应该进行一些细微调整，我的python有点生锈.

Your almost there, the issue is the if isn't quite right, and you need to make more use of sets. Haven't tested the code but should work with perhaps a few minor tweaks, my python is a bit rusty.

def countGroup(matrix):
    people = set()
    group1 = set()
    for i in range(len(matrix)):
        people.add(i) # Quick way to build a list of all the people
        for j in range(len(matrix)):
            if i == j: # Not useful, you should know yourself. 
              # Could avoid this by using itertools.combinations
              continue
            if matrix[i][j] == 1: # we just want to know
                group1.add(i)
                group1.add(j)
    group2 = people - group1 # Anyone not in group1 is in group2.

    return (group1, group2)

这篇关于基于关系的矩阵分组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！