大家能说说(leecode) Permutation Sequence这道题后的数学思路吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

大家能说说(leecode) Permutation Sequence这道题后的数学思路吗？

大家能说说(leecode) Permutation Sequence这道题后的数学思路吗？# JobHunting - 待字闺中

f*m2012-07-16 07:07

1 楼

谢谢。
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):
"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.

f*m2012-07-16 07:07

2 楼

自己顶

c*m2012-07-16 07:07

3 楼

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

I*82012-07-16 07:07

4 楼

这道题和next permutation 差不多把，我觉得的话，主要的思想就是swap，数学上来
说就是证明这些充要条件：
http://www.tsechung.com/wordpress/2012/07/16/permutation-sequen

g*t2012-07-16 07:07

5 楼

Isn't it very slow to swap one array k times? Remember that k could be very
large! I attached my code using a different idea.Its complexity is O(n^2).
#include
#include
#include
#include
using namespace std;
int permutation(int n){
int p = 1;
for(int i = 1; i <= n; i ++){
p *= i;
}
return p;
}
string perSeq(int n, int k){
string output;
bool flag[10];
fill_n(flag, 10, false);
--k;
for (int i = 1; i <= n; i ++){
int a = permutation(n - i);
int b = k / a;
k = k % a;
for (int j = 1; j <= n; j ++){
if (flag[j] == false){
--b;
if (b < 0){
flag[j] = true;
output = output + boost::lexical_cast(j);
break;
}
}
}
}
return output;
}
int main(int argc, char **argv){
if (argc != 3){
cout << "Wrong number of parameter!!\n";
exit(1);
}
int n = atoi(argv[1]);
int k = atoi(argv[2]);
string str = perSeq(n, k);
cout << str << endl;
}

【在 I*****8 的大作中提到】

: 这道题和next permutation 差不多把，我觉得的话，主要的思想就是swap，数学上来
: 说就是证明这些充要条件：
: http://www.tsechung.com/wordpress/2012/07/16/permutation-sequen

I*82012-07-16 07:07

6 楼

额，稍微看懂了一点, 但不是很懂C++和boost/lexical_cast.hpp，也没法跑leetcode
，感觉应该是可以的，简单复述下你的意思：
比如Input: n=4, k=24.
首先 factorial(4)=24, 然后24-1=23
loop第一位到第四位，然后如下：
1. 第一位=(23/factorial(3))+1=4,
2. 第二位=(23%6)/(factorial(2))+1=3
3. 第三位=（（23%6）%2）/1+1=2
4. 第四位= （23%6%2%1+1=1.
Output:4321

very

【在 g**********t 的大作中提到】

: Isn't it very slow to swap one array k times? Remember that k could be very
: large! I attached my code using a different idea.Its complexity is O(n^2).
: #include
: #include
: #include
: #include
: using namespace std;
: int permutation(int n){
: int p = 1;
: for(int i = 1; i <= n; i ++){

C*U2012-07-16 07:07

7 楼

我觉得直接可以用数学的递归来做
首先通过k你可以确定第一个数字
比如n=3, k=4
因为我们知道1开头的有2个 2开头的有2个
所以我们可以确定这个数字肯定是2开头，
以此类推
这里用到以某一数字开头的n-1位数有(n-1)!那么多
请大牛们指教

【在 f*********m 的大作中提到】

: 谢谢。
: 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):
: "123"
: "132"
: "213"
: "231"
: "312"

g*t2012-07-16 07:07

8 楼

You stole my idea!! Just kidding.. My code is based on the same idea.

【在 C***U 的大作中提到】

: 我觉得直接可以用数学的递归来做
: 首先通过k你可以确定第一个数字
: 比如n=3, k=4
: 因为我们知道1开头的有2个 2开头的有2个
: 所以我们可以确定这个数字肯定是2开头，
: 以此类推
: 这里用到以某一数字开头的n-1位数有(n-1)!那么多
: 请大牛们指教

f*m2012-07-16 07:07

9 楼

能说说思路吗？

very

【在 g**********t 的大作中提到】