[其他] 怎麼證明這樣的排序和輸入一定可行？

看板Math作者 (彎曲屎殼郎)時間5年前 (2020/09/17 06:06), 5年前編輯推噓2(2推 0噓 56→)
留言58則, 3人參與, 5年前最新討論串1/1
我在做一道題如下： https://nus.kattis.com/problems/longswaps 這道題我的作法是先排序然後在跟原來的輸入一個字元一個字元比較 如果不同，就檢查在限制k下能否跟其它字元做交換。 雖然通過測試的case，但我想是否有嚴謹的數學能證明呢？ 謝謝了 下面是我的code，希望有幫助 int main(){ string str; int k; cin >> str >> k; string sorted = str; sort(sorted.begin(),sorted.end()); for(int i=0;i<str.size();++i){ if(str[i]!=sorted[i] && i-k<0 && i+k>=str.size()){ cout << "No" << endl; return 0; } } cout << "Yes" << endl; return 0; } -- 與怪物戰鬥的人，應當小心自己不要成為怪物。 當你遠遠凝視深淵時，深淵也在凝視你。 弗里德里希·威廉·尼采 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.207.101.195 (美國) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1600294001.A.8D5.html
→
09/17 09:41, 5年前 , 1F
看不懂原PO的算法 冏 提供一個 若|s|>=2k 則任意相
09/17 09:41, 1F
→
09/17 09:44, 5年前 , 2F
鄰兩個都可以在其他不動的情況下互換 如考慮
09/17 09:44, 2F
→
09/17 09:46, 5年前 , 3F
(a1,a2,a3,a4, ,2)要換a3,a4 則a1,a3互換 a1,a4互
09/17 09:46, 3F
→
09/17 09:47, 5年前 , 4F
換 a1,a3再互換
09/17 09:47, 4F
→
09/17 09:53, 5年前 , 5F
但當|s|<2k時 a_{n-k},...,a_k是不能動的 但a1,...,
09/17 09:53, 5F
→
09/17 09:55, 5年前 , 6F
a_{n-k-1},a_k,a_{k+1},...,an是可以排序的(先把比
09/17 09:55, 6F
→
09/17 09:57, 5年前 , 7F
較小的都丟到頭 比較大都丟到尾 再用泡泡)
09/17 09:57, 7F
→
09/17 09:58, 5年前 , 8F
所以只要檢查排序前後的子字串a_{n-k},...,a_k是否
09/17 09:58, 8F
→
09/17 09:59, 5年前 , 9F
一樣即可
09/17 09:59, 9F
→
09/17 10:12, 5年前 , 10F
上面|s|<2k的情況打錯了 比較a_{n-k+1},...,a_k才對
09/17 10:12, 10F
※ 編輯: expiate (98.207.101.195 美國), 09/17/2020 11:08:35
→
09/17 11:24, 5年前 , 11F
如果code就是原PO原本的算法 那上面就是證明的大綱
09/17 11:24, 11F
→
09/17 11:25, 5年前 , 12F
(任意相鄰兩個都可以在其他不動的情況下互換保證了
09/17 11:25, 12F
→
09/17 11:25, 5年前 , 13F
泡泡)
09/17 11:25, 13F
→
09/17 11:32, 5年前 , 14F
請問你|s|是指string長度嗎？s的起始狀態都不會影響
09/17 11:32, 14F
→
09/17 11:34, 5年前 , 15F
最後的結果嗎？還是你認為|s|>=2k保證可以排序?
09/17 11:34, 15F
→
09/17 12:31, 5年前 , 16F
|s|是string長度 不是我的符號 是你的網頁裡的符號
09/17 12:31, 16F
→
09/17 12:36, 5年前 , 17F
|s|>=2k 不論s是何 都可以排序 重點在這個情況 我
09/17 12:36, 17F
→
09/17 12:36, 5年前 , 18F
們可以做到任意兩個相鄰位置的字符可以互換而不變
09/17 12:36, 18F
→
09/17 12:36, 5年前 , 19F
動其他字符的位置 如此再依Bubble sort即可
09/17 12:36, 19F
→
09/17 12:41, 5年前 , 20F
在你的code中 但當|s|>2k時 你for迴圈裡的if條件是
09/17 12:41, 20F
→
09/17 12:41, 5年前 , 21F
永不滿足的唷
09/17 12:41, 21F
推
09/17 12:48, 5年前 , 22F
typo: |s|>=2k
09/17 12:48, 22F
→
09/17 13:07, 5年前 , 23F
我想我可以理解，那數學上的證明就這樣解釋即可嗎？
09/17 13:07, 23F
→
09/17 13:08, 5年前 , 24F
Lemma: Assume |s|>=2k. Then we can exchange the
09/17 13:08, 24F
→
09/17 13:09, 5年前 , 25F
characters at i-th and (i+1)th positions without
09/17 13:09, 25F
→
09/17 13:09, 5年前 , 26F
change the positions of other characters.
09/17 13:09, 26F
→
09/17 13:09, 5年前 , 27F
Proof: Assume the string is "(a1)(a2)...(an)".
09/17 13:09, 27F
→
09/17 13:10, 5年前 , 28F
Case 1: If i<k, then consider
09/17 13:10, 28F
→
09/17 13:11, 5年前 , 29F
swap(ai,an)→swap(a{i+1},an)→swap(ai,an)
09/17 13:11, 29F
→
09/17 13:11, 5年前 , 30F
Case 2: If i>k, then consider
09/17 13:11, 30F
→
09/17 13:11, 5年前 , 31F
swap(ai,a1)→swap(a{i+1},a1)→swap(ai,a1)
09/17 13:11, 31F
→
09/17 13:12, 5年前 , 32F
Case 3: If i=k, then consider
09/17 13:12, 32F
→
09/17 13:13, 5年前 , 33F
swap(a{k+1},a1)→swap(a1,an)→swap(ak,an)
09/17 13:13, 33F
→
09/17 13:13, 5年前 , 34F
→swap(a1,an)→swap(a{k+1},a1)
09/17 13:13, 34F
→
09/17 13:14, 5年前 , 35F
這樣有一點程式基礎的人都可以理解 對數學而言稍微
09/17 13:14, 35F
→
09/17 13:15, 5年前 , 36F
可以接受 如果要全部轉成數學語言的也是可以
09/17 13:15, 36F
→
09/17 13:17, 5年前 , 37F
讓(a1,a2,...,an)為一個1到26的有限序列 考慮所有的
09/17 13:17, 37F
→
09/17 13:19, 5年前 , 38F
permutation σ使得(a_σ(1),...,a_σ(n))為遞增
09/17 13:19, 38F
→
09/17 13:22, 5年前 , 39F
收集所有這樣的σ的集合稱作S 並令G為symmetric
09/17 13:22, 39F
→
09/17 13:24, 5年前 , 40F
group S_n的子群 G:=< (i,j) : |i-j|>=k > 則問題變
09/17 13:24, 40F
→
09/17 13:25, 5年前 , 41F
成問S和G的交集是否非空 而證明這個問題的想法基本
09/17 13:25, 41F
→
09/17 13:26, 5年前 , 42F
上就和一開始提到的想法一樣 此時swap的角色就是
09/17 13:26, 42F
→
09/17 13:27, 5年前 , 43F
symmetric group裡的transposition
09/17 13:27, 43F
→
09/17 13:30, 5年前 , 44F
而上面的Lemma基本上就是說G包含(1,2),(2,3),...,
09/17 13:30, 44F
→
09/17 13:32, 5年前 , 45F
(n-1,n) 所以G就是S_n 自然而然S交G非空
09/17 13:32, 45F
→
09/17 13:34, 5年前 , 46F
而對於n<2k 也是一樣轉換過來即可
09/17 13:34, 46F
→
09/17 13:36, 5年前 , 47F
實際上在些情形下 G是由(1,2),(2,3),..,(n-k-1,n-k)
09/17 13:36, 47F
→
09/17 13:37, 5年前 , 48F
(k+1,k+2),...,(n-1,n)和(1,n)所生成的 也就是G是
09/17 13:37, 48F
→
09/17 13:39, 5年前 , 49F
{1,2,...,n-k,k+1,k+2,...,n}的permuation group
09/17 13:39, 49F
→
09/17 13:42, 5年前 , 50F
此時S交G非空意味著存在一個σ在S中 使得σ(i)=i 對
09/17 13:42, 50F
→
09/17 13:43, 5年前 , 51F
於所有i = n-k+1,...,k
09/17 13:43, 51F
→
09/17 13:55, 5年前 , 52F
最後這些討論只是為了嚴謹而存在 沒有給出任何新知
09/17 13:55, 52F
→
09/17 13:56, 5年前 , 53F
識唷 冏
09/17 13:56, 53F
→
09/18 01:30, 5年前 , 54F
非常感謝大大詳細的解說，您總是這麼熱心回答大家
09/18 01:30, 54F
→
09/18 01:30, 5年前 , 55F
的問題。再次感恩
09/18 01:30, 55F
推
09/18 03:42, 5年前 , 56F
補充一下，s < 2k 就一定存在做不到的case。這樣加
09/18 03:42, 56F
→
09/18 03:42, 5年前 , 57F
起來才算完整解答原po的問題。
09/18 03:42, 57F
→
09/18 04:15, 5年前 , 58F
也感謝上面大大，真的謝謝你們撥冗回答問題
09/18 04:15, 58F
‣ 更多 expiate 的文章
文章代碼(AID): #1VOennZL (Math)