CODEWITHSUNDEEP
algorithmmatching
Aleksander Fular
Aleksander Fular

Reputation: 873

Select optimal pairings of elements

I have following problem e.g: Given a bucket with symbols
1 1 2 3 3 4
And book of recipes to create pairs e.g:
12 13 24
Select from bucket optimal pairing, leaving as little as possible symbols in the bucket. So using the examplary values above the optimal pairing would be:
13 13 24 Which would use all the symbols given.
Naive picking from the bucket could result in something like:
12 13 Leaving the 3 and 4 unmatched. 3 and 4 cannot be matched because the book does not contain a recipe for that particular connection

Notes:
Real problem consits on average of: 500 elements in bucket in about 30 kind of symbols.

We've tried to implement the solution using the bruteforce algorithm, however I am afraid that even our grandchildren will not live long enough to see the result :).

There is no limit to the size of recipe book, it could even have every possible in the bucket. Pair made of the same element twice is not allowed.

The answer is not required to empty the bucket completely. Its just about getting the most pairs out of the bucket. Its okay to leave some in the bucket. It would be best to look for the optimal solution, however close approximation is also good enough.

I will appreciate an answer that proposes/gives hint to an algorithm to solve the problem.

Examples:
Bucket:
1 1 2 2 2 2 3 3 3 4 5 6 7 8 8
Recipe book:
12 34 15 68
Optimal result (one of possible):
{1 2} {1 2} {3 4} {6 8}
Leftover:
2 2 3 3 5 7 8

Upvotes: 4

Views: 3312

Answers (2)

templatetypedef
templatetypedef

Reputation: 372784

This problem is essentially the maximum matching problem with the small twist that you're allowed to have duplicate objects. Here's one way to solve this problem assuming you have a solver for maximum matching:

  1. Create a node for each number in the input list.

  2. For each recipe, for each pair of numbers matching that recipe, add an edge between the nodes for those numbers.

  3. Run a maximum matching algorithm and return the pairs reported that way.

There are a good number of off-the-shelf maximum matching algorithms you can use, and if you need to code one up yourself, consider Edmonds' Blossom Algorithm, which is reasonably efficient and less tricky to code up than other approaches.

Upvotes: 4

Abdennacer Lachiheb
Abdennacer Lachiheb

Reputation: 4888

First generate all possibles pairs of symbols and store them with the indices of each symbol , so if you have n symbols , then n*(n+1)/2 pairs are going to be generated (max case n=500 then 125250 pairs are going to be generated ).

Ex : bucket with symbols 1 1 3 Then pairs are going to be generated are (11,1,2)(13,1,3)(13,2,3). General format ( a[i]a[j], i, j ).

Now lets loop over generated pairs and delete pairs that doesn't exist in the book of recipes, so now we have at most 30 pairs .

Next lets build a graph such that the nodes are our generated pairs, and each 2 nodes are connected if the indices of the 2 pairs are different (using 2 nested loops over our pairs ) .

Finally we can perform BFS or DFS and find the longest graph between all generated graphs , which has the answer to our problem.

If you want c++/Java implementation ,please don't hesitate to ask.

Upvotes: 1

Related Questions