排列组合总结
程序员文章站
2022-05-21 22:44:27
...
对于很多数据规模较小的枚举,一般都是可以用排列或者组合进行粗暴的解决。
全排列:
1.型排列
a.枚举集合中所有排列情况
import java.util.Scanner;
public class 全排列 {
public static int[] arr=new int[]{0,1,2};
public static void main(String[] args) {
bfs(0,arr.length);
}
public static void bfs(int begin,int end){
if(begin==end){//递归出口
//输出结果
for(int i=0;i<end;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
return;
}
for(int i=begin;i<end;i++){
swap(i,begin);
bfs(begin+1,end);
swap(i,begin);//回溯,执行完毕交换回去
}
}
public static void swap(int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
输出
0 1 2
0 2 1
1 0 2
1 2 0
2 1 0
2 0 1
b.指定数组的某一片段进行全排列,对上面的代码做一些较小的改动就可以实现,指定start排列起始位置,end结束位置
import java.util.Scanner;
public class 全排列 {
public static int[] arr=new int[]{0,1,2,3,4,5,6,7,8,9};
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int start=sc.nextInt();//起始索引
int end=sc.nextInt();//结束索引
t=start;
bfs(start,end);//不包括end
}
static int t=0;
public static void bfs(int begin,int end){
if(begin==end){//递归出口
//输出结果
for(int i=t;i<end;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
return;
}
for(int i=begin;i<end;i++){
swap(i,begin);
bfs(begin+1,end);
swap(i,begin);//回溯,执行完毕交换回去
}
}
public static void swap(int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
输入
1 4
输出
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
组合:
a.取集合的所有子集2^n型
public class 全组合 {
public static void main(String[] args) {
Combination(new char []{'a','b','c','d'});
}
public static void Combination(char [] s){
if(s.length == 0){
return;
}
int len = s.length;
int n = 1<<len;
//从1循环到2^len-1
for(int i=0;i<n;i++){
StringBuffer sb = new StringBuffer();
//查看第一层循环里面的任意一种取值当中的哪一位是1[比如ab,011], 如果是1,对应的字符就存在,打印当前组合。
for(int j=0;j<len;j++){
// 1<<j 表示第j位上为1,其他位为0
if(((i>>j)&1)==1) // 对应位上为1,则加上要输出的字符
{
sb.append(s[j]);
}
}
System.out.print(sb + " ");
}
}
}
a b ab c ac bc abc d ad bd abd cd acd bcd abcd
b.取含有指定元素个数的子集,C(n,k)型
public class 组合取数 {
public static void main(String[] args) {
nums=new int[]{1,2,3,4,5,6,7};
put_subset(nums.length,6);
System.out.println(cnt);//输出组合个数
}
static int[] nums;
static int cnt=0;//取到的个数
//元素个数n,要取的个数k,C(k,n)n个当中取k个
public static void put_subset(int n,int k){
for(int i=0;i<(1<<n);i++){
int num=0,kk=i;
while(kk!=0){
kk=(kk&(kk-1));//消除kk最后一个1,如110完全消除1,则要执行两次
num++;//统计1的个数
}
if(num==k){
for(int j=0;j<n;j++){
if(((i>>j)&1)==1){
System.out.print(nums[j]+" ");
}
}
System.out.println();
cnt++;
}
}
}
}
输出
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
7