[JTHM]

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 c-tuple containing all and only the integers from 1 to c, in ascending order. Let the set of cardinality b which is the d-th 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.

[blackcompe]

So then this problem boils down to finding the d-th 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.

[JTHM]

blackcompe, on 26 July 2012 - 06:02 PM, said:

So then this problem boils down to finding the d-th 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.

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 n-th 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.)

[blackcompe]

Can you explain to me how the problem doesn't boil down to finding the d-th combination, when you explicitly said:

Quote

Let the set of cardinality b which is the d-th 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 d-th combination of E whose size is b.

I said you need to find the d-th 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

[mostyfriedman]

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.

[JTHM]

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.

AWESOME!

+1000 Internets to you, sir! This is going to be a huge help.