JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Finding the Lexicographically K-th Combinatorial Object
 Finding the Lexicographically K-th Combinatorial Object | Reply NameFinding the Lexicographically K-th Combinatorial ObjectProblemFrom all combinatorial objects of length n generated by specified rules you need to find the lexicographically k-th one.SolutionLet 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 &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.DiscussionIf 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 using namespace std; class Arrays { private: vector pow; void getMthSymbol(int m, int k, vector &ans) { if (m==0) return; ans.push_back(k/pow[m-1]); getMthSymbol(m-1,k%pow[m-1],ans); } public: vector getKth(int n, int k) { pow.resize(n); int i; pow[0]=1; for (i=1; i ans(0); getMthSymbol(n,k,ans); return ans; } }; ```
 Re: Finding the Lexicographically K-th Combinatorial Object (response to post by Ferlon) | Reply
 Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Finding the Lexicographically K-th Combinatorial Object Previous Thread  |  Next Thread