Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Ordering Combinations, Then Picking the nth Item

Date: 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/ 
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/