JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Finding the Lexicographically K-th Combinatorial Object | Reply
Name
Finding the Lexicographically K-th Combinatorial Object

Problem
From all combinatorial objects of length n generated by specified rules you need to find the lexicographically k-th one.

Solution
Let k be 0-based. Then let’s suppose am,p to be a number of combinatorial objects of length m satisfying certain condition marked as p. A totality of all p’s for some m describes a condition which suffixes of length m of any our combinatorial objects of length n must satisfy (and every such suffix must satisfy exactly one of those p’s).

So the general solution is like this pseudo-code:
class CombinatorialObject {
	void getMthSymbol (int m, int p, int k, vector<symbol> &ans) {
		if (m==0) return;
		ans.push_back(symbol(m,p,k));
		getMthSymbol(m-1,newP(m,p,k),newK(m,p,k),ans);
	}
};

Where function symbol(m,p,k) returns an appropriate symbol, function newP(m,p,k) returns new condition for a suffix of length m-1, and function newK(m,p,k) returns a number of appropriate suffix under this condition. These two functions may rely on am,p. To obtain the answer, we should call getMthSymbol with arguments n, condition p that actually means no condition in addition to problem description, k, and an empty array ans.

But there are three important questions: how we should calculate a(m,p), newP(m,p,k), and newK(m,p,k). If only there was a universal method, we would describe it here, but modes of calculating these vary too much for different problems, so we explain them on examples.

Discussion
If k is small enough, you may use brute force algorithm generating combinatorial objects in lexicographical order and simply take the k-th one. Our sophisticated approach is for cases when there are too many objects to iterate throw for passing time limit.

I couldn’t find any SRM problems requiring this algorithm easier than Division One – Level Three, so I suppose it will be more understandable if I give some other examples.

In simple cases you can calculate am,p directly and find k using a formula. Let’s suppose we need to find k-th lexicographically array of n integers from 0 to n-1, inclusive. This is basically the task of writing down number k in n-based notation, and can be solved easier, but we'll handle it in a manner that illustrates our idea.
In this simple case there are no constraints p on suffixes depending on previously set symbols, and am,p (actually simply am) is just a number of arrays of length m where each element is an integer between 0 and n-1, inclusive. am=mn, so we precompute it in array pow[m] before calling recursion.
#include <vector>
using namespace std;
class Arrays {
private:
	vector<int> pow;
	void getMthSymbol(int m, int k, vector<int> &ans) {
		if (m==0) return;
		ans.push_back(k/pow[m-1]);
		getMthSymbol(m-1,k%pow[m-1],ans);
	}
public:
	vector<int> getKth(int n, int k) {
		pow.resize(n);
		int i;
		pow[0]=1;
		for (i=1; i<n; ++i) pow[i]=pow[i-1]*n;
		vector<int> ans(0);
		getMthSymbol(n,k,ans);
		return ans;
	}
};
Re: Finding the Lexicographically K-th Combinatorial Object (response to post by Ferlon) | Reply
RSS