1
$\begingroup$

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: https://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.

  • 0
    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?2011-05-04
  • 2
    It looks to me like they are being taken in lexicographic order.2011-05-04
  • 0
    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](http://en.wikipedia.org/wiki/Combinatorial_number_system) for generating the $i$th combination directly.2011-05-04
  • 0
    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.2011-05-04
  • 0
    The same question by the same user (with my same answer as below) on [StackOverflow](http://stackoverflow.com/questions/5878768/determine-whether-a-symbol-is-part-of-the-ith-combination-ncr).2011-06-20

2 Answers 2