CODEWITHSUNDEEP
algorithm
Endy Tjahjono
Endy Tjahjono

Reputation: 24450

Combo detection mechanism

In a Point of Sale system, the cashier keys in the product type and the quantity one by one. Suppose there is a business rule for combos, for example buy 2 fries with 2 cokes and you get $1 off. I want to create a mechanism that automatically detect combos in the list of products bought, and then apply the appropriate discount.

The product master contains around 4000 items. There will be around 100 combos. Average number of products bought in a transaction is 2. Up to now the highest number of products in a transaction ever recorded is 128.

My thinking is if there are 3 products (A, B, C) in a transaction, I have to check the presence of combo for (A, B), (A, C), (B, C), (A, B, C). The number of combinations that need to be checked rise pretty fast when the transaction has more product types.

Is this possible? Anybody ever tried something like this? Care to share some insight on how to implement this?

Platform is vb.net 2010 and SQL Server 2005.

EDIT

A combo will contain 2 to 4 items.

Upvotes: 3

Views: 203

Answers (2)

Ajeet Ganga
Ajeet Ganga

Reputation: 8653

// I figured it is easy to post code than explaining long-winded style. All are programmer here anyways
typedef pair<string,int> item_quant;
bool funccomp (const item_quant& lhs, const item_quant& rhs)
{
    if((lhs.first < rhs.first) ||  (lhs.second < rhs.second))
        return true;
    return false;
}
struct classcomp {
    bool operator() (const vector<item_quant>& lhs, const vector<item_quant>& rhs) const
    {
        if(lhs.size() < rhs.size())
            return true;
        for(unsigned int i=0; i< lhs.size();++i)
        {
            if(!funccomp(lhs[i],rhs[i]))
                return false;
        }
        return true;
    }
} classcompObj;



int main()
{
    // Insert
    map<vector<item_quant>,int,classcomp> table;
    vector<item_quant> v;
    v.push_back(make_pair("coke",2));
    v.push_back(make_pair("fries",2));
    // Dont forget to sort.
    sort(v.begin(),v.end(),funccomp) ;
    table[v] = 1;

    //search
    int disc = (*table.find(v)).second;
    cout<<" disc = "<<disc<<endl;
    return 0;
}

Upvotes: 1

Zento
Zento

Reputation: 335

You could sort your possible combos like you already did in your post, then create a tree structure. If you have to check a combo, you first look for the first item (e.g. A), then follow the tree, then check for the next item (e.g. C). If you can find this, there is a possible combination, else not.

Different solution: Save all combinations sorted as in your question in a hash map and then look those combinations up. I could imagine this as pretty fast, but it would need a lot of space and some time to generate the hash map.

Upvotes: 1

Related Questions