4 Replies - 4119 Views - Last Post: 13 December 2012 - 09:53 PM

#1 JTHM  Icon User is offline

  • New D.I.C Head

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

Finding an arbitrary element of the m-th k-subset in polynomial time

Posted 10 December 2012 - 11:27 PM

Hello Dream.in.code,

I was wondering if one of you could help me with a problem. I want to know if there's a polynomial time algorithm to solve the following problem:

Given integers n, k, r, and c where r<k and c<(n+1 choose k), what is the (r+1)-th-smallest member of the c-th k-subset of integers from 0 to n?

I'm already quite familiar with a few variations on an algorithm that returns k-subsets as a function of integers without needing to generate any lower-indexed subsets (this is called an "unranking" algorithm, and a good explanation of one is given here): http://msdn.microsof...6(v=vs.71).aspx

And some useful additional reading can be found here: http://en.wikipedia....l_number_system

The problem is, the value of k increases exponentially with the size of its representation, and the algorithm above, and all variations on it with which I am familiar, require that the individual elements within the k-subset be generated in some order, whether largest to smallest or vice-versa. Therefore, in the worst-case scenario, it will take exponential time to reach some arbitrary element within the k-subset. The above algorithm, however, was designed to generate entire k-subsets, not just specific elements therein, and therefore I yet have hope that another, polynomial-time algorithm exists that would accomplish my intended goal.

And yes, before you ask, I have looked through all the textbooks and reference materials I can find, and not one of them even mentions the problem I have given above--which I find rather shocking, but there you have it.

I kindly ask that nobody reply who has not read this post in its entirety, and understood it. I have asked the same question of many people, including people who ought to have known better, who simply replied with something along the lines of, "Here's an algorithm for generating an arbitrary k-subset!" Again, as noted above, all such algorithms I know of take EXPONENTIAL TIME (and that's bad), because they require that the individual elements of that k-subset be generated in a certain order. I have had people reply, "No, this method doesn't require that the previous k-subset already be known," but that's not the problem. I do not need another algorithm that generates a k-subset from an integer index; I need an algorithm that finds the (r+1)-th smallest integer in that k-subset without needing to know the r-th smallest or the (r+2)-th smallest integer in that k-subset.

If you don't know whether the above problem can be solved in polynomial time, but do know whether it belongs in complexity class PH, that would be helpful too.

And I'm very sorry if I come off as snippy, but I've been working on a personal project (a paper I want to submit for publication) for a long time, and the lack of a solution to this problem means that I can't finish it. (I've become extremely frustrated.)

Anyone who can help would be my hero. Thanks.

Is This A Good Question/Topic? 0
  • +

Replies To: Finding an arbitrary element of the m-th k-subset in polynomial time

#2 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: Finding an arbitrary element of the m-th k-subset in polynomial time

Posted 11 December 2012 - 11:23 AM

Yes, there is a polynomial time algorithm. Because we aren't really supposed to do your work for you, I will give a similar problem

suppose we have n digits (0 through n-1), and we want to find the ith permutation. Instead of finding all permutations and looking at the ith one on the list, we can use our list, the number i, and some combinatorial equations to generate the answer. The key is knowing that there are n! permutations for a list of n unique characters. This means that there are (n-1)! permutations for (n-1) unique characters.

We know that the first batch of numbers would have to start with 0. Thus, there are (n-1)! permutations that begin with 0. If this number is less than i, then we know that the ith permutation cannot begin with 0. So now we try 1. If 2*(n-1)! is less than i, then we know that the ith permutation cannot begin with 0 or 1. Basically, we need to find k such that (k-1) * (n-1)! < i < (k) * (n-1)!. k is the first digit of the solution. We now remove the kth digit from the list of digits and subtract (k-1) * (n-1)! from i. We will call this number i_2. Our task is now to find the i_2th permutation of the remaining digits. Repeat until all digits are used. Here is an example of the algorithm in action

Find the 311th permutation of {0,1,2,3,4,5} Solution{}
n = 6
(n-1)! = 120
2 * 120 < 311 <= 3 * 120
k=3, kth digit = 2
311-(2*120)=51

Find the 51st permutation of {0,1,3,4,5} Solution{2}
n = 5
(n-1)! = 24
2 * 24 < 51 <= 3 * 24
k=3, kth digit = 3
51-(2*24)=3

Find the 3rd permutation of {0,1,4,5} Solution{2,3}
n = 4
(n-1)! = 6
0 * 6 < 3 <= 1 * 6
k=1, kth digit = 0
3-(0*6)=3

Find the 3rd permutation of {1,4,5} Solution{2,3,0}
n = 4
(n-1)! = 2
1 * 2 < 3 <= 2 * 2
k=2, kth digit = 4
3-(1*2)=1

Find the 1st permutation of {1,5} Solution{2,3,0,4}

The first permutation is just the remaining digits in order, but you can continue the algorithm if you wish.

Final Solution: {2,3,0,4,1,5}



So, your task would be to choose a digit, calculate what remains to be done and compare that to "c" to determine if you chose correctly, much in a similar manner to how "i" was compared to k and (n-1)!.

I hope this helps get you started.

This post has been edited by mojo666: 11 December 2012 - 11:28 AM

Was This Post Helpful? 0
  • +
  • -

#3 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: Finding an arbitrary element of the m-th k-subset in polynomial time

Posted 11 December 2012 - 02:15 PM

Quick note.

Quote

