Question

关于排列组合算法的问题

从1到93之间任取8个数字组成一个数列，要求不能是降序排列，也就是说数列中任何一个数字应该大于等于它前面的数字。请问共有多少种排列方式?
例如：
{1,2,3,4,5,6,7,8}
{1,2,2,2,5,6,7,8}
{1,2,3,4,5,6,7,93}
{10,11,30,40,44,50,60,90}
以上几种排列都是符合要求的
而以下是几种不符合要求的排列:
{1,2,3,2,4,5,6,7}
{10,10,10,9,10,10,10,11}
哈 谢一楼的算法
我补充下，是想用排列和组合的方式表达这个算法，比如从十个元素里面挑出三个有多少种挑法可以表示成
C(10,3),其他的类推。
我不清楚能不能只用排列和组合表示出这个算法，如果不能的话就只能手写循环了...另外刚刚忘记说，如果按照上面给出的条件得出的答案是1x8x6x0x8x7x8x9x4x3x0x0(因为连续数字会被系统认作电话号码，所以用x隔开).求通用算法~~~

Answer 1

献上历史上最烂的算法,不知道哪年能算出来!!

后面加了一个新算法

class TheBadOne
{
public static void main(String[] args)
{
int counter=0;
for(int i=1;i<=86;i++){
for(int j=i;j<=87;j++){
for(int k=j;k<=88;k++){
for(int l=k;l<=89;l++){
for(int m=l;m<=90;m++){
for(int n=m;n<=91;n++){
for(int o=n;o<=92;o++){
for(int p=o;p<=93;p++){
if(i==j||j==k||k==l||l==m||m==n||n==o||o==p)continue;
counter++;
System.out.println("此时数组为"+"{"+i+","+j+","+k+","+l+","+m+","+n+","+o+","+p+"}");
System.out.println("counter="+counter);
}
}
}
}
}
}
}
}
System.out.println(" final counter="+counter);
}
}

新算法
class TTT
{
public static void main(String[] args)
{
double counter=0;
for(int i=93;i>=8;i--){
counter+=i*(i-1)*(i-2)*(i-3)*(i-4)*(i-5)*(i-6)*(i-7);
System.out.println(i*(i-1)*(i-2)*(i-3)*(i-4)*(i-5)*(i-6)*(i-7));
System.out.println("inner counter="+counter);
}
System.out.println("counter="+counter);
}
}

算的结果是counter=1.1685135616E10

C:\>

Answer 2

可以这样计算：
P(93,8)/8!
8!是8的阶乘。

原理如下：
不妨设a<b<c<d<e<f<g<h是1~93中任意的八个数。
则此八个数的所有可能的排列个数是8！
但是这8！个排列中只有一个是符合你非降需排列的要求的。
即abcdefgh，其他排列均不符合要求。

也就是说，在每八个数字的全排列中只取一个。
所以，首先用P(93,8)求出93个数中任取八个的全排列的总数，而后再除以8！就可以了。

其实就是C(93,8)