18
Sep

# Grouping Algorithm

This is an algorithm which, when given a list
of friends and mutual friends can find the largest group of people in which all of the
people know each other. So now I’m going to run the program. Say I’m friends with A, B,
C, D, E, F, and G. A is friends with C, D, and E, B is friends with F and G, C is friends
with A, D is friends with A, E is friends with A. F is friends with B and G, and G is
friends with B and F. So the largest group is F and B and G. And whenever I refer to
a group, that’s a group in which everyone knows each other. So here’s how the code works.
It splits up the list of friends, and it splits up the list of mutual friends into separate
arrays that map to each other. Then, it orders both of those arrays based off of number of
mutual friends, from most mutual friends to least mutual friends. And then it starts to
put them into groups. This procedure is repeated for every friend: The friend is put into a
new group. The list of mutual friends is checked in order. Each time a friend’s mutual friends
contain all of the members of the group being formed, that friend is added to the group.
Each potential grouping gets put into an array. Then, it sorts the groups from largest to
smallest. Then it outputs the largest group. This is a version of the previous algorithm,
which, rather than taking an input of friends and mutual friends, takes an input of number
of friends, and randomly generates the rest. So here’s a couple of examples of it being
used. It’s not perfect, but I used it to mimic an “average case” scenario for my complexity
analysis. I found the average number of steps it took for every ten numbers between one
and a hundred, and also numbers one through ten, and I found a function that fit that
graph. It’s not perfect, it’s obviously a little off from the dots, but it’s pretty
close. Um, as you can see when looking at it, it’s the dotted line right there, and
the green points are the points from my tests. So here’s my results from the previous algorithm,
and the green line, the lowest line, shows the number of steps it takes when nobody is
friends with each other, so it’s a very low number of steps, and the red line is when
everybody is friends with each other, and the orange line is the average case, when
half the people are all friends with each other. The purple line is the previous function
from the other one, and it matches up really well with the average case. So, that’s my
algorithm.

Tags: , , ,