Join a number of people without repeating the combination with the stipulated maximum

Question

I have N pessoas to form as many meetings as possible. These N pessoas cannot speak to those who have already spoken at other meetings. Each meeting has at most N pessoas.

Based on this information I can set an example:

$pessoasIds = array(1,2,3,4,5,6,7,8,9...120); // Até 120 pessoas
$maxPessoas = 13; // 13 pessoas por reunião

Has some key points that should be considered:

• I cannot allow the Pessoa 1 talk to the Pessoa 2 if they have already spoken at any other meeting. I will give an example using 6 pessoas with at most 3 por reunião An example would be this:

    $reunioes = array(
        0 => array(1, 2, 3),
        1 => array(1, 4, 5),
        2 => array(1, 6),
        3 => array(2, 4, 6), // a pessoa número 2 ja conversou com a pessoa número 3 e 1 e a pessoa número 4 com a 5
        4 => array(2, 5) 
    );

• I need to keep the maximum number of people per meeting and I can’t exceed this amount.
• I need to hold at least one meeting per person. But I also need to make sure each person has a similar number of meetings, so it doesn’t get too uneven. Of course there will be people with fewer meetings than others, but as long as that difference is small it’s okay.
• In addition to keeping the maximum number of people in each meeting, I also need to try to maintain a standard number of people. For example, I need at least for most people to be able to have a meeting with 13 people each. If the other meetings are 8, 7, 5 or 2 people have no problem, but at least a good part of the meetings have equal number of participants, again not to be unfair.
• I also need to maintain a certain order of combination. By bringing everyone from the database, I need to sort them in order of priority. The highest priority comes first, with more chance of having scheduled meetings.

Now, I tried some different logics but none worked:

First Attempt

Catch the Pessoa 1 and combine with all others, until forming 13 meetings per person. The problem is that the Pessoa 1 will always have more meetings than the others, because as is the first, there is still no meeting, no one talked to anyone yet.

Second Attempt

I just tried to combine uma meeting of each person and back to the first. For example: assemble the combination of the meeting of Pessoa 1. Step to the second person, third and so on. When you get to the last one, go back to the first person and see if it’s still possible to generate another meeting. It didn’t work either because the number of people in each meeting was very uneven. Example: In a list of 120 people with 13 people in each meeting, by the 11th meeting there was forming only two people per meeting.

Third Attempt

This attempt was based on combining one by one. I took the first person and added another, thus forming a meeting of two people. I do the same with the second person, third person and so on until I reach the maximum of people per meeting in each one. The problem of this attempt I show below, which I will put as an example in PHP:

$reunioes = array(
    1 => array(1,2), // reunião da pessoa número 1
    2 => array(2,3), // reunião da pessoa número 2 e etc...
    3 => array(3,1)
    4 => array(4,1),
    5 => array(5,1)
    // ...
);

When I try to generate the next round of meetings to Pessoa 1 again, it will not have any more meeting to be generated, because everyone has already talked to the Pessoa 1.

Goal

The ultimate goal is to form meetings with the average of similar people in each group, respecting all the 'rules' I wrote in the question

It can happen to have meetings of two people, but the preference is that always try to reach the maximum of people in a meeting, which in the example I gave is 13. If the given limit is 5 people per meeting, the ideal would be that all meetings were with 5 people, but that depends on how many people have and etc, then it is normal that some have less than others and acceptable!

Other details

Also note that I will use ID’s and not sequential numbers. Rather than use 1,2,3,4, I’ll be using 46,12,13,10,1,9 that would be the ID’s of each person.

Answer 1

First take the number of people and divide by the maximum:

EX 50 people in 5 of the 10, soon we can make 10 meetings, without anyone was present in two.

EX(key groups): 1-5, 6-10, 11-15 16-20, 21-25 26-30, 31-35 36-40, 41-45 46-50 after that take one person from each key group (soon we will have 10 more meetings) 1-6-11-16-21 26-31-36-41-46 2-7-12-17-22 etc

do the same thing with the key groups 6 to 10 6-1 7-2... following the same analogy, assuming that you will not add the members of the key groups from 1 to 5 to the first 5 and from 6 to 10 to the last, after establishing the keys just work as follows:

(I will use x=10 to make it easier).

visualization scheme example key group 4 = 16 17 18 19 20 where 16=1 17=2 18=3 19=4 and 20=5 in numerology 12345 is first person of key group 1, the second person of the 2, the third of the 3, the fourth of the 4, and the fifth of the 5 if it were 23456 would be: the second person of group 1, 3 from 2 to 4 from 3 to 5 from 4 and the first from 6

group of wages

11111 22222 33333 44444 55555 66666 777 888 99999 xxxxx -

group of sequences with 1 as the basis

12345 13456 14567 15678 16789 1789x 189x2 19x23 1x2345 soon the 1 of the first group already attended all its meetings - repeat the previous groups now using 2,3,4,5,6,7,8,9,x as base:

21354 23547 25476 24769 27698 2698x 298x1

and follow the same analogy or form arrangements for your groups, without repetition

Answer 2

I did something similar, but to get only the available people without them having to confront each other in the same spot, I hope it helps you:

http://ideone.com/KNYZYU