Combinatorics masturbation

I dont want to make the impression that today at work I’m bored as hell, but, probably that’s the reason why I’m writing this post instead of working on my task in order to have something to say at the tomorrow daily meeting –yep, we have DAILY meetings twice a week in our personal SCRUM piece of paradise-. :p

Anyway, I decided to make some exercise from my combinatorics book instead (BOOK), one of those problems is the number 49th, which is basically asking to find the index of a given subset in the lexicographically sorted multi-subset of k-elements from A={1,2,…,10}.

So we have all the nCk subset of the given set and we want to have them numbered. This problem can be solved with paper and pencil just noting that what the author wants is just to sum the amout of subset which are lexicographically smaller that the requested k-elements subset, so for example given the 4-element subset {3,5,7,9} of A we have:

• The amount of 4-element subset starting with 1 and 2 are: 9C3 + 8C3 (Note those subset are lexicographically preceding the subset for which we are calculating the index)
• The amount of 3-element subset starting with 4 (the next element) are 6C2 (You remove from 1,2,3,4 from A, which gives you |A|-4 = 6)
• Then again you do the same for the subset starting with 6: 4C2
• and 8: 2C0

Summing up: 84+56+15+4+1=161 which is just the index we were looking for.. Since I was already dealing with this problem i wrote down a piece of code which made exactly the explained calculation:

#include 
#include 
#include 
using namespace std;

long comb(int n, int k)
{
	if(k>n) return 0;
	if(k==n) return 1;
	long r{1};
	for(int i{1};i<=k;i++)
	{
		r *= double(n-i+1)/i;
	}
	return r;
}
long calculate_index(vector& k_seq,int n)
{
	long r{1},l{0};
	long k{k_seq.size()};
	for(int i{0};i<k;i++)
		for(l++;l!=k_seq[i];l++)
			r += comb(n-l,k-i-1);
	return r;
}
int main()
{
	vector seq = {1,2,3,4,5,6,7,8,9,10};
	int k{4};
	string b(k,'1');
	b.resize(seq.size(),'0');
	int idx{1};
	vector r;
	string s;
	do{
		bool nl{false};
		for(int i{0};i<b.size();i++)
		{
			if(b[i]!='0'){
				r.push_back(seq[i]);
			}
		}
		string s;
		for(auto e:r)
			s += to_string(e);
		if(s=="3456" || s=="3579")
			cout<<s<<" - "<<idx<<" , combinatorics index: "<<calculate_index(r,seq.size())<<endl;
		++idx;
		r.clear();
	}while(prev_permutation(b.begin(),b.end()));
}

This code is written specifically to test the combinatorial algorithm for finding the index, and the function calculate_index just perform the operations described before.. comb just calculate nCk of course.

In the main function I’m just using the well known trick of permuting a binary sequence with m+k digits where m are zero and k 1, which basically allow you to count all the k-element combination from the set.

The complexity of this piece of code is O(n*k).