I kindly ask that nobody reply who has not read this post in its entirety, and understood it. I have asked the same question of many people, including people who ought to have known better, who simply replied with something along the lines of, "Here's an algorithm for generating an arbitrary k-subset!" Again, as noted above, all such algorithms I know of take EXPONENTIAL TIME (and that's bad), because they require that the individual elements of that k-subset be generated in a certain order. I have had people reply, "No, this method doesn't require that the previous k-subset already be known," but that's not the problem. I do not need another algorithm that generates a k-subset from an integer index; I need an algorithm that finds the (r+1)-th smallest integer in that k-subset without needing to know the r-th smallest or the (r+2)-th smallest integer in that k-subset.


I had trouble understanding this paragraph at first, but it seems like you don't understand the problem. All you need to do is find the cth k-subset in polynomial time. Then you can scan the elements in that subset for rth smallest element and it will still be polynomial. Knowing r or r+2 doesn't change that. K does not grow exponentially with the input. The input size is n and k is always less than n. The only reason the algorithms you know of take exponential time is probably because they produce ALL k-subsets and there is an exponential number of k-subsets. Producing one k-subset with k elements in polynomial time is not exponential.
Was This Post Helpful? 0
  • +
  • -

#4 JTHM  Icon User is offline

  • New D.I.C Head

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

Re: Finding an arbitrary element of the m-th k-subset in polynomial time

Posted 12 December 2012 - 05:39 PM

View Postmojo666, on 11 December 2012 - 02:15 PM, said:

Quick note.

Quote

I kindly ask that nobody reply who has not read this post in its entirety, and understood it. I have asked the same question of many people, including people who ought to have known better, who simply replied with something along the lines of, "Here's an algorithm for generating an arbitrary k-subset!" Again, as noted above, all such algorithms I know of take EXPONENTIAL TIME (and that's bad), because they require that the individual elements of that k-subset be generated in a certain order. I have had people reply, "No, this method doesn't require that the previous k-subset already be known," but that's not the problem. I do not need another algorithm that generates a k-subset from an integer index; I need an algorithm that finds the (r+1)-th smallest integer in that k-subset without needing to know the r-th smallest or the (r+2)-th smallest integer in that k-subset.


I had trouble understanding this paragraph at first, but it seems like you don't understand the problem. All you need to do is find the cth k-subset in polynomial time. Then you can scan the elements in that subset for rth smallest element and it will still be polynomial. Knowing r or r+2 doesn't change that. K does not grow exponentially with the input. The input size is n and k is always less than n. The only reason the algorithms you know of take exponential time is probably because they produce ALL k-subsets and there is an exponential number of k-subsets. Producing one k-subset with k elements in polynomial time is not exponential.


The space taken up by a binary number with value n is log(n). If n is in unary, the space it occupies is n, but of course, nobody uses unary. If you are given a binary (or any other non-unary) number, and you have to complete n operations, you are dealing with an exponential-time problem.

View PostJTHM, on 12 December 2012 - 05:35 PM, said:

View Postmojo666, on 11 December 2012 - 02:15 PM, said:

Quick note.

Quote

I kindly ask that nobody reply who has not read this post in its entirety, and understood it. I have asked the same question of many people, including people who ought to have known better, who simply replied with something along the lines of, "Here's an algorithm for generating an arbitrary k-subset!" Again, as noted above, all such algorithms I know of take EXPONENTIAL TIME (and that's bad), because they require that the individual elements of that k-subset be generated in a certain order. I have had people reply, "No, this method doesn't require that the previous k-subset already be known," but that's not the problem. I do not need another algorithm that generates a k-subset from an integer index; I need an algorithm that finds the (r+1)-th smallest integer in that k-subset without needing to know the r-th smallest or the (r+2)-th smallest integer in that k-subset.


I had trouble understanding this paragraph at first, but it seems like you don't understand the problem. All you need to do is find the cth k-subset in polynomial time. Then you can scan the elements in that subset for rth smallest element and it will still be polynomial. Knowing r or r+2 doesn't change that. K does not grow exponentially with the input. The input size is n and k is always less than n. The only reason the algorithms you know of take exponential time is probably because they produce ALL k-subsets and there is an exponential number of k-subsets. Producing one k-subset with k elements in polynomial time is not exponential.


The space taken up by a binary number with value n is log(n). If n is in unary, the space it occupies is n, but of course, nobody uses unary. If you are given a binary (or any other non-unary) number, and you have to complete n operations, you are dealing with an exponential-time problem.


Edit: I meant to say, if you are given a binary (or any other non-unary) number with value n, and you have to complete n operations, you are dealing with an exponential-time problem.
Was This Post Helpful? 0
  • +
  • -

#5 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: Finding an arbitrary element of the m-th k-subset in polynomial time

Posted 13 December 2012 - 09:53 PM

Quote

Given integers n, k, r, and c where r<k and c<(n+1 choose k), what is the (r+1)-th-smallest member of the c-th k-subset of integers from 0 to n

You are dealing with a problem on a set which means the set is part of your input. Even if you were to just use "n" as a label for the set, that still doesn't change the input size for the same reason pointers don't effect the input size of algorithms on lists, trees, ect. So, the algorithms are actually polynomial.

If for some reason you actually need a poly-logrithmic algorithm for your paper, I am leaning towards "impossible", though I can't prove it. It just seems like you can't get to the rth smallest element without first doing something equivalent to iterating over the previous elements.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1