作者ykjiang (York)
看板CSSE
标题Re: permutation algorithm
时间Sat Nov 18 11:45:10 2006
◆ From: 61.228.199.201
1F：推 xcycl:原 po 是问想做到 space 复杂度为 O(1), 不是 time ... 11/17 21:43
2F：推 ykjiang:我也看走眼了 :p 11/17 23:23
3F：推 ledia:他的意思是 in place permutation ? 11/18 01:09
4F：推 b6s:唔，大概是我弄错了，可这不是 swap 头尾成对的偶数项就好？ 11/18 04:13
5F：推 b6s:btw, 我所谓头尾成对偶数项，尾巴那只是倒数的偶数项。 11/18 04:21
利用多次 swap，有一个 space O(1), time O(N^2) 的方法，
过程举例如下：
0 (1 2) (3 4) (5 6) (7 8) 9
0 2 (1 4) (3 6) (5 8) 7 9
0 2 4 (1 6) (3 8) 5 7 9
0 2 4 6 (1 8) 3 5 7 9
0 2 4 6 8 1 3 5 7 9
每个 pass 都把括号内的数对 swap...
这其实是以 in place 法求转置矩阵的一个特例，
换句话说，它是求 N by 2 矩阵的转置（transpose）
有兴趣的人，可以帮忙推广成适用於 n by m 矩阵
的转置矩阵。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.59.14.146
※ 编辑: ykjiang 来自: 61.59.14.146 (11/18 12:12)
6F：推 drkkimo:好方法 11/18 20:56
7F：推 ykjiang:从这个方法出发，我几乎可以确定 space O(1), time O(N) 11/19 02:09
8F：→ ykjiang:的方法存在，有兴趣的人可以推推看 :) 11/19 02:10
9F：推 b6s:虽然 swap 的顺序不同，但我想到的跟这一样，推～ 11/20 01:19
10F：→ b6s:BTW, 这个问题应该可以视为 bipartite，所以 space O(1) 应该 11/20 01:19
11F：→ b6s:可是同时要 time O(N) 就不知道了，感觉上好像顶多 O(NlogN) 11/20 01:20