Re: [問題] array shuffle
※ 引述《BaronDavis5 (Baron Davis)》之銘言：
: 我也是用這個方法，主要idea是很久以前離散數學學過的一個permutation group
: 我猜應該是和前述cycle decomposition類似概念的東西
: 但是我之前把它寫出來後，發現不同長度時，permutation group的量不一定
: 比如在元素長度8時，就存在二個permutation group (註1)
: 但是在長度20時，就只存在一個permutation group(皆扣掉頭尾元素)
: 目前也想不出有沒有什麼方法可以找出那些沒交集permutation group...
: (註1)
: index 0 1 2 3 4 5 6 7
: original 1 3 5 7 2 4 6 8
: to 1 2 3 4 5 6 7 8
: permutation group (1 2 4) (3 6 5)
: (2 4 1),(6 5 3)
我的想法不很像,而且稍有些降級,是O(n^2)時間複雜度.
{1,3,5,7;2,4,6,8}
這個陣列,如果我先將最外圍未正確歸定位的數字做對,就是
3 _ _
{1,2,5,7;2,4,7,8}
6
意思是陣列中存在著左邊{3,5,7}與右邊{2,4,6}子陣列,右子陣列的頭要變成
左邊的頭,左子陣列的尾要變成右邊的尾;因此,2將3擠掉,7將6擠掉.
接著問題是,擠出來的3,6該擺在哪裏呢? 分別擺在原來的2,7位置嗎?
若程式這樣寫的話,得到的結果只是一個很接近答案的陣列,裏頭仍有部份凌亂.
但如果以更小步驟來想,擠出來的3應該把右邊的5往右邊擠過去,
擠出來的6則應該把左邊的4往左邊擠過去,
如果真把這推擠動作編入演算法中,時間就是O(n^2)複雜度.
其實這想法來自於較高階的想法,像俄羅斯娃娃那樣一層一層處理. 像以下陣列
{1,3,5,7,9,11;2,4,6,8,10,12}
先對調第一層子陣列,
{1,[2,4,6,8,10];[3,5,7,9,11],12}
再對調第二層子陣列,
{1,2,[3,5,7,9];[4,6,8,10],11,12}
再對調第三層子陣列,
{1,2,3,[4,6,8];[5,7,9],10,11,12}
如此做下去,一定能得到答案.
但這做法是O(n^2).
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.213.154
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 8 之 9 篇)：
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
