
Discussion (sequel) Another similar task is finding kth lexicographically permutation of n distinct integers from 0 to n1, inclusive. Here a_{m,p} is a number of permutations of m distinct elements, what is also doesn’t depend on previously set elements and thus can be marked as a_{m} (and a_{m}=m!). Even more, function newK also doesn’t depend on previously set elements – when we choose next element, we should just let through all permutations of length m starting with elements going lexicographically earlier than chosen one – and if this chosen one is number t (0based) from all now possible ones (with taking into account previously set elements), the number of all permutations let through will be a_{m1}*t, so we can set newK(m,k)=k%a_{m1}. But what is actually depend on previously set elements, it is function symbol(m,p,k). Here p means the set of already used elements. As we understand that number of all permutations of m elements starting with definite one is a_{m1}, we can calculate our required t=k/a_{m1}, and then find tth unused element. In code below we don’t perform operations of division and taking the remainder, but decrease the value of k iteratively instead; and array b[] stores marks for used elements.
#include <vector>
#include <cstring>
using namespace std;
class Permutations {
static const int c=15;
int a[c];
bool b[c];
int n;
void getMthSymbol(int m, int k, vector<int> &ans) {
int i;
if (m==0) return;
for (i=0; i<n; ++i) if (!b[i]) {
if (k>=a[m1]) k=a[m1]; else {
b[i]=1;
ans.push_back(i);
getMthSymbol(m1,k,ans);
break;
}
}
}
public:
vector<int> getKth (int nn, int k) {
int i;
n=nn;
a[0]=1;
for (i=1; i<=n; ++i) a[i]=a[i1]*i;
memset(b,0,sizeof(b));
vector<int> ans;
getMthSymbol(n,k,ans);
return ans;
}
};
For more complicated example, let’s look at problem in which we need to find kth lexicographically regular bracket sequence of length n. A regular bracket sequence is a sequence consisting of equal numbers of left and right brackets, and in every its suffix the number of left brackets is less than or equal to the number of right brackets. There a_{m,p} will be a number of suffixes of length m such that the difference between number of right brackets and number of left brackets in each of them is equal to p (let’s call it balance). So each suffix with zero balance is a regular bracket sequence itself. First of all, we calculate a_{m,p} using dynamic programming. There is only one (empty) suffix of length 0, and its balance equals to 0 too. Then, when we add one bracket to the left thus increasing length of the suffix on 1, we may come to zero balance only by adding left bracket to the suffix with balance 1 (a[i][0]=a[i1][1]), but we may come to nonzero balance by two possibilities – adding left or right bracket, decrease or increase balance (a[i][j]=a[i1][j1]+a[i1][j+1]). Then we start to reconstruct kth lexicographically regular bracket sequence. When we need to find kth suffix of certain length with zero balance, we simply add a left bracket to answer and go to finding suffix with balance 1, but when we need to find kth suffix of length m with nonzero balance p, we should look at k to make decision which kind of bracket to add. If the number of suffixes of length m1 with balance p+1 is greater than k, a suffix which must be added to already constructed left part of sequence is among them, but if this number is less than or equal to k, we need a suffix with balance p1. So we add to answer an appropriate bracket and go further.
#include <vector>
#include <string>
using namespace std;
class BracketsSequences {
private:
vector<vector<int> > a;
string ans;
void getMthSymbol(int m, int p, int k, string &ans) {
if (m==0) return;
if (p==0) {
ans+='(';
getMthSymbol(m1,p+1,k,ans);
return;
}
if (k<a[m1][p+1]) {
ans+='(';
getMthSymbol(m1,p+1,k,ans);
} else {
ans+=')';
getMthSymbol(m1,p1,ka[m1][p+1],ans);
}
}
public:
string getKth(int n, int k) {
int i,j;
a.resize(n+1);
for (i=0; i<=n; ++i) a[i].resize(n+2,0);
a[0][0]=1;
for (i=1; i<=n; ++i) {
a[i][0]=a[i1][1];
for (j=1; j<=i; ++j) a[i][j]=a[i1][j1]+a[i1][j+1];
}
ans="";
getMthSymbol(n,0,k,ans);
return ans;
}
};
You may use similar method for combinatorial objects that are not of length exactly n, but are of length at most n. For this you should use “empty” symbol with a_{m,p}=1 for p associated with it.
As you see, there may be many very different problems solved with a help of this approach. Time complexities of algorithms using it generally depend on time complexity of dynamic schemes of calculating a_{m,p}, but in some cases time complexity of searching an appropriate next symbol may be significant too. For example, if at some m number of suffixes a_{m1,p} depend directly on symbol chosen at this step, you may iterate over all possible symbols to find an appropriate (actually in our second example the situation is so, but there are only two different symbols), and if the number of possible symbols is great, and you, say, need to reply to many requests of getting combinatorial object by number, a naïve linear search may be too slow. So it is useful to prepare a cumulative array b_{m,p}=a_{m,0}+…+a_{m,p} (if we can enumerate all possible p’s 0based) and find an appropriate symbol and thus an appropriate p using binary search.
Perhaps last to add: Beware of trying to construct combinatorial objects from the end to the beginning! As we are speaking about lexicographic order, we should fix elements going from left to right, not vice versa. Of course, there are problems in which both approaches work correctly, but it is not right in general. 