Combinations Formulae & Mapping to Index Values

[raminee]

TL;DR

How to come up with an indexing formulae for all set of combinations from a given set of numbers?

The Combinations formulae will find the number of possible combinations that can be obtained by taking a sample of items from a larger set.

C = n! / [r! * (n-r)! ]

Where n is the number of set samples and r is the number of desired selected samples.
So as an example say we have n=5 and r=2.
Here are all the possible 10 combinations for choosing 2 samples out of 5 samples as shown in attached picture.
Note a 1 is a selected sample.
My question is given a chosen sample combination can we come up with a formulae that can map it to its index value ??

So say we come up with combination samples 1 and 3 then how do we get to index 5 ??

 

[Office_Shredder]

What do ,"chosen sample combination" and "index value" mean here?

 

[raminee]

In the example I have chosen we have 5 samples in our data set. So n =5.
I have selected r to be 2. So we are looking at 2 sample combinations out of 5.
As shown in the attached picture in my original post the 2 sample combinations are indicated as 1s.
So in the table first 2 samples combination is sample 0 and sample 1. Next combination is sample 0 and sample 2 and so on. There are a total of ten 2 samples combinations as shown in the table.
Now let's say we map each of the 10 combinations to an index value. This way rather than say what the 2 samples combinations are I like to give the index and use a formulae to calculate the 2 samples combinations.

So if I say index 5 then one should be able to calculate, through a known formulae, that the two chosen samples are samples 1 and sample 3 as shown in the table. And so on for each index value.

Hope this clarifies it a bit.

 

[DrClaude]

I think you should figure out first how to get the index from the two samples, $s_1$ and $s_2$.

Spoiler

$$
\mathrm{index} = \frac{1}{2} \left[ (2n-1) s_1 - s_1^2 \right] + (s_2 - s_1)
$$

 

[raminee]

I think you should figure out first how to get the index from the two samples, $s_1$ and $s_2$.

Spoiler

$$
\mathrm{index} = \frac{1}{2} \left[ (2n-1) s_1 - s_1^2 \right] + (s_2 - s_1)
$$

Thank you DrClaude for this formula.

Given the example I posted I assume n=5, S2 is S(i+1) and S1 is S(i) where (i) is the sample position from 0 to 4.
You formula works for the example that I have given and the index goes from 1 to 10 which is fine.
But I was looking for more of a generic way to code this regardless of the numbers in the data set or the number of samples chosen.

What happens when we choose 4 samples out of 10 data sets ? Here we get 210 possible combinations.

I know a long time ago I came across this problem and I believe there was a solution as how to decode a given index knowing (n) and (r). but I have lost the paper and I can not find it anywhere on line.

So if anyone knows how to do it in a more generic way pls do let me know.

I will play around with your idea to see if I can make it for other possibilities.

Thanks again

 

[pbuk]

So if anyone knows how to do it in a more generic way pls do let me know.

Useful search terms:
Combination rank algorithm
Combinatorial number system
Combinadics

We have a different topic here for this kind of problem, I'll get it moved:
https://www.physicsforums.com/forums/programming-and-computer-science.165/

Oh and

 

[.Scott]

Let's see, sounds recursive to me.
With no attempts at optimization:

Spoiler

#include <iostream>
#include <algorithm>
#include <vector>

//
// Returns the index of a combination.
//  The combination is a sequence of "r" integers starting at s[i0].
//  Return value is the index of the combination "s" within a list of
//  "s.size()" combinations of "n" elements.
_int64 GetIndex(int n, std::vector<int>s)
{
   int i, v, r, rA, rB;
   _int64 nCount, nIndex;

   //
   // Handle simple cases without recursion.
   r=(int)s.size();
   if((n<=0)||(r<=0)) return 0;
   v=s[0];
   if(r==1) return v;
   //
   // Prepare for the recursive call.
   std::vector<int>::iterator it;
   std::vector<int> sR(s.begin()+1, s.end());
   for(it=sR.begin(); it!=sR.end(); it++) {
      *it = *it - v - 1;
   }
   //
   // Handle case where the first index is zero.
   if(v==0) return GetIndex(n-1, sR);
   //
   //  Calculate the number of combinations when the first element is
   // zero: (n-1)!/[(r-1)!*(n-r)!] = (n-1)!/(rA!rB!)
   rA = std::max(r-1, n-r);
   rB = std::min(r-1, n-r);
   nCount = 1;
   for(i=rA+1;i<n;i++) nCount *= i;
   for(i=2;i<=rB;i++) nCount /= i;
   //
   //  Count forward in the list of combinations until we get to the
   // first element.
   nIndex = nCount;
   for(i=1;i<v;i++) {
      //
      // Increment by "n-i" elements taken "r-1" elements at a time.
      //  (n-i-1)!/[(r-1)!*(n-i-r)!]
      nCount *= n-r-i+1;
      nCount /= n-i;
      nIndex += nCount;
   }
   return nIndex += GetIndex(n-v-1, sR);
}

int main()
{
   int v, minv;

   //
   // From your example:
   int n = 5;   // The total number of possible values.
   std::vector<int>sRaw={1,3};  // The combination in question.
   // std::vector<int>sRaw={2,3,4};  // The combination in question.
   //
   //   Our algorithm depends on values in range (0<=v<n) and in
   // ascending order.
   std::sort(sRaw.begin(), sRaw.end());  // Now an ordered list.
   std::vector<int>s;
   s.reserve(sRaw.capacity());
   std::vector<int>::iterator it;
   for(minv=-1,it=sRaw.begin(); it!=sRaw.end(); it++) {
      v = *it;
      if((v>minv)&&(v<n)) {
         minv = v;
         s.push_back(v);
      }
   }
   //
   _int64 index = GetIndex(n, s);
   std::cout << "Index is " << index << "\n";
}