How can I distribute x cakes amongst y people?
- by Rupert
I have an associative 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('id'=>'1','id'=>'2')
$people = array('id'=>'1','id'=>'2','id'=>'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('cake_id'=>'1', 'person_id'=>'1'),
'2'=>array('cake_id'=>'1', 'person_id'=>'2'),
'3'=>array('cake_id'=>'2', 'person_id'=>'2'),
'4'=>array('cake_id'=>'2', 'person_id'=>'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?
