→ hwanger : 看不懂原PO的算法 冏 提供一個 若|s|>=2k 則任意相 09/17 09:41
→ hwanger : 鄰兩個都可以在其他不動的情況下互換 如考慮 09/17 09:44
→ hwanger : (a1,a2,a3,a4, ,2)要換a3,a4 則a1,a3互換 a1,a4互 09/17 09:46
→ hwanger : 換 a1,a3再互換 09/17 09:47
→ hwanger : 但當|s|<2k時 a_{n-k},...,a_k是不能動的 但a1,..., 09/17 09:53
→ hwanger : a_{n-k-1},a_k,a_{k+1},...,an是可以排序的(先把比 09/17 09:55
→ hwanger : 較小的都丟到頭 比較大都丟到尾 再用泡泡) 09/17 09:57
→ hwanger : 所以只要檢查排序前後的子字串a_{n-k},...,a_k是否 09/17 09:58
→ hwanger : 一樣即可 09/17 09:59
→ hwanger : 上面|s|<2k的情況打錯了 比較a_{n-k+1},...,a_k才對 09/17 10:12
※ 編輯: expiate (98.207.101.195 美國), 09/17/2020 11:08:35
→ hwanger : 如果code就是原PO原本的算法 那上面就是證明的大綱 09/17 11:24
→ hwanger : (任意相鄰兩個都可以在其他不動的情況下互換保證了 09/17 11:25
→ hwanger : 泡泡) 09/17 11:25
→ expiate : 請問你|s|是指string長度嗎?s的起始狀態都不會影響 09/17 11:32
→ expiate : 最後的結果嗎?還是你認為|s|>=2k保證可以排序? 09/17 11:34
→ hwanger : |s|是string長度 不是我的符號 是你的網頁裡的符號 09/17 12:31
→ hwanger : |s|>=2k 不論s是何 都可以排序 重點在這個情況 我 09/17 12:36
→ hwanger : 們可以做到任意兩個相鄰位置的字符可以互換而不變 09/17 12:36
→ hwanger : 動其他字符的位置 如此再依Bubble sort即可 09/17 12:36
→ hwanger : 在你的code中 但當|s|>2k時 你for迴圈裡的if條件是 09/17 12:41
→ hwanger : 永不滿足的唷 09/17 12:41
推 hwanger : typo: |s|>=2k 09/17 12:48
→ expiate : 我想我可以理解,那數學上的證明就這樣解釋即可嗎? 09/17 13:07
→ hwanger : Lemma: Assume |s|>=2k. Then we can exchange the 09/17 13:08
→ hwanger : characters at i-th and (i+1)th positions without 09/17 13:09
→ hwanger : change the positions of other characters. 09/17 13:09
→ hwanger : Proof: Assume the string is "(a1)(a2)...(an)". 09/17 13:09
→ hwanger : Case 1: If i<k, then consider 09/17 13:10
→ hwanger : swap(ai,an)→swap(a{i+1},an)→swap(ai,an) 09/17 13:11
→ hwanger : Case 2: If i>k, then consider 09/17 13:11
→ hwanger : swap(ai,a1)→swap(a{i+1},a1)→swap(ai,a1) 09/17 13:11
→ hwanger : Case 3: If i=k, then consider 09/17 13:12
→ hwanger : swap(a{k+1},a1)→swap(a1,an)→swap(ak,an) 09/17 13:13
→ hwanger : →swap(a1,an)→swap(a{k+1},a1) 09/17 13:13
→ hwanger : 這樣有一點程式基礎的人都可以理解 對數學而言稍微 09/17 13:14
→ hwanger : 可以接受 如果要全部轉成數學語言的也是可以 09/17 13:15
→ hwanger : 讓(a1,a2,...,an)為一個1到26的有限序列 考慮所有的 09/17 13:17
→ hwanger : permutation σ使得(a_σ(1),...,a_σ(n))為遞增 09/17 13:19
→ hwanger : 收集所有這樣的σ的集合稱作S 並令G為symmetric 09/17 13:22
→ hwanger : group S_n的子群 G:=< (i,j) : |i-j|>=k > 則問題變 09/17 13:24
→ hwanger : 成問S和G的交集是否非空 而證明這個問題的想法基本 09/17 13:25
→ hwanger : 上就和一開始提到的想法一樣 此時swap的角色就是 09/17 13:26
→ hwanger : symmetric group裡的transposition 09/17 13:27
→ hwanger : 而上面的Lemma基本上就是說G包含(1,2),(2,3),..., 09/17 13:30
→ hwanger : (n-1,n) 所以G就是S_n 自然而然S交G非空 09/17 13:32
→ hwanger : 而對於n<2k 也是一樣轉換過來即可 09/17 13:34
→ hwanger : 實際上在些情形下 G是由(1,2),(2,3),..,(n-k-1,n-k) 09/17 13:36
→ hwanger : (k+1,k+2),...,(n-1,n)和(1,n)所生成的 也就是G是 09/17 13:37
→ hwanger : {1,2,...,n-k,k+1,k+2,...,n}的permuation group 09/17 13:39
→ hwanger : 此時S交G非空意味著存在一個σ在S中 使得σ(i)=i 對 09/17 13:42
→ hwanger : 於所有i = n-k+1,...,k 09/17 13:43
→ hwanger : 最後這些討論只是為了嚴謹而存在 沒有給出任何新知 09/17 13:55
→ hwanger : 識唷 冏 09/17 13:56
→ expiate : 非常感謝大大詳細的解說,您總是這麼熱心回答大家 09/18 01:30
→ expiate : 的問題。再次感恩 09/18 01:30
推 wohtp : 補充一下,s < 2k 就一定存在做不到的case。這樣加 09/18 03:42
→ wohtp : 起來才算完整解答原po的問題。 09/18 03:42
→ expiate : 也感謝上面大大,真的謝謝你們撥冗回答問題 09/18 04:15