【问题】
编号为1,2,3,4,5的五个人分别去坐编号为1,2,3,4,5的五个座位,其中有且仅有两个人的编号与座位号一致的坐法有几种?
A.10种
B.20种
C.30种
D.60种
【出处】
《高中数学 排列组合题型解题研究(新高考)》P8例25 中原教研工作室编著
【数学解答】
五个人乱坐有A(5,5)=120种,ABCD皆在其内,均未排除
假定1,2两个人与座位号一致,剩下的3,4,5三个要选编号为3,4,5的座位,要求编号不能与座位号一致
3号座位只能在4,5中选一,假定为4;4号座位只能选5,选3的话5号座位就与编号5的重了;然后5号座位没得选,只能拿剩下的3.由此看两个座位号和人编号对上后,剩下的三人三座只能有2种排法;
五个座位中选两个座位有C(5,2)种情况,因此总排法就是C(5,2)*2=5*4/2/1*2=20种。选B。
【程序解答】
程序解答就相对容易了,把A(5,5)的全排列列出,然后筛选出编号和序号对应的方案即可。
全排列类代码:
package test241012;
import java.util.ArrayList;
import java.util.List;
/**
* 用于产生排列结果的工具类
* 从n个元素中取出m个元素,按照一定的顺序排成一列。得到所有排列的方案
*/
class Arranger {
// 保存在内部的对原始元素数组的引用
private int[] arr;
// 总计多少元素,此即数组长度
private final int n;
// 选多少个
private final int m;
// 返回结果
private List<List<Integer>> results;
/**
* 构造函数一
* 这个构造函数是用于全排列的(n=m=数组长度)
*
* @arr 原始元素数组
*/
public Arranger(int[] arr) {
this.arr = arr;
this.n = arr.length;
this.m = arr.length;
this.results = new ArrayList<>();
doArrange(new ArrayList<>());
}
/**
* 构造函数二
* 这个构造函数是用于部分排列的(m<n=数组长度)
*
* @param arr 原始元素数组
* @param selCnt 选多少个
*/
public Arranger(int[] arr, int selCnt) {
this.arr = arr;
this.n = arr.length;
this.m = selCnt;
if (m > n) {
throw new ArrayIndexOutOfBoundsException("m:" + m + " >n:" + n);
}
this.results = new ArrayList<>();
doArrange(new ArrayList<>());
}
/**
* 使用递归进行全排列,结果放在results中
*
* @param initialList 初始链表
*/
private void doArrange(List<Integer> initialList) {
List<Integer> innerList = new ArrayList<>(initialList);
if (m == initialList.size()) {
results.add(innerList);
}
for (int i = 0; i < arr.length; i++) {
if (innerList.contains(arr[i])) {
continue;
}
innerList.add(arr[i]);
doArrange(innerList);
innerList.remove(innerList.size() - 1);
}
}
/**
* 获得结果链表的引用
*
* @return
*/
public List<List<Integer>> getResults() {
return results;
}
// 测试
public static void main(String[] args) {
int[] numbers = {1, 2, 3, 4};
Arranger arranger = new Arranger(numbers);
System.out.println("四元素全排列示例:");
int idx = 0;
for (List<Integer> re : arranger.getResults()) {
System.out.println(String.format("%02d", ++idx) + "." + re);
}
/*Arranger arranger2 = new Arranger(numbers, 2);
System.out.println("\n四选二排列示例:");
idx = 0;
for (List<Integer> re : arranger2.getResults()) {
System.out.println(String.format("%02d", ++idx) + "." + re);
}*/
}
}
主类代码:
package test241012;
import java.util.ArrayList;
import java.util.List;
/**
* 编号为1,2,3,4,5的五个人分别去坐编号为1,2,3,4,5的五个座位
* 其中有且仅有两个人的编号与座位号一致的坐法有几种?
*
* 2024年10月12日
*/
public class Test241012 {
public static void main(String[] args) {
int[] nums= {1,2,3,4,5};
Arranger arger = new Arranger(nums,nums.length);
int idx = 0;
for (List<Integer> line : arger.getResults()) {
List<Integer> corrects=new ArrayList<>();
int count=0;
for(int i=0;i<5;i++) {
if(i+1==line.get(i)) {
count++;
corrects.add(i+1);
}
}
if(count==2) {
System.out.println(String.format("%02d", ++idx) + "." + line+" @"+corrects);
}
}
}
}
【程序输出结果】
01.[1, 2, 4, 5, 3] @[1, 2]
02.[1, 2, 5, 3, 4] @[1, 2]
03.[1, 3, 4, 2, 5] @[1, 5]
04.[1, 3, 5, 4, 2] @[1, 4]
05.[1, 4, 2, 3, 5] @[1, 5]
06.[1, 4, 3, 5, 2] @[1, 3]
07.[1, 5, 2, 4, 3] @[1, 4]
08.[1, 5, 3, 2, 4] @[1, 3]
09.[2, 3, 1, 4, 5] @[4, 5]
10.[2, 4, 3, 1, 5] @[3, 5]
11.[2, 5, 3, 4, 1] @[3, 4]
12.[3, 1, 2, 4, 5] @[4, 5]
13.[3, 2, 4, 1, 5] @[2, 5]
14.[3, 2, 5, 4, 1] @[2, 4]
15.[4, 1, 3, 2, 5] @[3, 5]
16.[4, 2, 1, 3, 5] @[2, 5]
17.[4, 2, 3, 5, 1] @[2, 3]
18.[5, 1, 3, 4, 2] @[3, 4]
19.[5, 2, 1, 4, 3] @[2, 4]
20.[5, 2, 3, 1, 4] @[2, 3]
【结论】
数学解答和程序解法途径不同,结论一致,可以相互印证。