Question

排列组合问题证明

有n个数在输入序列中，其中j个是不相同的。按顺序输出到输出序列，每次输出的时候都和输出序列中的每一个数字比较，如果遇到相同的数字，则把该数字从输出序列中删除，加入到输入序列的末端；如果比较之后，没有相同的数字，则把该数字加入输出序列的末端。请问，最多比较多少次？答案是：(N-1)*(N-1)- (J-1)(J-2)/2。请证明。
补充说明:
一开始,
输入序列：1，2,3,3,2,2
输出序列：
比较次数：0
然后输入序列第一个数字，进输出序列。因为输出序列没有元素，所以不需要比较。
输入序列：2,3,3,2,2
输出序列：1
比较次数：0
然后第二个,第三个元素输出
输入序列：3,3,2,2
输出序列：1,2
比较次数：1
输入序列：3,2,2
输出序列：1,2,3
比较次数：3
然后第四个元素3输入，一个个和输出序列的元素进行比较之后，发现有3，则把原来的3从输出序列中删除，加入到输出序列的最后
输入序列：2,2，3
输出序列：1,2
比较次数：6
同样，第五个元素
输入序列：2,3,2
输出序列：1
比较次数：8
第六个元素
输入序列：3,2
输出序列：1,2
比较次数：9
第七个元素
输入序列：2
输出序列：1,2,3
比较次数：11
第八个元素
输入序列：2
输出序列：1,3
比较次数：13
第九个元素
输入序列：
输出序列：1,3,2
比较次数：15

Answer 1

既然是问最多比较多少次，那么就要按极端情况考虑。
假设输出序列中已有j个元素，输入序列中有n-j个元素，
极端情况就是这n-j个元素与输出序列中的第j个元素相同。
因此，第一次比j次，第二次比j-1次，输入序列元素减1，输出序列保持j个
故 需比较 (n-j)(j+j-1)=(n-j)(2j-1) 次后，输入序列为0

而j个不同元素放到输出序列，需比较 0+1+2+...+(j-1)=j(j-1)/2 次
因此 共比较 j(j-1)/2+(n-j)(2j-1) 次（与答案不同）

答案是 (N-1)*(N-1)- (J-1)(J-2)/2。如果其中N，J 与题目的n,j 含义相同，感觉这个答案有问题。
举例来说，3个1在输入序列中，显然结果只有一个，共比较2次。
而根据(N-1)*(N-1)- (J-1)(J-2)/2，应该是 N=3，J=1，结果是4次，不对吧。

追问

答案肯定没错。。。定理来着。。

追答

那就是条件不符合，否则怎么解释3个1在输入序列中的结果呢？

追问

什么叫条件不符合。三个1的话，n=3,j=1, (N-1)*(N-1)- (J-1)(J-2)/=4,最多交换4次。结果是只交换了2次，却是小于4次。。

追答

啊，如果是这样的话，(n-1)*(n-1)就好了，绝对是最多。

追问

答案不是还减了神马吗。。。不懂啊不懂。。。。那个答案在j=n的时候是n(n-1)/2，符合逻辑啊~~

Answer 2

注意这样每一种组合一一对应一种放法，所以取值方法是为C(N+n，N）

追问

为什么啊，然后呢？