比一次
比較
/ \
Y / \ N
/ \
結果1 結果2
比兩次
比較 比較
/ \ / \
Y / \ N Y / \ N
/ \ / \
比較 結果3 or 結果1 比較
/ \ / \
Y / \ N Y / \ N
/ \ / \
結果1 結果2 結果2 結果3
比三次
比較
/ \
/ \
Y / \ N
/ \
/ \
比較 比較
/ \ / \
Y / \ N Y / \ N
/ \ / \
結果1 結果2 結果3 結果4
單純暴力法 ... XD
接下來用數學歸納法應該可以推得 k+1
※ 引述《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!個組合，因為每種組合似乎都可以用最多兩次交換就可以得到。
: 這題之前有人討論過，看完還是不解，不知道大家的想法如何。感謝！