f*********m
发帖数: 726 | 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*********m
发帖数: 726 | |
c**m
发帖数: 535 | |
I*****8
发帖数: 37 | 4 这道题和next permutation 差不多把，我觉得的话，主要的思想就是swap，数学上来
说就是证明这些充要条件：
http://www.tsechung.com/wordpress/2012/07/16/permutation-sequen |
g**********t
发帖数: 475 | 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*****8
发帖数: 37 | 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***U
发帖数: 2406 | 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**********t
发帖数: 475 | 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*********m
发帖数: 726 | 9 能说说思路吗？
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 ++){
|
