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

5

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

Based on this information I can set up an example:

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

There are a few key points that should be considered:

  • I can not allow Pessoa 1 to talk to Pessoa 2 if they have already talked at any other meeting. I'll give an example using 6 pessoas with max 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 can not exceed this amount.
  • I need to keep at least one meeting per person. But I must also make each person have a similar number of meetings, so as not to get too uneven. Of course there will be people with fewer meetings than the others, but as long as this difference is small, that's fine.
  • In addition to keeping the maximum number of people in each meeting, I also need to try to maintain a default number of people. For example, I need at least that most people can make a meeting and that is with 13 people each. If the other meetings are 8, 7, 5 or 2 people, it does not matter, but at least a good part of the meetings have the same number of participants, again not to be unfair.
  • I also need to keep a certain order of combination. When I bring everyone in the database, I need to sort them in the order of priority. The highest priority comes first, with more chance of having scheduled meetings.

Now, I tried some different logic but none worked:

First attempt

Take Pessoa 1 and combine it with all the others, to form 13 meetings per person. The problem is that Pessoa 1 will always have more meetings than the others, because as it is the first, there is no meeting yet, no one has spoken to anyone yet.

Second attempt

I tried to combine only uma meeting of each person and return to the first. For example: I am combining the Pessoa 1 meeting. I pass to the second person, third and so on until the last person. When you get to the last one, go back to the first person and see if you can still generate another meeting. It did not work as well because the number of people at each meeting was very uneven. Example: In a list of 120 people with 13 people in each meeting, there were already only two people per meeting by the 11th meeting.

Third Try

This attempt was based on combining one by one. I pick up the first person and add another, thus forming a meeting of two people. I do the same with the second person, third person, and so on until there are a 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 set of meetings for Pessoa 1 again, it will not have any more meetings to be generated, because everyone has already spoken with Pessoa 1 .

Objective

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

It may happen that you have meetings for two people, but the preference is that you always try to reach the maximum number 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 you have and so on, so it is normal for some to have less than the other and acceptable!

Further details

Note also that I will use ID's instead of sequence numbers. Instead of using 1,2,3,4 , I'll be using 46,12,13,10,1,9 that would be the id's of each person.

    
asked by anonymous 03.11.2014 / 19:46

2 answers

2

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

EX 50 people in 5 out of 10, we will soon be able to do 10 meetings, without anyone being 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 (we will soon have 10 more meetings) 1-6-11-16-21 26-31-36-41-46 2-7-12-17-22 etc.

Do the same with the key groups from 6 to 10 6-1 7-2 ... following the same analogy, assuming you number the members of the key groups from 1 to 5 for the first 5 and 6- 10 for the last ones, after setting the keys, just work as follows:

(for easy use I use x = 10).

example diagram example group key 4 = 16 17 18 19 20 where 16 = 1 17 = 2 18 = 3 19 = 4 and 20 = 5 in numerology 12345 is the first person in group key 1, the second of sec 2, a 3 of 3, 4 of 4, and 5 of 5 if it were 23456 would be: the second person of group1, 3 of 2 to 4 of 3 to 5 of 4 and the first of 6

group of ordinances

11111 22222 33333 44444 55555 66666 77777 88888 99999 xxxxx -

sequential group with 1 as the base

12345 13456 14567 15678 16789 1789x 189x2 19x23 1x2345 soon the 1 in the first group has already participated in all his 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

    
12.11.2014 / 13:24
1

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

link

    
12.08.2015 / 22:01