※ 引述《windincloud (雲淡風輕)》之銘言：
: 今天遇到一個問題不知道是否能證明它
: 問題如下:
: Give a string. Randomize the order of alphabet in the string while keeping
: di-alphabet distrubution contant.
: supposed:
: If the start alphabet not equal to end alphabet, then you only can get the
: same start and the same end in new string.
: 簡單的說 今天給定一串字串，然後將其兩兩成一對去看，將這樣的組成比例記下來
: 之後產生一條序列，且規定這條新產生的序列兩兩成一對去看的組成比例要與原來相同
: 猜想
: 要是今天給定的序列第一個字與最後一個字是不同的，則新產生之字串的頭尾會與原來的
: 相同
: 這邊舉例來說
: 給定字串 gaccagca
: 此字串可得 di-alphabet組成為
: ga*1
: ac*1
: cc*1
: ca*2
: ag*1
: gc*1
: 之後我產生的字串 gcaccaga
: gc*1
: ca*2
: ac*1
: cc*1
: ag*1
: ga*1
: 這樣的比例與原字串gaccagca的比例是相同的
: 此後這邊的猜想只要是這字串新產生的一定是g開頭a結尾
: (前提是第一個字與最後一個字是不同的)
: 不知道有人是否能證明此猜想?
: 感謝~
筆者提供一個想法:
假設某個字串的開頭是x,結尾是y,則我們考慮產生的所有與x相關的
di-alphabet數量,不難發現無論如何, "x*" 型一定比 "*x" 型多一
組,這是因為開頭的x前面沒有任何符號,而字串中間若出現獨立的x,
則會同時產生 "x*" 與 "*x" 各一組.即使出現了連續的x,也只是中
間多了幾組 "xx" 而已. (*代表某個任意不同於x的符號)
因此,假若某個字串的兩組序列以不同的符號為開頭 , 則它們產生的
di-alphabet比例必然不同 , 此結論等價於 "組成比例相同則開頭亦
相同" .
結尾的部分同理可證.
僅供參考
高斯教授 2009/01/15
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.90.101