t******e
发帖数: 1293 | 1 给你一堆数字12345，再给一个数字k，让求出第k小的排列数
如k=0，那么输出12345
如k=1，输出12354
如k=2，输出12435 |
h*********i
发帖数: 116 | |
t******e
发帖数: 1293 | 3 假设没有重复的
【在 h*********i 的大作中提到】
: 重复的怎么算 12344算什么 算一次还是两次
|
p*********a
发帖数: 21 | 4 classical Cantor expansion problem!
gxxgle it, you will get the answer. |
q******u
发帖数: 46 | 5 可以算出第一位是floor((k-1)/(n-1)!)+1，剩余的递归就好了。非递归的程序如下：
void print_comb_kth(int n, int k){
int fac = 1;
int i, j;
int *buf;
for (i=2; i<=n; i++) fac*=i;
if (k>fac || k<1){
printf("Index out of range!\n");
return;
}
if (n==1){
printf("1\n");
return;
}
buf = (int*) malloc(sizeof(int)*n);
for (i=1; i<=n; i++) buf[i-1] = i;
for (i=1; i
fac /= (n+1-i);
printf("%d", buf[(k-1)/fac]);
j = (k-1)/fac;
while (j
buf[j] = buf[j+1];
【在 t******e 的大作中提到】
: 给你一堆数字12345，再给一个数字k，让求出第k小的排列数
: 如k=0，那么输出12345
: 如k=1，输出12354
: 如k=2，输出12435
|
T*****9
发帖数: 2484 | 6 这个算法不好
字典序法有专门的算法
【在 q******u 的大作中提到】
: 可以算出第一位是floor((k-1)/(n-1)!)+1，剩余的递归就好了。非递归的程序如下：
: void print_comb_kth(int n, int k){
: int fac = 1;
: int i, j;
: int *buf;
: for (i=2; i<=n; i++) fac*=i;
: if (k>fac || k<1){
: printf("Index out of range!\n");
: return;
: }
|
q******u
发帖数: 46 | 7 不就是while可以省掉嘛，改成个链表就好了，O(1)。我就是懒...其他应该都是最优的
【在 T*****9 的大作中提到】
: 这个算法不好
: 字典序法有专门的算法
|
H*M
发帖数: 1268 | 8 这题的答案是？？到底什么经典算法啊？谁能给个提示?
谢了！
没想到排列组合这些有这么多trick..
【在 t******e 的大作中提到】
: 给你一堆数字12345，再给一个数字k，让求出第k小的排列数
: 如k=0，那么输出12345
: 如k=1，输出12354
: 如k=2，输出12435
|
a****n
发帖数: 1887 | 9 先sort,然后next_permutation 掉K次 |
H*M
发帖数: 1268 | 10 suppose是不能用next_permutation的吧
【在 a****n 的大作中提到】
: 先sort,然后next_permutation 掉K次
|
|
|
a****n
发帖数: 1887 | 11 这篇我觉得写得最清楚
http://www.cppblog.com/yuyang7/archive/2009/03/30/78403.html
code:
bool next_permutation(int[] vals)
{
int n = vals.Length;
if (n < 2) return false;
while (true)
{
int i = n - 1;
while (i > 0 && vals[i] <= vals[i - 1]) --i;
if (i == 0) return false;
--i;
int j = n - 1;
while (vals[j] <= vals[i]) --j;
swap(vals[i],vals[j]);
int begin = ++i, end = vals. |
b****j
发帖数: 78 | 12 算法的python实现是这样的，很容易转化成C/C++:
def get_kth_permutation(k, n):
p = []
for i in xrange(n):
p.append(k % (i + 1))
k //= i + 1
for i in xrange(n):
for j in xrange(i + 1, n):
if p[j] <= p[i]:
p[i] += 1
return list(reversed(p))
【在 H*M 的大作中提到】
: 这题的答案是？？到底什么经典算法啊？谁能给个提示?
: 谢了！
: 没想到排列组合这些有这么多trick..
|
g*******y
发帖数: 1930 | 13 这个方法比前面那个慢，尤其如果k很大很大的话
我觉得做k-th permutation的题不能用next permutation
【在 a****n 的大作中提到】
: 先sort,然后next_permutation 掉K次
|
b***e
发帖数: 1419 | 14 我错乱了, 原来是鞭尸.
【在 H*M 的大作中提到】
: 这题的答案是？？到底什么经典算法啊？谁能给个提示?
: 谢了！
: 没想到排列组合这些有这么多trick..
|
a****n
发帖数: 1887 | 15 恩
【在 g*******y 的大作中提到】
: 这个方法比前面那个慢，尤其如果k很大很大的话
: 我觉得做k-th permutation的题不能用next permutation
|
