How to split an array based on a condition?

Question

I'm working on a PHP/MySQL app and I have a very simple table that looks like this:

id | name | came_with
1    John    null
2    Jane    1
3    Dean    null

It has about 50 records but the main idea is that it stores people who register for an event, if they bring guests their name also gets stored with the id of the person who invited them in the came_with field, very simple.

I have to shuffle these names up and split them in X number of groups based on how many persons I want in each group which would be very easy since I can store each record in an array, use shuffle to randomize the order and the use array_chunk to generate smaller arrays depending on the number of persons.

The problem is that I can't have people who came together on the same group, so in this example John and Jane can't be on the same group, it's ok though for a person who came with 2 more to get placed on the same group if I choose to generate 2 groups since there's no choice. I'm VERY lost in what the logic should be to try to do this, I'm not asking for the exact code but for ideas in how to accomplish it.

Thanks in advance!