欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排列组合总结

程序员文章站 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

相关标签: 算法