phpalgorithmoptimizationpartition-problem

Reputation: 593

How to partition combinations from three categories?

I have an array with recipes from 3 categories, breakfast, lunch and dinner. Each of these categories, have 10 unique recipes.

$recipes = [
    'breakfast' => [
        0 => [
            'title' => 'eggless waffles',
            'calorie' => 210,
        ],
        1 => [
            'title' => 'blueberry oatmeal',
            'calorie' => 161,
        ],
        ...
     ],
    'lunch' => [9],
    'dinner' => [9]
];

I'd like to sort and create a combination of 3 recipes for each day

$days = array_fill(0, 6, [1 => [], 2 => [], 3 => []]);

Each recipe has a calorie amount, and each final day should have a combination (consists of 1 breakfast, 1 lunch and 1 dinner) with recipes that was ordered by whichever 3 recipe combo hit closest to 500

For example, if day 1 combined recipes (breakfast, lunch and dinner) calorie totaled 660, and day 2 was 400. It's possible that switching breakfast from day 2, to day 1 might make both of them hit closest to 500, however it's possible that switching day 3 breakfast to day 1, and day 2 to day 3 might make all 3 hit closer to 500 as well.

So day 1, 2, 3, 4, 5, 6, and 7 should have 3 recipes (breakfast, lunch and dinner)

$final = [
    0 => [
        'breakfast' => [...],
        'lunch' => [...],
        'dinner' => [...],
    ],
     1 => [
        'breakfast' => [...],
        'lunch' => [...],
        'dinner' => [...],
    ],
    2 => [
        'breakfast' => [...],
        'lunch' => [...],
        'dinner' => [...],
    ],
    ...
];

