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);});
}
列印結果
