作者ykjiang (York)
看板CSSE
標題Re: permutation algorithm
時間Fri Nov 17 12:14:26 2006
我沒有更快的方法,不過在 Python 下可以這樣寫:
>>> from numpy import *
>>> N=5
>>> a=arange(2*N) # creates an array for demo
>>> a # views the content of the array
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> a.shape=(N,2)
>>> a.transpose().ravel()
array([0, 2, 4, 6, 8, 1, 3, 5, 7, 9])
上面拆成兩行寫,其實只要一行就搞定了:
>>> a.reshape(N,2).transpose().ravel()
array a 經過三次轉換就得到答案了。
由上面可以看出,如果有特殊的硬體來進行矩陣運算的話,
可以加速很多。
※ 引述《jeunder ()》之銘言:
: 請教大家一個問題.
: 有一個陣列 x[2N] 要將其內容根據某個排列規則做 permutation.
: 規則如下:
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.226.118
※ 編輯: ykjiang 來自: 211.74.226.118 (11/17 12:31)
→ ykjiang:有想到一個 space O(1) ,但 time 要 O(N^2) 的方法 11/18 00:32
→ ykjiang:要用到多次的小 transpose 及 swap ,不是很實用 11/18 00:33