How can I distribute x cakes amongst y people?

I have an array with the ids of x cakes and another associative array with the ids of y people. I want to ensure that each cake is enjoyed by exactly 2 people and that each person gets a fair share of cake overall. However, cakes must be kept whole (i.e. if the average cake per person is a fraction, this fraction will be rounded up for some, and down for others). No person can be assigned the same cake twice. For example:

$cake = array(''1','2')
$people = array('1','2','3')

In order to do so, I wish to create a new array where each row represents a cake-person assignment. As each cake is being assigned to two people, the number of rows in this table should be exactly twice the number of cakes. There will not be exactly 1 solution to this problem but a solution to the above example would be:

$cake_person = array(
    '1'=>array('1', '1'),
    '2'=>array('1', '2'),
    '3'=>array('2', '2'),
    '4'=>array('2', '3'),
    )

Notice that people 1 and 3 are losing out but that is because there is no more cake to go around! Each cake must be given exactly twice.

How can I generate such a solution reliably for larger numbers of people and cakes?

Having implemented Artefacto's useful response, I've dec开发者_如何学运维ided to post my code below just in case anybody else finds it useful.

Data

//Create people array with 25 people
$people = range(1,25);

//Create cake array with 77 cakes
$cake = range(1,77);

Code

$people_cakes = array();
$totalPeople = count($people);
$idp = 0;

foreach($cakes as $cake) {
    $id1 = $idp % $totalPeople;
    $id2 = ($idp + 1) % $totalPeople;
    $people_cakes[] = array($people[$id + 1], $cake);
    $people_cakes[] = array($people[$id + 2], $cake);

    $idp = $idp + 2;
    }

Implement an algorithm that iterates through the cakes and assigns parts in order:

• Start with idp = 0
• Iterate through the cakes
  • Give the first hald to person stored in position (idp mod total persons) of the persons' array.
  • Give the second half to person stored in position ((idp+1) mod total persons) of the persons' array.
  • Sum 2 to idp

This will not give the same result as your example (person 1 will get two halves), but that was not a requirement.

Example script:

$cakes = range(1, 77);
$people = range(1,25);

$result = array();
$idp = 0;
foreach ($cakes as $cid) {
    $result[] = array(
        'cake_id' => $cid,
        'person_id' => $people[$idp % count($people)],
    );
    $result[] = array(
        'cake_id' => $cid,
        'person_id' => $people[($idp+1) % count($people)]
    );
    $idp += 2;
}


$total = array();
foreach ($result as $a) {
    if (!array_key_exists($a['person_id'], $total)) {
        $total[$a['person_id']] = 0;
    }
    $total[$a['person_id']]++;
}

var_dump($total); //gives the number of halves per person

I haven't tested it but I think it should work

Let's take the example of 77 cakes and 25 people.

If each cake is eaten by 2 people, to feed 25 people you need 12.5 cakes. We'll be generous and make it 13 (i.e. use ceiling)

So, you have 77 cakes, that means you can give 77 / 13 = 5.92 cakes to each person. We round that down and get 5. In order to generalise I will call this minCakes

So at this point you know everyone should get at least minCakes cakes. There will be some more that you can redistribute.

So now you iterate over the persons 2 at a time and

give person 1 and person 2 cakes from 1 to minCakes

give person 3 and 4 cakes from minCakes + 1 to minCakes * 2 + 1

....

In our case person 25 is alone :(, so he will get his minCakes cakes and give half to people number 1 to minCakes.

Essentially persons n and n+1 will have cakes minCakes * floor(n/2) + 1 to minCakes * floor(n/2) + minCakes

If the number of people is odd you process the last one separately, as you have to distribute the other half of the cakes to other minCakes people.

Now it's time to distribute what's left. In our case 5 * 24/2 = 60 plus the 5 cakes for person 25 gives us a grand total of 65 cakes used, so 77 - 65 = 12 cakes left.

You start to distribute those from either number 1 (if the number of people was even) or, like in our case, from number minCakes+1 (as the first ones have already had their extra share).

Now you just iterate again over the people 2 at a time and assign them half cake. If you get to number 25 just loop back to 1.