How to find the best match (set of options) among several sets of options?

by QuantiumTech   Last Updated August 28, 2018 15:05 PM

Imagine a couple dozen services (sets of options), each of which contains a subset of all available options. I want to create a web form listing all possible options so that users can check the boxes for the options they want, then, after the form is submitted, return a report listing the services from best match to worst.

As an example, consider all the different TV services available- cable, satellite, streaming... how could I setup a page that allows a user to say, "out of 350 channels, these are the 10/20/35 that I actually watch" (check the checkboxes, submit the form, query the database...) then return a list of services that best covers the 10/20/35 specified requirements.

I'm having trouble wrapping my brain around the best way to go about this... how the data/tables would be structured, what the query would look like, etc. If someone could make some suggestions on how to best approach this, I would really appreciate the help.

Tags : php mysql


Answers 1


For this kind of thing you have to decide what 'best' means. Once you have done that the rest will fall into place.

So with your TV example, presumably each package offers a set of channels and you want the cheapest combination of packages that include all the channels you selected.

Simple enough, make a recursive tree search of all the packages, removing channels from the selection and adding up the price as you go. Order by total price and the first one is your answer!

However, what if there is one really cheap package that offers all but one of your channels, but that channel is not available by itself on other packages.

A real person might well want to see that at the top of the list, even though they would miss out on one of their essential channels.

It's this kind of thing you have to think through and get clear in your head. Once you are clear you can assign bonus points to these scenarios and order them accordingly

Edit: sorry, missed your php tag, but here is a sample algorithm. You could do it faster in sql, but it would not scale well.

public List<List<Package>> BestMatch(
    IEnumerable<string> remainingChannels, 
    IEnumerable<Package> remainingPackages,
    IEnumerable<Package> results
    )
{
    var new_result = new List<List<Package>>();
    var rp = remainingPackages.Where(i => i.channels.Any(j => remainingChannels.Contains(j)));
    if(!rp.Any())
    {
        new_result.Add(results.ToList());
        return new_result;
    }

    foreach (var p in rp)
    {
        var rc = remainingChannels.Where(i => !p.channels.Contains(i));
        var new_rp = rp.Where(i => i != p);
        var r2 = new List<Package>();
        r2.AddRange(results);
        r2.Add(p);
        new_result.AddRange(BestMatch(rc, new_rp, r2));
    }

    return new_result;
}
Ewan
Ewan
August 28, 2018 14:24 PM

Related Questions


Is this a race condition?

Updated April 16, 2015 20:02 PM


problem in show threads 1 result mysql.php

Updated May 28, 2015 22:02 PM