5 Replies - 1126 Views - Last Post: 26 July 2012 - 10:12 PM

#1 JTHM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 25-April 12

Fastest Way to Determine if an Element Belongs in a Combination

Posted 26 July 2012 - 04:59 PM

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Fastest Way to Determine if an Element Belongs in a Combination

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1148
  • View blog
  • Posts: 2,528
  • Joined: 05-May 05

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.
Was This Post Helpful? 1
  • +
  • -

#3 JTHM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 25-April 12

Re: Fastest Way to Determine if an Element Belongs in a Combination

Posted 26 July 2012 - 06:28 PM

View Postblackcompe, 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.)
Was This Post Helpful? 0
  • +
  • -

#4 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1148
  • View blog
  • Posts: 2,528
  • Joined: 05-May 05

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:

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

Was This Post Helpful? 1
  • +
  • -

#5 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

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.
Was This Post Helpful? 2
  • +
  • -

#6 JTHM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 25-April 12

Re: Fastest Way to Determine if an Element Belongs in a Combination

Posted 26 July 2012 - 10:12 PM

View Postmostyfriedman, 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1