比一次
比较
/ \
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!个组合，因为每种组合似乎都可以用最多两次交换就可以得到。
: 这题之前有人讨论过，看完还是不解，不知道大家的想法如何。感谢！