Find n-th lexicographically permutation of a string

Find n-th lexicographically permutation of a string

Complexity: O(string length)

 

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const int max_char = 26;
	const int max_fact = 20;
	ll fact[max_fact];
	void factorials()
	{
	//cerr << "test\n";
	fact[0] = 1;
	for(int i = 1; i < max_fact; i++){
	fact[i] = fact[i - 1] * i;
	}
	}
	void nPermute(string str, int n)
	{
	factorials();
	//cerr <<str << " "<<n<<endl;
	int l = str.size();
	// count the frequencies all character
	int freq[max_char] = {0};
	for(int i = 0; i < l; i++)
	freq[str[i] - 'a']++;
	char out[max_char];
	// iterate till sum equals n
	int sum = 0;
	int k = 0;
	while(sum != n)
	{
	sum = 0;
	//cerr << "te--st\n";
	for(int i = 0; i < max_char; i++)
	{
	if(freq[i] == 0) continue;
	//remove character
	freq[i]--;
	// calculate sum after fixing a particular charater
	int xSum = fact[l - 1 - k];
	for(int j = 0; j < max_char; j++)
	xSum /= fact[freq[j]];
	sum += xSum;
	//if sum > n fix that char as present char and update sum
	// and required nth after fixing charat that position
	if(sum >= n){
	out[k++] = i + 'a';
	n -= (sum - xSum);
	break;
	}
	if(sum < n)
	freq[i]++;
	}
	}
	for(int i = max_char - 1; k < l && i >= 0; i--)
	if(freq[i]){
	out[k++] = i + 'a';
	freq[i++]--;
	}
	out[k] = '\0';
	cout << out << endl;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int n;
	string s;
	cin >> s >> n;
	nPermute(s, n);
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Find n-th lexicographically permutation of a string .cpp hosted with ❤ by GitHub

Share: