转载声明：原文转自:http://www.cnblogs.com/xiezie/p/5574516.html
受到ACM1015的影响，个人感觉，有必要对统计学上的 全组合和全排列 进行一个简单的总结
组合数：从m个不同元素中取出n（n≤m）个元素的所有组合的个数，叫做从m个不同元素中取出n个元素的组合数（Combination）。
如1,2,3三个元素的全组合为：
1
2
3
12
13
23
123
以下是java实现的获取全组合及其个数的算法：
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Scanner; public class GetCombination { public static void main(String[] args) {
Scanner scan = new Scanner(new BufferedInputStream(System.in));
String s = scan.next();
ArrayList<String> list = new ArrayList<>();
ArrayList<Character> com = new ArrayList<>();
int len = s.length() + 1;
for(int i = 1 ; i != len ; i ++){
getCombinations(list,s.toCharArray(),0,i,com);
}
for(int i = 0 ; i != list.size() ; i ++){
System.out.println(list.get(i));
}
System.out.println(getCountOfCombinations(s.length(),s.length()));
scan.close();
} static void getCombinations(ArrayList<String> list ,char[] cs, int start,int len,ArrayList<Character> com){//len为组合的长度
if(len == 0){
String s = "";
for(int i = 0 ; i != com.size() ; i ++){
s = s.concat(com.get(i).toString());
}
list.add(s);
return;
}
if(start==cs.length){
return;
}
com.add(cs[start]);
getCombinations(list,cs,start+1,len-1,com);
com.remove(com.size()-1);
getCombinations(list,cs,start+1,len,com);
} static int getCountOfCombinations(int arrLen,int len){//获取长度为len的组合数
int m = 1;
for(int i = 0 ; i != len ; i ++ ){
m*=arrLen-i;
}
int n = 1;
for(int i = len ; i != 1 ; i --){
n*=i;
}
return m/n;
} }
全排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
如1,2,3三个元素的全排列为：
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
共3*2*1=6种 3！
以下是java实现的获取全排列及其个数的算法：
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Scanner; public class GetAllPermutations { public static void main(String[] args) {
Scanner scan = new Scanner(new BufferedInputStream(System.in));
String s = scan.next();
ArrayList<String> list = new ArrayList<>();
getAllPermutations(list,s.toCharArray(),0,s.length());
System.out.println("----------非字典序----------");
for(int i = 0 ; i != list.size() ; i ++){
System.out.println(list.get(i));
}
list.clear();
System.out.println("----------字典序----------");
getAllPermutations2(list,s.toCharArray(),0,s.length());
for(int i = 0 ; i != list.size() ; i ++){
System.out.println(list.get(i));
}
System.out.println(getCountOfAllPermutations(s.toCharArray(),0,s.length()));
scan.close();
} static int getCountOfAllPermutations(char[] cs,int start,int len){//start为数组序号
int count = 1;
int n = start + len ;
for(int i = start ; i != n ; i ++ ){
count *= i+1;
}
return count;
} //非字典序
static void getAllPermutations(ArrayList<String> answers,char[] cs,int start,int len){
if(start == len ){
answers.add(String.valueOf(cs));
return;
}
for(int i = start ; i != len ; i ++){
swap(cs,i,start);
getAllPermutations(answers,cs,start+1,len);
swap(cs,i,start);
}
} //字典序
static void getAllPermutations2(ArrayList<String> list, char[] cs, int i, int length) {
sort(cs);
permutations(list,cs,i,length);
} static void sort(char[] a) {//对字符数组进行快排
int len = a.length;
int low = 0,high = len - 1;
quickSort(a, low, high);
} static void quickSort(char[] a, int l ,int h){
if(l>=h){
return;
}
int low = l;
int high = h;
char k = a[low];
while(low< high){
//
while(high>low&&a[high]>=k){//寻找元素右边比其小的
high --;
}
a[low] = a[high];//进行交换，K指向high
while(low<high&&a[low]<=k){//寻找元素左边比其大的
low++;
}
a[high] = a[low];//进行交换，K指向low
}
a[low] = k;//将K赋给low
quickSort(a, l, low-1);
quickSort(a, low+1, h);
} static void permutations(ArrayList<String> answers,char[] cs,int start,int len){//cs为字典序数组
if(cs==null)
return;
while(true)
{
answers.add(String.valueOf(cs));
int j=start+len-2,k=start+len-1;
while(j>=start && cs[j]>cs[j+1])
--j;
if(j<start)
break; while(cs[k]<cs[j])
--k; swap(cs,k,j); int a,b;
for(a=j+1,b=start+len-1;a<b;++a,--b)
{
swap(cs,a,b);
}
}
} static void swap(char[] cs , int i , int j){
char t;
t = cs[i];
cs[i] = cs[j];
cs[j] = t;
}
}