2014
11-19

# LeetCode-Permutation Sequence[数组]

### Permutation Sequence

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):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

$a_2, a_3, …, a_n$, 共计$n-1$个元素，$n-1$个元素共有$(n-1)!$个排列，于是就可以知道 $a_1 = k / (n-1)!$。

\begin{eqnarray}
k_2 &=& k\%(n-1)! \nonumber \\
a_2 &=& k_2/(n-2)! \nonumber \\
k_{n-1} &=& k_{n-2}\%2! \nonumber \\
a_{n-1} &=& k_{n-1}/1! \nonumber \\
a_n &=& 0 \nonumber
\end{eqnarray}

// LeetCode, Permutation Sequence
// 使用next_permutation()，TLE
class Solution {
public:
string getPermutation(int n, int k) {
string s(n, '0');
for (int i = 0; i < n; ++i)
s[i] += i+1;
for (int i = 0; i < k-1; ++i)
next_permutation(s.begin(), s.end());
return s;
}

template<typename BidiIt>
bool next_permutation(BidiIt first, BidiIt last) {
// 代码见上一题 Next Permutation
}
};


// LeetCode, Permutation Sequence
// 康托编码，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
string getPermutation(int n, int k) {
string s(n, '0');
string result;
for (int i = 0; i < n; ++i)
s[i] += i + 1;

return kth_permutation(s, k);
}
private:
int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; ++i)
result *= i;
return result;
}

// seq 已排好序，是第一个排列
template<typename Sequence>
Sequence kth_permutation(const Sequence &seq, int k) {
const int n = seq.size();
Sequence S(seq);
Sequence result;

int base = factorial(n - 1);
--k;  // 康托编码从0开始

for (int i = n - 1; i > 0; k %= base, base /= i, --i) {
auto a = next(S.begin(), k / base);
result.push_back(*a);
S.erase(a);
}

result.push_back(S[0]); // 最后一个
return result;
}
};


1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}