作者semop (semop)
看板CSSE
标题Re: permutation algorithm
时间Sat Nov 18 16:58:35 2006
※ 引述《jeunder ()》之铭言：
: 就是将 x 的偶数项依序放到 x[0 ~ N-1],
: 将 x 的奇数项依序放到 x[N ~ 2N-1].
: 希望能够做到时间复杂度为 O(N), 这显然很容易办到.
: 但是我又希望空间复杂度能够是 O(1), 也就是不可以有随 N 而变大的暂存变数.
: 这是否有可能办到?
: 感觉上似乎和离散数学里面的 permutation group 有关?
: 想请教大家的想法. 谢谢. :)
一个尽量减少空间使用量的做法：
时间复杂度 O(N)
空间复杂度也是 O(N), 但实际上只需要使用 n / 2 个 bit 而已
简单来说，就是从 i = 1 开始，直接将 x[i] 的内容放到正确位置，然後将原本
该位置资料放到下一个正确位置，直到写回 x[i] 为止。
但这样往往会有漏掉的，就必须要检查 i < n, i = 3, 5 ... 的状况。
实测需要处理的 i 值：
n = 2: 1
n = 3: 1
n = 4: 1, 3
n = 5: 1, 3
n = 6: 1
n = 7: 1
n = 8: 1, 3, 5, 7
n = 9: 1, 3
n = 10: 1
n = 11: 1, 3, 5, 7, 9
n = 12: 1, 5
n = 13: 1, 5
n = 14: 1, 3, 9
n = 15: 1
n = 16: 1, 3, 5, 7, 11, 15
n = 17: 1, 3, 5, 11
n = 18: 1, 3, 5, 7, 15
n = 19: 1
n = 20: 1, 3, 7, 13
看不出规则来，似乎不太容易再简化。
----------------------------------------------------------------------
#include <stdio.h>
#include <malloc.h>
void dump(int *x, int n, int t) {
int i;
for(i = 0; i < n; i++)
if(i == t) { printf("[%02d]", x[i]); } else { printf(" %02d ", x[i]); }
printf("\n");
}
void permutation(int* x, char* z, int n, int p) {
int a = p;
int b = p / 2 + (p % 2) * (n / 2);
int c = x[a];
int t;
do {
t = x[b]; x[b] = c; c = t; // swap(c, x[b])
a = b;
b = b / 2 + (b % 2) * (n / 2);
if(a % 2) z[a / 2] = 1;
dump(x, n, a);
}
while(a != p);
}
void main(int argc, char* argv[]) {
int i, n, t;
int* x;
char* z;
if(argc < 2) return;
sscanf(argv[1], "%d", &n); if(n <= 0) return;
t = n * 2;
x = malloc(t * sizeof(int));
z = calloc(n / 2, sizeof(char));
for(i = 0; i < t; i++) x[i] = i;
dump(x, t, t);
for(i = 1; i < n; i += 2) if(z[i / 2] == 0) {
printf("[%d]\n", i);
permutation(x, z, t, i);
}
dump(x, t, t);
}
--
※ 编辑: semop 来自: 61.222.173.26 (11/18 19:12)