基于关系的矩阵分组 [英] Matrix grouping based on relation

问题描述

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

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

输入

1100
1110
0110
0001

输出:

2

• 有n = 4个人编号为related [0]至related [3].
• 有两对彼此直接认识的:( related [0]，相关[ 1 ])和(相关[ 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 is transitive, the set of people {related[0], related[1], related[2]} is considered a single group.
• The remaining person, related[3], does not know any other people and is a separate group: {related[3]}
• There are a total of 2 groups.

示例

输入:

10000
01000
00100
00010
00001

输出:

5

未显示直接关系，因此有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]}

示例

输入

1100000
1110000
0110000
0001000
0000110
0000110
0000001

输出

4

• 有两对彼此直接认识的:( related [0]，相关[ 1 ])和(相关[ 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 is transitive, the set of people {related[0], related[1], related[2]} is considered 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 and is 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)

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