关于各种排列组合java算法实现方法

一利用二进制状态法求排列组合此种方法比较容易懂但是运行效率不高小数据排列组合可以使用

复制代码 代码如下:
import javautilArrays;

//利用二进制算法进行全排列
//count:
//count:

public class test {
public static void main(String[] args) {
long start=SystemcurrentTimeMillis();
count();
long end=SystemcurrentTimeMillis();
Systemoutprintln(endstart);
}
private static void count(){
int[] num=new int []{};
for(int i=;i<Mathpow( );i++){
String str=IntegertoString(i);
int sz=strlength();
for(int j=;j<sz;j++){
str=""+str;
}
char[] temp=strtoCharArray();
Arrayssort(temp);
String gl=new String(temp);
if(!glequals("")){
continue;
}
String result="";
for(int m=;m<strlength();m++){
result+=num[IntegerparseInt(strcharAt(m)+"")];
}
Systemoutprintln(result);
}
}
public static void count(){
int[] num=new int []{};
int[] ss=new int []{};
int[] temp=new int[];
while(temp[]<){
temp[templength]++;
for(int i=templength;i>;i){
if(temp[i]==){
temp[i]=;
temp[i]++;
}
}
int []tt=tempclone();
Arrayssort(tt);
if(!Arraysequals(ttss)){
continue;
}
String result="";
for(int i=;i<numlength;i++){
result+=num[temp[i]];
}
Systemoutprintln(result);

}
}
}

二用递归的思想来求排列跟组合代码量比较大

复制代码 代码如下:
package practice;

import javautilArrayList;
import javautilList;

public class Test {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Autogenerated method stub
Object[] tmp={};
//        ArrayList<Object[]> rs=RandomC(tmp);
ArrayList<Object[]> rs=cmn(tmp);
for(int i=;i<rssize();i++)
{
//            Systemoutprint(i+"=");
for(int j=;j<rsget(i)length;j++)
{
Systemoutprint(rsget(i)[j]+"");
}
Systemoutprintln();

}
}

// 求一个数组的任意组合
static ArrayList<Object[]> RandomC(Object[] source)
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
if(sourcelength==)
{
resultadd(source);        
}
else
{
Object[] psource=new Object[sourcelength];
for(int i=;i<psourcelength;i++)
{
psource[i]=source[i];
}
result=RandomC(psource);
int len=resultsize();//fn组合的长度
resultadd((new Object[]{source[sourcelength]}));
for(int i=;i<len;i++)
{
Object[] tmp=new Object[resultget(i)length+];
for(int j=;j<tmplength;j++)
{
tmp[j]=resultget(i)[j];
}
tmp[tmplength]=source[sourcelength];
resultadd(tmp);
}

}
return result;
}

static ArrayList<Object[]> cmn(Object[] sourceint n)
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
if(n==)
{
for(int i=;i<sourcelength;i++)
{
resultadd(new Object[]{source[i]});

}
}
else if(sourcelength==n)
{
resultadd(source);
}
else
{
Object[] psource=new Object[sourcelength];
for(int i=;i<psourcelength;i++)
{
psource[i]=source[i];
}
result=cmn(psourcen);
ArrayList<Object[]> tmp=cmn(psourcen);
for(int i=;i<tmpsize();i++)
{
Object[] rs=new Object[n];
for(int j=;j<n;j++)
{
rs[j]=tmpget(i)[j];
}
rs[n]=source[sourcelength];
resultadd(rs);
}
}
return result;
}

}

三利用动态规划的思想求排列和组合

复制代码 代码如下:
package Acm;
//强大的求组合数
public class MainApp {
public static void main(String[] args) {
int[] num=new int[]{};
String str="";
//求个数的组合个数
//        count(strnum);
//        求n个数的组合个数
count(strnum);
}

private static void count(int i String str int[] num) {
if(i==numlength){
Systemoutprintln(str);
return;
}
count(i+strnum);
count(i+str+num[i]+""num);
}

private static void count(int i String str int[] numint n) {
if(n==){
Systemoutprintln(str);
return;
}
if(i==numlength){
return;
}
count(i+str+num[i]+""numn);
count(i+strnumn);
}
}

下面是求排列

复制代码 代码如下:

package Acm;
//求排列求各种排列或组合后排列
import javautilArrays;
import javautilScanner; public class Demo {
private static boolean f[];
public static void main(String[] args) {
Scanner sc=new Scanner(Systemin);
int sz=scnextInt();
for(int i=;i<sz;i++){
int sum=scnextInt();
f=new boolean[sum];
Arraysfill(f true);
int[] num=new int[sum];
for(int j=;j<sum;j++){
num[j]=j+;
}
int nn=scnextInt();
String str="";
count(numstrnn);
}
}
/**
*
* @param num 表示要排列的数组
* @param str 以排列好的字符串
* @param nn  剩下需要排列的个数如果需要全排列则nn为数组长度
*/
private static void count(int[] num String str int nn) {
if(nn==){
Systemoutprintln(str);
return;
}
for(int i=;i<numlength;i++){
if(!f[i]){
continue;
}
f[i]=false;
count(numstr+num[i]nn);
f[i]=true;
}
}
}