k-Element Subsets ranking

PAL Algoritmus

Iterating over subset of only the length of k using Ranking function .

Let set T={1,2,3,4,5}. All subsets of length k=3 are

123 124 125 134 135 145 234 235 245 345

Rank 5 = 00101, therefore subset of T given rank 5 is {3,5}.

Ranking

Function kSubsetLexRank(size n; k-subset of T) : rank {
	r = 0;
	T[0] = 0;
	
	for i = 1..k:
		if T[i-1]+1 < T[i]-1:
			for j = T[i-1]+1..T[i]-1
				r = r + comb(n-j, k-i);
}

Unranking

Basically converting rank to its binary representation by dividing to 2 until 0.

Function SubsetLexUnrank( size n; rank r ) : set {
	T = { }
	for i = n downto 1: 
		if r mod 2 = 1: 
			T = T ∪ {i} 
		r = r div 2
	return T
}

Finding sucessor

function KSubsetLexSuccesor(k-element subset of T, size n){
	U = T;
	i = 0;
	
	while ( i < k AND T[k - i] = n - i ){
		i++;
	}
	
	i = k - i // index in the 
	if ( i == 0 ) throw; // 
	
	for (j = i..k){
		U[j] = T[i] + 1 + j - i
	}
}

Imagine ABAKUS!

1234        Right is empty, take 4, make it 5
123 5       Right is empty, tak 5, make it 6
123  6      Right is 6, skip it, take 3, make it 45
12 45       Right is empty, take 5, make it 6
12 4 6      Right is 6, skip it, make 4 into 56
12  56      Right is 56, skip it, turn 2 into 345
1 345 
1 34 6

Like abakus, you skip the right “piece”, find the first from the right, push it one right and take all the rest and put is right after.