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

问题描述

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

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]).因为关系是可传递的,一组人{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.

示例

输入:

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]).因为关系是可传递的,一组人{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)
      

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

10-11 00:28