Hey Dream.In.Code, I need to write an efficient algorithm to solve a decision problem (for a personal project, not school), but I'm not sure how to do it.
This is the problem:
We are given four integers: a, b, c, and d, all greater than zero. Values for a and b are both less than or equal to c, and d is less than or equal to (c choose b ).
Let E be a ctuple containing all and only the integers from 1 to c, in ascending order. Let the set of cardinality b which is the dth combination of b elements of E be F; let the order of the combinations of elements of E be defined however you wish. The problem is to decide if a is a member of F.
The trick to this is, in order to solve this in any reasonable running time for large inputs, we can't bother generating the entire combination, or even a sizable fraction of it (because the size of E and F can increase exponentially with the length of the representation of c and b, respectively, such an inefficient method would run in EXPSPACE). Does anyone have any thoughts as to how I would go about this? Examples in pseudocode would be extremely helpful, as would a reference to a book that would contain an answer.
Deterministic algorithms only, if you don't mind, unless someone can show that this problem is outside P but inside PH on the assumption that P!=NP.
5 Replies  1262 Views  Last Post: 26 July 2012  10:12 PM
#1
Fastest Way to Determine if an Element Belongs in a Combination
Posted 26 July 2012  04:59 PM
Replies To: Fastest Way to Determine if an Element Belongs in a Combination
#2
Re: Fastest Way to Determine if an Element Belongs in a Combination
Posted 26 July 2012  06:02 PM
So then this problem boils down to finding the dth combination in the set of (c choose b ) combinations. A quick Google search returned the following relevant links:
Nth Combination  The accepted answer looks a bit complex, but maybe it'll help. The second answer looks simple and correct, but I wonder about its efficiency for large inputs.
Nth Combination  The accepted answer looks a bit complex, but maybe it'll help. The second answer looks simple and correct, but I wonder about its efficiency for large inputs.
#3
Re: Fastest Way to Determine if an Element Belongs in a Combination
Posted 26 July 2012  06:28 PM
blackcompe, on 26 July 2012  06:02 PM, said:
So then this problem boils down to finding the dth combination in the set of (c choose b ) combinations. A quick Google search returned the following relevant links:
Nth Combination  The accepted answer looks a bit complex, but maybe it'll help. The second answer looks simple and correct, but I wonder about its efficiency for large inputs.
Nth Combination  The accepted answer looks a bit complex, but maybe it'll help. The second answer looks simple and correct, but I wonder about its efficiency for large inputs.
It does not, I'm afraid, boil down to that. I'm looking for a method that would run efficiently (e.g. in polynomial time). To do that would require not having to generate every element of the nth combination until we reach the element we are looking for. (As I mentioned, such a method would take EXPSPACE, or if we were able to discard every element after generating it, EXPTIME.)
#4
Re: Fastest Way to Determine if an Element Belongs in a Combination
Posted 26 July 2012  06:32 PM
Can you explain to me how the problem doesn't boil down to finding the dth combination, when you explicitly said:
If the objective is to tell whether a is in F, then I need to know F. F is the dth combination of E whose size is b.
I said you need to find the dth combination; I didn't say anything about an algorithm (or its runtime) to find it.
Quote
Let the set of cardinality b which is the dth combination of b elements of E be F; let the order of the combinations of elements of E be defined however you wish. The problem is to decide if a is a member of F.
If the objective is to tell whether a is in F, then I need to know F. F is the dth combination of E whose size is b.
I said you need to find the dth combination; I didn't say anything about an algorithm (or its runtime) to find it.
This post has been edited by blackcompe: 26 July 2012  06:34 PM
#5
Re: Fastest Way to Determine if an Element Belongs in a Combination
Posted 26 July 2012  09:50 PM
This is a nice problem that got me interested as I haven't come across it before, so thanks for asking it. Anyway I believe this should answer it.
Combinadic
This article is very nice as well.
Sorry I couldn't be of further assistance as I myself am currently reading about this problem.
Combinadic
This article is very nice as well.
Sorry I couldn't be of further assistance as I myself am currently reading about this problem.
#6
Re: Fastest Way to Determine if an Element Belongs in a Combination
Posted 26 July 2012  10:12 PM
mostyfriedman, on 26 July 2012  09:50 PM, said:
This is a nice problem that got me interested as I haven't come across it before, so thanks for asking it. Anyway I believe this should answer it.
Combinadic
This article is very nice as well.
Sorry I couldn't be of further assistance as I myself am currently reading about this problem.
Combinadic
This article is very nice as well.
Sorry I couldn't be of further assistance as I myself am currently reading about this problem.
AWESOME!
+1000 Internets to you, sir! This is going to be a huge help.
Page 1 of 1
