project euler problem 24

Lexicographic permutations

Problem 24

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?

Answer: 2783915460 Completed on Thu, 10 Oct 2013, 15:48

剛開始用了康托計算的，但是一直不對，郁悶死了，然後直接用了next_permutation，因為1000000，是以還擔心時間逾時呢，但是一運作就很快，直接就用這函數了哈哈……

#include <iostream>
#include <map>
#include <deque>
#include <queue> //包含優先隊列
#include <stack>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
int main()
{
    int a[10]={0,1,2,3,4,5,6,7,8,9},k=1;
    while(k!=1000000) {next_permutation(a,a+10);k++;}
    for(int i=0;i<10;i++)
        cout<<a[i];
    cout<<endl;
    return 0;
}