作者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)