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
|