Subset Ranking

PAL Algoritmus

Ranking subsets based on significant vector. Significant vector is a binary string of lenght n, which is 1 if element is in a subset and zero otherwise.

Let set T={1,2,3,4,5}. Rank 5 = 00101, therefore subset of T given rank 5 is {3,5}.

Ranking

Function SubsetLexRank(size n; set T) : rank {
	r = 0;
	for i = 1..n:
		if i in T:
			r = r + 2**(n-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 successor

Basically just add one and do the unranking algorithm