It's been days since I've reached an impasse, and I cannot figure out how to go about sorting these arrays into a combination of 3 for each day. (I know I'm not providing a lot of code to go off of)

Edit 1: This is what I've got so far:

class Combinations {

    private $days;

    public function __construct(){
        $this->days = array_fill(1, 7, [1 => [], 2 => [], 3 => []]);
    }

    public function create(){
        $median = 600;

        foreach($this->days as $day => $categories){
            while($this->dayIsIncomplete($day)){
                $recipes = [];
                foreach($categories as $category => $value){
                    $recipes[$category] = $this->getRandomRecipe($category);
                }

                // add random meals to first day
                if($day === 1){
                    $this->days[$day] = $recipes;
                    continue;
                }

                foreach($recipes as $category => $recipe){
                    foreach($this->days as $dayKey => $mealsArray){
                        $originalMacros = $this->totalMacros($mealsArray);

                        // remove $recipe category from mealsArray, and merge it ($recipe)
                        $filteredMacros = $this->totalMacros(array_merge([$recipe], array_filter($mealsArray, function($key) use($category){
                            return $key !== $category;
                        }, ARRAY_FILTER_USE_KEY)));

                        // if original is not closer to median
                        if(($originalMacros - $median) * ($originalMacros - $median) < ($filteredMacros - $median) * ($filteredMacros - $median)){
                            // flip current recipes
                            // switch D2B ($recipe) with D1B
                        }
                    }
                }
            }
        }
    }

    public function getRandomRecipe(int $category){
        $recipes = []

        if($category === 1){
            $recipes[] = ['id' => 1, 'calorie' => 310];
            $recipes[] = ['id' => 2, 'calorie' => 360];
            $recipes[] = ['id' => 3, 'calorie' => 450];
            $recipes[] = ['id' => 4, 'calorie' => 330];
            $recipes[] = ['id' => 5, 'calorie' => 220];
            $recipes[] = ['id' => 6, 'calorie' => 390];
            $recipes[] = ['id' => 7, 'calorie' => 400];
            $recipes[] = ['id' => 8, 'calorie' => 320];
            $recipes[] = ['id' => 9, 'calorie' => 460];
        }

        if($category === 2){
            $recipes[] = ['id' => 10, 'calorie' => 420];
            $recipes[] = ['id' => 11, 'calorie' => 360];
            $recipes[] = ['id' => 12, 'calorie' => 450];
            $recipes[] = ['id' => 13, 'calorie' => 310];
            $recipes[] = ['id' => 14, 'calorie' => 320];
            $recipes[] = ['id' => 15, 'calorie' => 490];
            $recipes[] = ['id' => 16, 'calorie' => 440];
            $recipes[] = ['id' => 17, 'calorie' => 520];
            $recipes[] = ['id' => 18, 'calorie' => 560];
        }

        if($category === 3){
            $recipes[] = ['id' => 19, 'calorie' => 510];
            $recipes[] = ['id' => 20, 'calorie' => 660];
            $recipes[] = ['id' => 21, 'calorie' => 750];
            $recipes[] = ['id' => 22, 'calorie' => 610];
            $recipes[] = ['id' => 23, 'calorie' => 580];
            $recipes[] = ['id' => 24, 'calorie' => 690];
            $recipes[] = ['id' => 25, 'calorie' => 710];
            $recipes[] = ['id' => 26, 'calorie' => 620];
            $recipes[] = ['id' => 27, 'calorie' => 730];
        }

        return $recipes[array_rand($recipes)];
    }

    public function dayIsIncomplete($day){
       return !empty($this->days[$day][1]) && !empty($this->days[$day][2]) && !empty($this->days[$day][3]);
    }

    public function totalMacros($array){
        $total = 0;
        foreach ($array as $key => $value) {
            $total += $value['calorie'];
        }
        return $total / 2;
    }
}

Edit 2:

I'm trying to figure out what algorithm best fits to sort this issue out. I think using a bipartite matching (maximum) algorithm might be what I need.

Edit 3:

Thank you all for taking the time to help, I haven't forgotten about the answers. I had to put this aside for the time being, however soon enough I'll get to it, and the accepted answer will get my remaining 300 bounty.

Upvotes: 0

Answers (3)

Jannes Botis

Reputation: 11242

You have:

10 breakfasts
10 lunches
10 dinners

The combinations of these are 10x10x10 = 1000 recipes.

Part 1

Calculate these recipes and their total calories each.

From each recipes `s total calories, calculate the absolute difference from the daily calories goal:

AbsoluteDifference = Abs(calories - 500)

and which breakfast, lunch and dinner it consists of.

So now e.g. you have a list:

| Recipes   | AbsDiff | Breakfast | Lunch | Dinner |
| recipe 1  |  140    |  1        |   7   |  4 
| recipe 2  |  135    |  4        |   8   |  3
| recipe 3  |  210    |  7        |   9   |  10
 ... 
| recipe 1000 | 170   |  5        |   1   |  9

Part 2

This is the difficult part, by calculating all combinations of 7 recipes is gonna take too long.

The best combination is the one that has total of absDiff of its recipes the minimum:

MIN(AbsDiff(recipe1) + AbsDiff(recipe2) + AbsDiff(recipe7))

Algorithm

The idea is to calculate only a few combinations of 7 different recipes.

Initial Step

Make a guess of "how much the minimum could be about", e.g. say you think it is likely less than 350 calories.

Using this guess, you can try to calculate all the combinations of 7 recipes that have TotalCaloriesDiff < 350.

Based on:

In a collection of n positive numbers that sum up to or less than S, at least one of them will be less than S divided by n (S/n).

In this case S=350 and n=7, then at least one recipe should have AbsDiff < 350/7 = 50.

So, you could try to calculate combinations of 7 recipes with lower total differences to the guess.

Steps

Get the recipes with AbsDiff(recipe1) < 350 / 7
For each recipe1 found above, get the next recipes that have AbsDiff(recipe2) < (350 - AbsDiff(recipe1)) / 6 and they do not share any breakfast, lunch or dinner with recipe1.
continue till you get combinations of 7 recipes.
select the combination with lowest TotalCaloriesDiff

If you do not find any results, based on your guess, you raise the guess, e.g. 350 + 50 = 400.

Here is my answer to a similar problem.

Upvotes: 1

Olivier

Reputation: 18122

So I tested a genetic algorithm and it works. I used Jenetics, a Java library (it's not PHP, sorry, but PHP is not suited to heavy computations anyway).

I took 1400 calories as the daily target.

The function to be minimized is the mean squared error.

Here's the code:

import java.util.ArrayList;
import io.jenetics.*;
import io.jenetics.engine.*;
import io.jenetics.util.*;

public class Recipes
{
    private static final int TARGET = 1400;
    private static final int DAYS = 7;

    private static class Recipe
    {
        public int id;
        public int calories;

        public Recipe(int id, int calories)
        {
            this.id = id;
            this.calories = calories;
        }
    }

    private static ISeq<Recipe> getSeq(int[] ids, int[] calories)
    {
        ArrayList<Recipe> list = new ArrayList<>();
        for(int i=0;i<ids.length;i++)
            list.add(new Recipe(ids[i], calories[i]));
        return ISeq.of(list);
    }

    private static double meanSquareError(Genotype<EnumGene<Recipe>> gt)
    {
        int err = 0;
        for(int d=0;d<DAYS;d++)
        {
            int calories = 0;
            for(int m=0;m<3;m++)
                calories += gt.get(m).get(d).allele().calories;
            err += (calories-TARGET)*(calories-TARGET);
        }
        return err / (double)DAYS;
    }

    public static void main(String[] args)
    {
        ISeq<Recipe> recipes1 = getSeq(new int[]{ 1,  2,  3,  4,  5,  6,  7,  8,  9}, new int[]{310, 360, 450, 330, 220, 390, 400, 320, 460});
        ISeq<Recipe> recipes2 = getSeq(new int[]{10, 11, 12, 13, 14, 15, 16, 17, 18}, new int[]{420, 360, 450, 310, 320, 490, 440, 520, 560});
        ISeq<Recipe> recipes3 = getSeq(new int[]{19, 20, 21, 22, 23, 24, 25, 26, 27}, new int[]{510, 660, 750, 610, 580, 690, 710, 620, 730});

        Factory<Genotype<EnumGene<Recipe>>> gtf = Genotype.of(
            PermutationChromosome.of(recipes1, DAYS),
            PermutationChromosome.of(recipes2, DAYS),
            PermutationChromosome.of(recipes3, DAYS)
        );

        Engine<EnumGene<Recipe>, Double> engine = Engine
            .builder(Recipes::meanSquareError, gtf)
            .optimize(Optimize.MINIMUM)
            .populationSize(50)
            .alterers(new SwapMutator<>(0.2), new PartiallyMatchedCrossover<>(0.2), new Mutator<>(0.01))
            .build();

        Phenotype<EnumGene<Recipe>, Double> result = engine.stream()
            .limit(20000)
            .collect(EvolutionResult.toBestPhenotype());

        for(int m=0;m<3;m++)
        {
            for(int d=0;d<DAYS;d++)
            {
                Recipe r = result.genotype().get(m).get(d).allele();
                System.out.print(String.format("%2d (%d)  ", r.id, r.calories));
            }
            System.out.println();
        }
        System.out.println("MSE = " + result.fitness());
    }
}

A genetic algorithm is non-deterministic so it gives a different result each time. The best solution I could get is:

 3 (450)   4 (330)   5 (220)   2 (360)   7 (400)   1 (310)   8 (320)
16 (440)  15 (490)  17 (520)  10 (420)  13 (310)  11 (360)  14 (320)
19 (510)  23 (580)  20 (660)  26 (620)  24 (690)  27 (730)  21 (750)

MSE = 14.285714

It's almost perfect (all days are at 1400 calories except Sunday which has 1390).

Upvotes: 2

PawMaw

Reputation: 111

I think first you should make a combination of dishes, where calorie should be near to 500, to make them unice, like:

$arr = [
    0 => [
        'breakfast' => 160
        'lunch' => 160
        'dinner' => 180
    ],
...

You should rebuild array like $breakfast = ['1' => 130, '2' => 150, '3' => 160, '4' => 170, '5' => 120, '6' => 100, '7' => 130] and etc. Maybe try to compare arrays like

$final = ['1' => 152, '2' => 235, '3' => 521, '4' => 343, ... ];

And then you can grab each value from $arr ->

$final = ['1' => ['breakfast' => '1', 'lunch' => '5', 'dinner' => '2'], ...];

I think you can modify this logic as you want. Best of luck