37 lines
1021 B
C++
37 lines
1021 B
C++
/** A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
|
|
012 021 102 120 201 210
|
|
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? */
|
|
|
|
#include "0.hpp"
|
|
|
|
#define _max 10
|
|
#define _end 1000000
|
|
|
|
string ch = "0123456789";
|
|
uu count[_max] = {};
|
|
uu num[_max] = {1, 1};
|
|
|
|
int main()
|
|
{
|
|
uu locale = _end - 1;
|
|
string out = "";
|
|
|
|
for(unsigned int i = 2; i < _max; i++) {
|
|
num[i] = num[i - 1] * i;
|
|
//cout << num[i] << endl;
|
|
}
|
|
|
|
for(unsigned int i = _max - 1; i >= 1; i--) {
|
|
count[i] = locale / num[i];
|
|
locale %= num[i];
|
|
//cout << count[i] << endl;
|
|
out += ch[count[i]];
|
|
ch = ch.substr(0, count[i]) + ch.substr(count[i] + 1);
|
|
//cout << out << '\t' << ch << endl;
|
|
}
|
|
|
|
cout << out + ch << endl;
|
|
|
|
return 0;
|
|
}
|