# 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.