CSP-1 第9次 枚举法(取数排列问题)

csp李老师

2024-05-04 8:39:15
2024-05-14 8:39:15

信息与公告

排列:从n个不同元素中,任取m个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;
排列数:从n个不同元素中取出m个元素的所有排列的个数。
下面讨论当m是确定的数,如何枚举排列问题。

1、排列(可放回)
例如:从1~n中取出3个数的排列(可重复),若n=4,则
1 1 1,1 1 2,1 1 3,1 1 4,1 2 1,1 2 2,1 2 3,1 2 4,1 3 1,…

for(inti=1; i<=n; i++)	
	for(int j=1;j<=n; j++)	
		for(int k=1; k<=n; k++)  

2、排列(不放回)
例如:从1~n中取出3个数的排列(取出后不放回),若n=4,则
1 2 3,1 2 4,1 3 2,1 3 4,2 1 3,2 1 4,…

for(inti=1; i<=n; i++)	
	for(int j=1;j<=n;j++)	
		for(int k=1; k<=n; k++)
			if(i!=j &&i!=k && j!=k ) 

3、数组排列:从n个数的数组a中,任取3个数进行排列

sort(a+0, a+n);     // 如果要按字典升序列出所有排列,则可先对数组排序
for(inti=0; i<=n-1; i++)	// 枚举下标
	for(int j=0; j<=n-1; j++)	
		for(int k=0; k<=n-1; k++)  // 如果是任取4个数排列,则再加第4层for循环
			if(i!=j &&i!=k && j!=k )// 不放回,要加上这个if判断;放回则不加