[理工] DS 101台大

[jeremy4849 (yang)]

1. Assume that the elements are pairwise distinct. Answer the following questions on sorting algorithms.
(2)A single comparison between two elements can distinguish up to 2 permutations. How many permutations can be distinguished using k comparisons?

我的答案：(k+1)!
不知道這題的意思是什麼，我的假設是在k+1個數之下做 k comparisons，如果有3個數做2 comparisons 應該可以有 3!個組合，因為每種組合似乎都可以用最多兩次交換就可以得到。
這題之前有人討論過，看完還是不解，不知道大家的想法如何。感謝！



--
Sent from my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 42.71.126.67
推 A4P8T6X9:我覺得是2^k種，我是用decision tree的leaf想的，他說都
→ A4P8T6X9:不一樣是說明決策樹是2元而不是三元。
推 leosnake:想法跟原PO一樣，k個comparisons 可以排序k+1個數
→ leosnake:k+1個數總共有 (k+1)!個permutations
推 leosnake:NO 我說錯了 別理我XD
→ jeremy4849:X覺得蠻有可能是2^k的
→ entryword:我也覺得是2^k