排列组合问题证明有n个数在输入序列中,其中j个是不相同的.按顺序输出到输出序列,每次输出的时候都和输出序列中的每一个数字

既然是问最多比较多少次,那么就要按极端情况考虑.
假设输出序列中已有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，符合逻辑啊~~