#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <string>


using namespace std;


void print(vector<int> v){
	for (int i = 0; i<v.size(); i++)
		cout << v[i] << " ";
	cout << "\n===================================\n";
}

void generate_int_array(vector<int> &v, int n){
	for (int i = 0; i<v.size(); i++)
		v[i] = rand() % 100;
}

string generate_string(int cnt_of_char){
	char chars[36] = {
		'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', 'a', 's', 'd', 'f', 'g',
		'h', 'j', 'k', 'l', 'z', 'x', 'c', 'v', 'b', 'n', 'm', '1', '2', '3', '4',
		'5', '6', '7', '8', '9', '0' };
	string result="";
	for (int i = 0; i < cnt_of_char; i++)
		result += chars[rand()%36];
	return result;
}


void per(vector<int> &a, vector<int> &b, int i, int &cnt){
	if (i == a.size())
		cnt++;
	else{
		for (int j = 0; j<a.size(); j++){
			if (b[j] == 0){
				b[j] = 1;
				a[i] = j + 1;
				per(a, b, i + 1, cnt);
				b[j] = 0;
			}
		}
	}
}

/*
*
*/
int main() {
	srand(time(0));
	int n, cnt = 0;
	time_t start_time, finish_time;

	cout << "Enter count of elements";
	cin >> n;
	vector<int> v(n), b(n);
	generate_int_array(v, n);

	//INT STL NEXT_PERMUTATION
	sort(v.begin(), v.end());
	start_time = time(NULL);
	do{
		cnt++;
		//print(v);
	} while (next_permutation(v.begin(), v.end()));
	finish_time = time(NULL);
	cout << "\nTime of STL next_permutation: " << finish_time - start_time << ". Cnt of STL permutation: " << cnt;
	cout << endl;


	//INT MY PERMUTATION
	start_time = time(NULL);
	cnt = 0;
	per(v, b, 0, cnt);
	finish_time = time(NULL);
	cout << "\nTime of my permutation: " << finish_time - start_time << ". Cnt of MY permutation: " << cnt << endl;


	//STRING STL NEXT_PERMUTATION
	cnt = 0;
	vector<string> sv(n);
	for (int i = 0; i < sv.size(); i++)
		sv[i] = generate_string(5);
	sort(sv.begin(), sv.end());
	start_time = time(NULL);
	do{
		cnt++;
	} while (next_permutation(sv.begin(), sv.end()));
	finish_time = time(NULL);
	cout << "\nTime of STRING STL next_permutation: " << finish_time - start_time << ". Cnt of STRING STL permutation: " << cnt;
	cout << endl;


	return 0;
}