How to partition people in a network of friends?

Question

In your class, many students are friends. Let’s assume that two students who share a friend should be friends; in other words, if students 0 and 1 are friends and students 1 and 2 are friends, then students 0 and 2 should be friends. Using this rule, we can partition students into circles of friends. To do this, implement a network() function, which accepts two input arguments. The first is the n number of students in the class. We consider that students are identified using integers 0 to n - 1. The second input argument is a list of tuple objects that define friends. For example, the tuple (0, 2) defines students 0 and 2 as friends. The network() function should display the partition of students in circles of friends, as we say:

>>> redes(5, [(0, 1), (1, 2), (3, 4)])

Rede social 0    is {0, 1, 2}

Rede social 1    is {3, 4}

What I did:

def redes(n,lista_tuplas):
    rede = []
    rede2 =[]
    for i in range(len(lista_tuplas) - 1):
        while set(lista_tuplas[i]).intersection(set(lista_tuplas[i+1])):
            rede += set(lista_tuplas[i]).union(set(lista_tuplas[i+1]))
            break
        rede2.append(lista_tuplas[i])
    return rede,rede2


n = 5
lista_tuplas = [(0,1),(3,5),(3,6)]
print(redes(n,lista_tuplas))

The problem is that the code misses when there are no friends in common. My output with the above data was:

([3, 5, 6], [(0, 1), (3, 5)])

The first partition is correct but the second is not: (3, 5) should not have entered the second partition! Can anyone help me figure out what I’m missing? How to correct?

Answer 1

I created a solution using set and for...else... Yes, that for...else may seem very strange but when you understand what it’s for it can be very useful, as is the case...

Steps to solving the problem:

1. Create a list of social groups;
2. Scroll through all received relationships as argument;

3. Test if any of the students in each relationship are already in some group

   • If at least one of the students is already in a group, add both in the group (as we are working with set there will be no duplicate students in the group);

   • If both students are not in any group, create a new group with both students.

4. Return the resulting group list

Code:

def redes(relacionamentos):
    grupos = []

    for rel in relacionamentos:
        rel = set(rel)

        for grupo in grupos:
            if grupo & rel:
                grupo |= rel
                break
        else:
            grupos.append(rel)

    return grupos

PS: I purposely ignored the number of students proposed in the exercise because it makes no difference in the algorithm, except perhaps the validation of the received tuples.

---

Explanation

for...else

If you check the documentation you will find the following:

Loop statements may have an Else clause; it is executed when the loop Terminates through exhaustion of the iterable (with for) or when the condition Becomes false (with while), but not when the loop is terminated by a break statement.

Free translation:

Repeat loops may have a clause else; this will be executed when the loop ends by the exhaustion of the eternal (with for) or when the condition becomes false (with while), but not when the loop is ending through a break.

So what I did in my code is I went through all the social groups that exist up to that point, and if any of the students are part of some group, add both to the group and get out of the loop using break, that way you won’t fall in else.

However, if, after going through all the groups, students do not yet belong to any of the groups Python will run the block else where I create a new group with students.

Examples:

• for...else:

  If you iterate to the end, you enter else:

  for i in range(5):
      print(i, end=" ")
  else:
      print("\n[O for executou até o fim sem interrupção]")
  

  Exit

  0 1 2 3 4
  [O for executou até o fim sem interrupção]
  

  If interrupted by a break:

  for i in range(5):
      break
  else:
      print("[Nunca ocorrerá por causa do break]")
  

  The above code does not print anything on the screen as it does not enter the else.

• while...else:

  If you iterate to the end, you enter else:

  i = 0
  while i < 5:
      print(i, end=" ")
      i += 1
  else:
      print("\n[O while executou até o fim sem interrupção]")
  

  Exit

  0 1 2 3 4
  [O while executou até o fim sem interrupção]
  

  If interrupted by a break:

  i = 0
  while i < 5:
      break
  else:
      print("[Nunca ocorrerá por causa do break]")
  

  The above code does not print anything on the screen as it does not enter the else.

^{Code running on Repl.it}

---

Full code with examples mentioned in the question

def redes(relacionamentos):
    grupos = []

    for rel in relacionamentos:
        rel = set(rel)        # transformo a tupla em set

        for grupo in grupos:
            if grupo & rel:   # se um dos alunos está no grupo
                grupo |= rel  # adiciona os alunos ao grupo
                break         # sai do for
        else:
            grupos.append(rel)

    return grupos


exemplos = [
    [(0, 1), (1, 2), (3, 4)],  # Primeiro exemplo da pergunta
    [(0, 1), (3, 5), (3, 6)],  # Exemplo com erro na pergunta
]

print(f">>> redes({exemplos[0]!r})")
resultado_1 = redes(exemplos[0])
for i, grupo in enumerate(resultado_1, start=1):
    print(f"Grupo {i}: {grupo!r}")

print(f"\n>>> redes({exemplos[1]!r})")
resultado_1 = redes(exemplos[1])
for i, grupo in enumerate(resultado_1, start=1):
    print(f"Grupo {i}: {grupo!r}")

^{Code running on Repl.it}

Exit:

>>> redes([(0, 1), (1, 2), (3, 4)])
Grupo 1: {0, 1, 2}
Grupo 2: {3, 4}

>>> redes([(0, 1), (3, 5), (3, 6)])
Grupo 1: {0, 1}
Grupo 2: {3, 5, 6}

Answer 2

In fact, just change the while for if since your logical test is excluding. See:

def redes(n,lista_tuplas):
    rede = []
    rede2 =[]
    for i in range(len(lista_tuplas) - 1):
        if set(lista_tuplas[i]).intersection(set(lista_tuplas[i+1])):
            rede += set(lista_tuplas[i]).union(set(lista_tuplas[i+1]))
        else:
            rede2.append(lista_tuplas[i])
    return rede,rede2


n = 5
lista_tuplas = [(0,1),(3,5),(3,6)]
print(redes(n,lista_tuplas))

Output:

([3, 5, 6], [(0, 1)])

That said, I think your solution still has some problems:

1) Why n is a function argument if you do not use?

2) The way your code is, it is only possible to identify networks if the circles with common friends are adjacent. Noted this?