作者jeunder ()
看板CSSE
标题permutation algorithm
时间Fri Nov 17 02:20:35 2006
请教大家一个问题.
有一个阵列 x[2N] 要将其内容根据某个排列规则做 permutation.
规则如下:
x[0] -> x[0];
x[1] -> x[N];
x[2] -> x[1];
x[3] -> x[N+1];
:
:
x[2k] -> x[k];
x[2k+1] -> x[N+k];
:
:
x[2N-2] -> x[N-1]
x[2N-1] -> x[2N-1]
(0 <= k < N)
就是将 x 的偶数项依序放到 x[0 ~ N-1],
将 x 的奇数项依序放到 x[N ~ 2N-1].
希望能够做到时间复杂度为 O(N), 这显然很容易办到.
但是我又希望空间复杂度能够是 O(1), 也就是不可以有随 N 而变大的暂存变数.
这是否有可能办到?
感觉上似乎和离散数学里面的 permutation group 有关?
想请教大家的想法. 谢谢. :)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.64.148.4