Lexicographic rank of a string(without duplicate character)

লেক্সিকোগ্রাফিক বলতে বুঝায় অ্যালফাবেটিকাল অর্ডার। যেমনঃ কোন স্ট্রিং "xyz" হলে, আমরা বলতে পারি এই স্ট্রিং এর লেক্সিকোগ্রাফিক অর্ডারের প্রথমে আছে "xyz", এরপরে "xzy" .. অর্থাৎ স্ট্রিং এর সকল পারমুটেশন এর সিরিয়াল, যারা কিনা ছোট থেকে বড় আকারে সর্টেড অবস্থায় আছে। এখন এরকম একটি স্ট্রিং দেখে আমাদের বলতে হবে এর র‍্যাঙ্ক কত। যেমনঃ "abc" এর ক্ষেত্রে, rank of "abc" = 1, rank of "acb" = 2 .... এভাবে।
একদম ব্যাসিকভাবে চিন্তা করলে আমরা সকল পারমুটেশন জেনারেট করে দেখতে পারি যে স্ট্রিং টি কততম পারমুটেশন এর সাথে মিলে গেছে। তাহলে সেটিই আমাদের স্ট্রিং এর র‍্যাঙ্ক।

	#include <bits/stdc++.h>
	using namespace std;
	int main()
	{
	string s;
	cin >> s;
	string temp = s; // store the string to find matching
	sort(s.begin(),s.end()); // sort in ascending order
	int rank = 1;
	do
	{
	if(s == temp)
	{
	cout << "Rank is : " << rank << endl;
	return 0;
	}
	rank++;
	}while(next_permutation(s.begin(),s.end()));
	return 0;
	}

view raw lexocigraphic rank.cpp hosted with ❤ by GitHub

এভাবে আমাদের টাইম কমপ্লেক্সিটি অনেক বেড়ে যাবে, প্রায় এক্সপোনেন্ট হারে!! (exponent) এজন্য আমাদের আরো ভালো এপ্রোচ দরকার।
আমরা একটি স্ট্রিং ধরি, "FRIEND" এর র‍্যাঙ্ক বের করতে হবে। এখানে প্রথম ক্যারেক্টার  "F" এবং "F" এর চেয়ে ছোট ২ টি ক্যারেক্টার আছে ("D", "E") এবং "F" কে তার জায়গায় ফিক্সড করলে আমাদের বাকি থাকে আরো ৫ টি জায়গা এবং "F" এর আগের ২ টি ক্যারেক্টার ঐ ৫ টি জায়গায় বসতে পারবে ৫ ফ্যাক্টরিয়াল (5!) উপায়ে। তাহলে ২ টির জন্য কম্বিনেশন হবে ২*৫!
এখন আমরা তাহলে "F" এর কাজ শেষ হলে, "F" কে ফিক্সড করে দেই। মানে "F" নিয়ে আমাদের আর মাথা ব্যথা করতে হবে না। এখন দ্বিতীয় ক্যারেক্টার "R" নিয়ে দেখি। "R" এর চেয়ে ছোট ৪ টি ক্যারেক্টার আছে ("D", "E", "I", "N"). ["F" কে আমরা ফিক্সড করে দিয়েছি, কাজেই "F" বাদ] 
তাহলে আমরা "R" এর জন্য পাবোঃ ২*৫! + ৪*৪! (আগের "F" এরগুলোও ধরতে হবে)।
একই ভাবে আমরা বাকি ক্যারেক্টার গুলোর জন্য করে ফেলিঃ

"I" = 2*5! + 4*4! + 2*3!
"E" = 2*5! + 4*4! + 2*3! + 1*2!
"N" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1!
"D" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0!
তাহলে, "FRIEND" এর জন্য র‍্যাঙ্ক হবে ঃ 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0! = 351
যেহেতু, র‍্যাঙ্ক ১ থেকে শুরু হয়, কাজেই আমাদের ফাইনাল রেজাল্ট হবে 1 + 351 = 352.

	#include <bits/stdc++.h>
	using namespace std;
	int factorial(int n)
	{
	int f = 1;
	while(n>0)
	f *= n,n--;
	return f;
	}
	int main()
	{
	string s;
	cin >> s;
	string temp = s; // store the string to find matching
	sort(s.begin(),s.end()); // sort in ascending order
	int rank = 1;
	int len = temp.size();
	for(int i = 0; i < len; i++)
	{
	char ch = temp[i];
	int counter = 0;
	for(int j = 0; j < len; j++)
	{
	if(s[j] == ch)
	{
	s[j] = '#'; // fix the character
	break;
	}
	else if(s[j] != '#')
	counter++;
	}
	rank += counter*factorial(len-i-1);
	}
	cout << "Rank is : " << rank << endl;
	return 0;
	}

view raw lexicographic rank factorial.cpp hosted with ❤ by GitHub

এর কপ্লেক্সিটি O(n²)। আমরা একটু বুদ্ধি খাটালে এর কমপ্লেক্সিটিকে কমিয়ে আনতে পারবো। এজন্য আমরা কিউমুলেটিভ ভাবে প্রতিটি ক্যারেক্টারের চেয়ে ছোট ক্যারেক্টারকে একটি অ্যারেতে সেভ করে রাখবো।এরপরে প্রতিবার সেখান থেকে কাউন্ট নিয়ে আমরা কাজ করবো O(n) কপ্লেক্সিটিতে

	#include <bits/stdc++.h>
	using namespace std;
	int counter [256];
	int factorial(int n)
	{
	int f = 1;
	while(n>0)
	f *= n,n--;
	return f;
	}
	void make_array(string s)
	{
	for(int i = 0; i < s[i]; i++)
	counter[s[i]]++;
	for(int i = 1; i < 256; i++)
	counter[i] += counter[i-1];
	}
	void update_counter(char ch)
	{
	for(int i = ch; i < 256; i++)
	counter[i]--;
	}
	int main()
	{
	string s;
	cin >> s;
	int len = s.size();
	int rank = 1;
	int total = factorial(len);
	make_array(s);
	//contains count of characters which are present
	// in s and are smaller than i
	for(int i = 0; i < len; i++)
	{
	total /= len - i;
	//count number of chars smaller than s[i]
	//fron s[i+1] to s[len-1]
	rank += counter[s[i]-1]*total;
	//reduce count of characters greater than s[i]
	update_counter(s[i]);
	}
	cout << "Rank is : " << rank << endl;
	return 0;
	}

view raw lexicographic rank factorial O(n).cpp hosted with ❤ by GitHub