60. Permutation Sequence

Total Accepted: 56468 
Total Submissions: 221337 
Difficulty: Medium
The set  [1,2,3,…,n]  contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Subscribe to see which companies asked this question
Hide Tags
 
Backtracking Math
Hide Similar Problems
 
(M) Next Permutation (M) Permutations
分析:
率直に言って、この問題は難しいですね.法則の総括はネットから来ています.コードはおばさんの法則に基づいて書いた!
原文分析:http://www.cnblogs.com/boring09/p/4253508.html
1つ1つのシミュレーションは必ずタイムアウトしなければなりません.生算だけが法則を探しています.
例えばn=4、k=10で、まずn=4のすべての配列を書きます.
(1)1 2 3 4<−1番目のシーケンス2 3 4,シーケンス(2)1 2 4 3(3)1 3 2 4(4)1 3 4 2(5)1 4 2 3(6)1 4 3 2<−最後のシーケンス4 3 2,逆シーケンス(7)2 1 3 4(8)2 1 4 3(9)2 3 1 4(10)2 3 4 1<−ターゲットシーケンス(11)2 4 1 3 3(12)2 4 3 1(13)3 1 2 4(14)3 1 4(15)3 1 4...(後の省略)
仮にk=10の最終結果がABCDであるとする
a)まずAを確定する.
4!=24、ここ4!個の組み合わせのうち、k=10個目の先頭Aを探すと、Aが1~nのうちのceiling{k/3!}=1.666=2個(ceilingは全体を取ることを表す)、すなわちA=2である.最後に2を1~nから削除し、kを更新し、k=k%3!=4(n-1)!で4番目のグループの先頭Bを探します)
b)次にBを確定する.
k=4>2だから!=2,Bは1~nのうちのceiling{k/2!}=2つ、2つ前に削除されたので、現在2番目の数字は3、すなわちB=3です.最後に3を1~nから削除し、k=k%2を更新!=2
c)次にCを見る.
k=0は,我々が要求するシーケンスが必ずあるシーケンスの末尾にあることを示すので,その後の数字は大きいものから小さいものへ順次出力すればよい,すなわちC=4である.4を1~nから削除し、続行します.
d)最後にDを見る.
k=0であるため、同様に、D=1が得られる.
おばさんにひざまずいて・・・、おばさんのおかげで、上の考えはコードに変換されました.

class Solution {
public:
	string getPermutation(int n, int k) {
		string result="";
		string numstr(n+1,'*');
		for(int i=1;i<=n;i++)
			numstr[i]=i+'0';
		dfs(result,numstr,n,k);
		return result;
	}

	void dfs(string &result,string &numstr,int n,int curk)
	{
		if(numstr.size()==1)//snumtr[0]=‘*’，      
			return;
		int n1=factorial(n-1);//   
		int kk=ceil(1.0*curk/n1);//    
		if(kk==0)
		{
		    //k=0                    
		    //                      
			sort(numstr.begin(),numstr.end());
			for(int i=0;i<numstr.size()-1;i++)
				result+=numstr[numstr.size()-i-1];
			return;
		}
		result+=numstr[kk];
		numstr.erase(numstr.begin()+kk);//  
		dfs(result,numstr,n-1,curk%n1);
	}
	//    n     
	int factorial(int n)  
	{  
		int sum = 1;  
		for(int j = 2; j <= n; j++)  
			sum *= j;  
		return sum;  
	}  
};

付暴力方法(タイムアウト):

class Solution {
public:
    void next_permutation(string& nums) {    
            if(nums.empty() || nums.size()==1)    
                return;    
            string::iterator ite1=nums.end()-1;    
            for(;;)    
            {    
                string::iterator ite2=ite1;    
                ite1--;    
                if(*ite1 < *ite2)    
                {    
                    string::iterator itej=nums.end();    
                    while(!(*ite1 < *--itej));    
                    iter_swap(ite1,itej);    
                    reverse(ite2,nums.end());    
                    return;    
                }    
                    
                if(ite1==nums.begin())    
                {     
                   reverse(nums.begin(),nums.end());    
                   return;    
                }    
            }    
        } 
    string getPermutation(int n, int k) {
        string result(n,'0');
        for(int i=1;i<=n;i++)
            result[i-1]=i+'0';
        for(int i=0;i<k-1;i++)//  k-1 
           next_permutation(result);
        return result;   
    }
};

注:本博文はEbowTangオリジナルで、その後も本論文を更新する可能性があります.転載する場合は、必ずこの情報をコピーしてください!
原文住所:http://blog.csdn.net/ebowtang/article/details/51648717
原作者ブログ:http://blog.csdn.net/ebowtang
このブログLeetCodeの問題解索引:http://blog.csdn.net/ebowtang/article/details/50668895