1.求集合的所有子集（又称全组合）
求一个集合的所有组合，例如集合{A,B,C}的所有子集为：{},{A,B,C},{A,B},{A,C},{B,C},{A},{B},{C}。
思路
对于任意集合A，元素个数为n（空集n=0），则所有子集的个数为2^n个
如集合A={a,b,c},其子集个数为8；对于任意一个元素，在每个子集中，
要么存在，要么不存在，对应关系是：
a=1或a=0，b=1或b=0，c=1或c=0
映射为子集：
(1,1,1)->(a,b,c)
(1,1,0)->(a,b )
(1,0,1)->(a, c)
(1,0,0)->(a )
(0,1,1)->( b,c)
(0,1,0)->( b )
(0,0,1)->( c)
(0,0,0)->( ) 空集
观察以上规律，与计算机中数据存储方式相似，故可以通过(a=100,b=010,c=001)与集合映射000 - 111（0表示有，1表示无）作与运算，即获取集合的相应子集。
算法1：
位图法：
1）构造一个和集合一样大小的数组A，分别与集合中的某个元素对应，数组A中的元素只有两种状态：“1”和“0”，分别代表每次子集输出中集合中对应元素是否要输出，这样数组A可以看作是原集合的一个标记位图。
2）数组A模拟整数“加一”的操作，每“加一”之后，就将原集合中所有与数组A中值为“1”的相对应的元素输出。
代码如下
/**
* 获取所有子集
*/
private static ArrayList<ArrayList<Integer>> getSubList(int[] arr) {
ArrayList<ArrayList<Integer>> allList = new ArrayList<>();
int size = 1 << arr.length;// 2^n次方
for (int mark = 0; mark < size; mark++) {
ArrayList<Integer> aList = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
/* 重要：这句是最重要的代码:是 0-7 分别与运算 1，2，4
* 000 001 010 011 100 101 110 111
*
*/
if ((mark & (1 << i)) != 0) {
aList.add(arr[i]);
}
}
allList.add(aList);
}
return allList;
}
public static void main(String[] args) {
int[] arr= {1,2,3};
ArrayList<ArrayList<Integer>> list = getSubList(arr);
for (int i=0;i<list.size();i++) {
ArrayList<Integer> mList=list.get(i);
for (int j=0;j<mList.size();j++) {
System.out.print(mList.get(j)+" ");
}
//换行
System.out.println();
}
}
-
java求集合的所有子集、所有子序列、全排列全组合问题
算法2：递归迭代法：
public class Demo {
public static void main(String[] args) {
int[] arr = {1, 2};
Set<Set<Integer>> f = f(arr.length, arr);
System.out.println(f);
}
public static Set<Set<Integer>> f(int k, int[] arr) {
if (k == 0) {
Set<Set<Integer>> set = new HashSet<>();
set.add(new HashSet<>());//添加一个空集合
return set;
}
Set<Set<Integer>> set = f(k - 1, arr);
Set<Set<Integer>> resultSet = new HashSet<>();
for (Set<Integer> integerSet : set) {//扫描上一层的集合
//上一层的每个集合都包含两种情况，一种是加入新来的元素，另一种是不加入新的元素
HashSet<Integer> subSet = new HashSet<>();
subSet.addAll(integerSet);
subSet.add(arr[k - 1]);
resultSet.add(subSet);
resultSet.add(integerSet);
}
return resultSet;
}
}
2.求集合的所有排列（又称全排列）
一，问题描述
给定一个字符串，求出该字符串的全排列。
比如："abc"的全排列是：abc、acb、bac、bca、cab、cba
二，实现思路
* 从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理，
* 从而得到所有元素的全排列。以对字符串abc进行全排列为例，我们可以这么做：以abc为例：
* 固定a，求后面bc的排列：abc，acb，求好后，a和b交换，得到bac
* 固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba
* 固定c，求后面ba的排列：cba，cab。
*
* 即递归树：
str: a b c
ab ac ba bc ca cb
result: abc acb bac bca cab cba
/*
* 全排列
*/
public static void permutation(String str, String result) {
/* 全排列 递归实现
递归树：
str: a b c
ab ac ba bc ca cb
result: abc acb bac bca cab cba
*/
// 当result长度等于长度，说明已经遍历到叶子节点，直接打印
if (result.length() == str.length()) { // 表示遍历完了一个全排列结果
System.out.println(result);
} else {
for (int i = 0; i < str.length(); i++) {
// 判断result中没有 a、b、c
if (result.indexOf(str.charAt(i)) < 0) {
permutation(str, result + str.charAt(i));
}
}
}
}
public static void main(String args[]) throws Exception {
String str="abc";
permutation(str,"");
}
3.求集合的所有子序列（即所有的排列组合）
思路：
子序列和子集合不一样，子序列有顺序差别，子集合没有顺序，子序列为所有子集合的排列组合，即集合的所有子序列 = 集合的所有子集合的排列组合集。
/*
* 获取所有子集(全组合)
*/
private static List<String> combination(String str) {
ArrayList<String> allList = new ArrayList<>();
int size = 1 << str.length();// 2^n次方
for (int mark = 0; mark < size; mark++) {
ArrayList<String> aList = new ArrayList<>();
for (int i = 0; i < str.length(); i++) {
/* 重要：这句是最重要的代码:是 0-7 分别与运算 1，2，4
* 000 001 010 011 100 101 110 111
*
*/
if ((mark & (1 << i)) != 0) {
aList.add(str.charAt(i)+"");
}
}
allList.add(String.join("", aList));
}
//allList.forEach((item)->{System.out.println(item);});
return allList;
}
/*
* 全排列
*/
public static void permutation(String str, String result, List<String> allResult) {
/* 全排列 递归实现
递归树：
str: a b c
ab ac ba bc ca cb
result: abc acb bac bca cab cba
*/
// 结果 开始传入"" 空字符进入 len 是这个数的长度
if (result.length() == str.length()) {
// 表示遍历完了一个全排列结果
allResult.add(result);
} else {
for (int i = 0; i < str.length(); i++) {
// 返回指定字符在此字符串中第一次出现处的索引。
if (result.indexOf(str.charAt(i)) < 0) {
permutation(str, result + str.charAt(i), allResult);
}
}
}
}
public static void main(String[] args) {
String str="abc";
List<String> allList = combination(str);
List<String> allSequence = new ArrayList<>();
allList.forEach((item)->{
List<String> sequence = new ArrayList<>();
permutation(item,"",sequence);
allSequence.addAll(sequence);
});
allSequence.forEach((item)->{System.out.println(item);});
}
打印结果
