Re: [問卦] 這段code要怎麼打?已回收

看板Gossiping作者TWN48 (台灣48)時間7年前 (2018/04/16 22:36)推噓5(5推 0噓 5→)

留言10則, 10人參與討論串12/18 (看更多)

※ 引述《NTUgambler (二十世紀末的賭徒)》之銘言： : 今天有編號1~6的椅子環繞一圈 : 我要在上面擺3顆蘋果 : 如果擺放1號2號3號 : 簡記為{1,2,3} : 今天我想把相似的擺法分在同一群 : 意即{1,2,3}和{2,3,4}擺法相似放置同一群 : 我的判斷式該如何描寫呢? : 我的想法是{x1,x2,x3} {y1,y2,y3} : 若|x2-x1|=|y2-y1|且|x3-x2|=|y3-y2| 則能分到同一群 : 但是好像就無法處理頭尾相鄰的部分 : 意即{1,2,3}和{1,2,6}其實是要同一群的 : 還有我{}的index都是由小排到大 : 請問我的判斷式要怎麼寫呢? 先定義好幾個名詞： N: 你的環的大小（椅子的數量），以這個例子 N = 6 index list: 元素的 index 形成的 list，由小到小，就是你舉的 {1, 2, 3}, {2, 3, 4} 這樣的東西 distance list: index list 兩兩元素之間距離形成的 list，例如 index list {1, 2, 3} (N=6) 的 distance list 是 {1, 1, 4} index list {1, 5, 6} (N=6) 的 distance list 是 {4, 1, 1} 換個表示法： distance_list(6, {1, 2, 3}) == {1, 1, 4} distance_list(6, {1, 5, 6}) == {4, 1, 1} signature distance list: 給定一個有 n 個元素的 distance list，因為它是排在環上，所以選定不同元素當作「開頭」，可以有 n 種同樣意義的寫法，例如 {1, 1, 4}, {1, 4, 1}, {4, 1, 1} 在環上都代表相同的排列，只是開頭選得不同。所以我們定義 signature distance list 是這群 list 當中最「大」的一個。 list 比大小則是類似字典排序（逐個元素比對）： for i = 0..(n-1) 第一個 a[i] != b[i] 時，若 a[i] > b[i] 則說 list a > b a[i] < b[i] 則說 list a < b 若比到最後 a[i] 和 b[i] 都相等，則說 list a == b signature({1, 1, 4}) == signature({1, 4, 1}) == signature({4, 1, 1}) == {4, 1, 1} 所以你的問題就可以這樣簡化：當給定環的大小 N，如何判斷兩個 index list A, B 是代表同樣的排列解法就是：判斷 index list A, B 的 signature distance list 是否相等，也就是 signature(distance_list(A)) == signature(distance_list(B)) （以上依照你的範例，index 用 1-base，以下為了方便改為 0-base，意思是一樣的）用 python implement 大概是這樣： === def distance(n, index_a, index_b): return (index_b - index_a) if index_b > index_a else \ ((index_b + n) - index_a) def distance_list(n, index_list): return [distance(n, index_list[i], index_list[(i + 1) % len(index_list)]) \ for i in range(len(index_list))] def circular_list_start_at(l, start_at): return l[start_at:] + l[:start_at] def signature(n, distance_list): lists = [circular_list_start_at(distance_list, i) \ for i in range(len(distance_list))] return max(lists) def is_equivalent(n, index_list_a, index_list_b): return signature(n, distance_list(n, index_list_a)) == \ signature(n, distance_list(n, index_list_b)) === >>> is_equivalent(6, [0, 1, 2], [0, 1, 5]) True -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.30.32 ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1523889363.A.CD5.html ※ 編輯: TWN48 (140.112.30.32), 04/16/2018 22:36:18

→

jimmy8343

04/16 22:36, 7年前 , 1^F

04/16 22:36, 1^F

推

d86249

04/16 22:37, 7年前 , 2^F

04/16 22:37, 2^F

→

derrick1220

04/16 22:37, 7年前 , 3^F

04/16 22:37, 3^F