Menu
Basically, given a sorted list of positive non-zero numbers, say {1, 4, 5}, change a single number in the list to maximize the distinct combinations possible. The above gives 1, 4, 5, 6, 9, 10, that is, six combinations. If we were to change 4 to 2 so we have {1, 2, 5}, we'd get 1, 2, 3, 5, 6, 7, 8, that is, seven combinations.
I need to find a number x to add to a single number of the list to maximize the amount of combinations. x should be the smallest abslout value, we can both add or subtract.
I've done it using brute force by enumeration, which runs in many times exponential time. So it's not feasible for larger problems. Now I need to do it fast.
Just checking the number of combinations is exponential time? And I have to find the exact optimal solution.
What would be some keywords for solving this problem? I've attempted to find a recurrence, so I could use dynamic programming and some sort of branch and bound to limit the explosion, but it's no use.
I've looked into problems like cutting mill, subset sum, and a lot of other combinatorial optimization problems to see if I could find some ideas. But I don't get it. Simply verifying the solution is exponential time.
386
The formula for combinations is generally n! / (r! (n -- r)!), where n is the total number of possibilities to start and r is the number of selections made. In our example, we have 52 cards; therefore, n = 52. We want to select 13 cards, so r = 13.
Given an array of positive integers arr[] and a sum x, find all unique combinations in arr[] where the sum is equal to x. The same repeated number may be chosen from arr[] unlimited number of times. Elements in a combination (a1, a2, …, ak) must be printed in non-descending order.
First, we take an empty list 'res' and start a loop and traverse each element of the given list of integers. In each iteration, pop the element, store it in 'num', find remaining difference for sum K, and check if the difference exists in the given list or not.
This is just a stab at it, I've written no code or even worked out any proofs on it.
Since you're limited to changing only one value, I would consider that the easiest way to eliminate combinations (which I know you're not trying to do, but hear me out) is to make two numbers add up to another number in the list. So in your example 1 4 5 because 1 + 4 = 5 you lose out on combinations there. Therefore I would do a query of the set of numbers for what number pairs result in another member of the set. This is O(n^2 lg n) as you compare each number to every other number, and in doing so also search the (sorted) list of numbers to find if it exists or not.
Your candidate is that which has the highest number of 'collisions'. Hands down, by making the highest collision-prone number a zero-collision number, you will get the maximum increase in end results. From there, it is just a matter of finding what number to add/subtract to it to make it a non-collision number. I haven't worked out the proper way to do this, but I suspect it can be done with dynamic programming in polynomial time.
There lies another serious problem in which you have ties. I think this is in the worst case going to add an extra *n to your complexity, as you will have at most n ties to simultaneously search. So assuming you can calculate the above problem in n^p time where p is some constant polynomial, then the entire problem should still be solveble in n^(p+1) time.
This is certainly a doosy of a problem, and I hope this has been able to shed some light onto it. After two months, someone has to take a stab at it, right? :)
131
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
