Ordering Combinations, Then Picking the nth ItemDate: 10/22/2010 at 12:47:19 From: Hari Subject: Formula/Algorithm to get the Nth combination directly I need to get the nth combination from a set of combinations directly, i.e., without computing the previous combinations. For example, there are four ways to choose three elements from the set {1, 2, 3, 4}: (1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4) Say I want just the third combination, which in this example would be (1, 3, 4). To get it, I first explicitly generated the previous two. For sets of values as small as this, it is easy to use such sequential generation and an incremental counter to get the nth combination. But it is impractical to use this method when the number of combinations is really large, e.g., 20C10. Is there any formula/algorithm to compute the nth combination quickly? I tried to see if the combinations generated follow a pattern so that we can determine if an element will be present in that combination or not, but could not exactly figure out the scenario. Date: 10/23/2010 at 19:24:55 From: Doctor Vogler Subject: Re: Formula/Algorithm to get the Nth combination directly Hi Hari, Thanks for writing to Dr. Math. The first question you have to answer before determining the nth combination is: In what order are the combinations? You could list them in many different orders, and changing the order will change which one is in the nth position. So that's the first question you have to decide. In your example, you may have assumed the dictionary order. To compare two r-tuples under that protocol, you look at the smallest number that is in only one of the two sets, and the one with that number is the one that comes first. This is equivalent to sorting the r numbers in each of your r-tuples and then comparing the first numbers first, and moving to the second numbers if the first ones are the same, and so on. This is the order that has the following rule to move from one combination to the next combination, where we are talking about the k-choose-r r-tuples of numbers between 1 and k, inclusive: Find the last number (of the r) which is NOT (k - r) more than its position -- meaning, not a k in the r'th (last) spot not a k - 1 in the (r - 1)'st spot not a k - 2 in the (r - 2)'nd spot, etc. (Usually, this will be the last number.) Then increase that number by one, and (if it isn't the last number) change all of the numbers after it to the next consecutive integers (counting up by ones). When you want to list all combinations, you should start with the r-tuple (1, 2, 3, 4, ... r), and then use the above algorithm to go to the next one until you have exhausted them all. Now, to find the nth combination without listing all of the ones before it, you want to determine what the r different numbers are from left to right (or smallest to largest). You should first ask what the first number is. Could it be a 1? Well, how many combinations have a first number of 1? For that matter, how many combinations have a first number of m for any m? It turns out that the number of combinations with first number m is exactly (k - m)-choose-(r - 1), since you have to select the remaining (r - 1) numbers from the (k - m) numbers that are greater than m. So, first you check if N <= (k - 1)-choose-(r - 1). If it is, then the first number is 1. If it's not, then the first number is not 1, and you should check if N - (k - 1)-choose-(r - 1) <= (k - 2)-choose-(r - 1) If so, then the first number is 2. If not, then you keep going. Once you have determined the first number, then you do the same analysis to figure out what the second number is. And you repeat this pattern until you have determined all r of the numbers. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 10/25/2010 at 08:47:05 From: Hari Subject: Thank you (Formula/Algorithm to get the Nth combination directly) Hi Doctor Vogler, Thanks a lot for the immediate response. I was able to get the nth combination the way you have described it. I really am happy that I got the information and was able to work it out rightly. Thanks for your time and help :) Date: 11/08/2010 at 05:27:09 From: Hari Subject: Formula/Algorithm to get the Nth combination directly Hi again, I have a question regarding a variation on this problem. What is the way to generate the nth combination if the combinations are listed in order of their sums, from smallest to largest? To return to my example, the set {1, 2, 3, 4} has 4 combinations of 3 numbers: (1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4) In this set of combinations, the sums of the entries in each combination are, respectively, (1 + 2 + 3) = 6 (1 + 2 + 4) = 7 (1 + 3 + 4) = 8 (2 + 3 + 4) = 9 For this ordering by sums, the combinations happen to preserve the dictionary sorting of their constituent elements. But for larger sets, the sums of combinations do not necessarily produce a sorting equivalent to the dictionary order. Is there any way to identify the nth combination when ordering them according to their sums? Date: 11/08/2010 at 11:16:35 From: Doctor Vogler Subject: Re: Formula/Algorithm to get the Nth combination directly Hi Hari, Thanks for writing back to Dr. Math. Well, you can do basically the same strategy by first determining what sum you should be on, and then determining the combination for that sum. You just have to figure out how to count: (1) How many combinations are there that have a particular sum, and (2) How many combinations with a particular sum have a certain first term. Do you think you can answer those two questions and build an algorithm, or do you need help with them? If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 11/08/2010 at 11:41:15 From: Hari Subject: Formula/Algorithm to get the Nth combination directly Hi, Thanks for the reply. Actually, the data I am talking about will be very big, so I could not think of any way to form the algorithm, and need your help to get the algorithm in place for the two steps that you have mentioned. Thanks again for the help; awaiting your reply. Date: 11/16/2010 at 00:19:40 From: Doctor Vogler Subject: Re: Formula/Algorithm to get the Nth combination directly Hi Hari, Sorry about the delay. I have been thinking about this, but am having a hard time coming up with a nice, neat algorithm for counting the number of combinations that have a particular sum. I'll keep thinking about it and let you know if I come up with anything. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/