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.

## 5 Replies - 1345 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 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.

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 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.

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

### #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 d-th 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 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.

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

### #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