Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hi I'm new to this, feel free to correct or edit anything if I haven't done something properly.

This is a programming problem I'm having and finding a closed form instead of looping would help a lot.

The Problem
Given a list of N symbols say {0,1,2,3,4...}
And ${{N}\choose{r}}$ combinations of these

eg. ${{N}\choose{3}}$ will generate:

0 1 2
0 1 3
0 1 4
...
...
1 2 3
1 2 4
etc...

For the ith combination ($i = [1 .. {{N}\choose{r}}]$) I want to determine Whether a symbol (s) is part of it.
Func(N, r, i, s) = True/False or 0/1
eg. Continuing from above The 1st combination contains 0 1 2 but not 3
F(N,3,1,"0") = TRUE
F(N,3,1,"1") = TRUE
F(N,3,1,"2") = TRUE
F(N,3,1,"3") = FALSE

Current approaches and tibits that might help or be related.
Relation to matrices For r = 2 eg. {4}\choose{2} the combinations are the upper (or lower) half of a 2D matrix
1,2 1,3 1,4
----2,3 2,4
--------3,4

For r = 3 its the corner of a 3D matrix or cube for r = 4 Its the "corner" of a 4D matrix and so on.

Another relation
Ideally the solution would be of a form something like the answer to this: http://stackoverflow.com/questions/5052688/calculate-combination-based-on-position
The question there is (i think) not well worded

The nth combination in the list of combinations of length r (with repitition allowed), the ith symbol can be calculated
Using integer division and remainder:
$\lfloor n/r^i\rfloor$ % r = (0 for 0th symbol, 1 for 1st symbol....etc)

eg for the 6th comb of 3 symbols the 0th 1st and 2nd symbols are:
i = 0 => 6 / 3^0 % 3 = 0
i = 1 => 6 / 3^1 % 3 = 2
i = 2 => 6 / 3^2 % 3 = 0

The 6th comb would then be 0 2 0

I need something similar but with repition not allowed.

Thank you for following this question this far :]
Kevin.

share|improve this question
    
You must have a rule for obtaining the combinations in some order, because in general there is no such thing as "the" $i$th choice of $k$ elements from a set of $N$ (so it makes no sense to talk about "the $i$th combination" without a rule for ordering them). How are you ordering them? –  Arturo Magidin May 4 '11 at 4:50
2  
It looks to me like they are being taken in lexicographic order. –  Robert Israel May 4 '11 at 5:09
    
Is your ordering 012, 013, 014… really crucial? If any order will work, and if it is okay to consider the $i$th combination in the lexicographical order of the strings written in descending order (210, 310, 320, 321, 410, 420… etc.), then there is a nice and fast algorithm for generating the $i$th combination directly. –  ShreevatsaR May 4 '11 at 5:55
    
Thanks to all so far for your input. The order certainly doesn't matter, It just needs to be unique and complete. ShreevatsaR: thanks for the link I'll look into it and see if that is what I'm looking for. –  kevyin May 4 '11 at 8:41
    
The same question by the same user (with my same answer as below) on StackOverflow. –  ShreevatsaR Jun 20 '11 at 3:47

2 Answers 2

Just for completeness, I'm posting as an answer an elaboration of my comment above. There is no "closed form" as far as I know, but there's a very efficient algorithm. All this is also in Knuth Volume 4A (section 7.2.1.3).

Since you don't care about the order in which the combinations are generated, let's instead use the lexicographic order of the combinations where each combination is listed in descending order. Thus for $r=3$, the first 10 combinations of 3 symbols would be: 210, 310, 320, 321, 410, 420, 421, 430, 431, 432. The advantage of this ordering is that the enumeration is independent of $n$; indeed it is an enumeration over all sets of 3 symbols from $\{0, 1, 2, \dots \}$.

Now, there is a standard method to directly generate the $i$th combination given $i$, so to test whether a symbol $s$ is part of the $i$th combination, you can simply generate it and check. The method is the following:

How many combinations of $r$ symbols start with a particular symbol $s$? Well, the remaining $r-1$ positions must come from the $s$ symbols $0, 1, 2, \dots, s-1$, so it's $\binom{s}{r-1}$. As this is true for all $s$, the first symbol of the $i$th combination is the smallest $s$ such that $\sum_{k=0}^{s}\binom{k}{r-1} \ge i$. Once you know the first symbol, the problem reduces to finding the $\left(i - \sum_{k=0}^{s-1}\binom{k}{r-1}\right)$th combination of $r-1$ symbols, where we've subtracted those combinations that start with a symbol less than $s$.

In Python code, where C(n,r) is a function that returns $n \choose r$:

def combination(r, k):
    '''Finds the kth combination of r letters.'''
    if r==0: return []
    sum = 0
    s = 0
    while True:
        if sum + C(s,r-1) < k:
            sum += C(s,r-1)
            s += 1
        else:
            return [s] + combination(r-1, k-sum)

def Func(N, r, i, s): return s in combination(r, i)

The complexity is a bit icky to calculate, but it finds the 10000000000000000000000000000000000000000000000000000000000000000th combination of 500 letters (it starts with 542) in less than 0.5 seconds.

share|improve this answer

what you're looking for is called Lehmer code

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.