关于各种排列组合java算法实现方法
关于各种排列组合java算法实现方法
发布时间:2016-12-28 来源:查字典编辑
摘要:一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用复制代码代码如下:importjava.util...

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

复制代码 代码如下:

import java.util.Arrays;

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

//count1:170187

//count2:291656

public class test {

public static void main(String[] args) {

long start=System.currentTimeMillis();

count2();

long end=System.currentTimeMillis();

System.out.println(end-start);

}

private static void count2(){

int[] num=new int []{1,2,3,4,5,6,7,8,9};

for(int i=1;i<Math.pow(9, 9);i++){

String str=Integer.toString(i,9);

int sz=str.length();

for(int j=0;j<9-sz;j++){

str="0"+str;

}

char[] temp=str.toCharArray();

Arrays.sort(temp);

String gl=new String(temp);

if(!gl.equals("012345678")){

continue;

}

String result="";

for(int m=0;m<str.length();m++){

result+=num[Integer.parseInt(str.charAt(m)+"")];

}

System.out.println(result);

}

}

public static void count1(){

int[] num=new int []{1,2,3,4,5,6,7,8,9};

int[] ss=new int []{0,1,2,3,4,5,6,7,8};

int[] temp=new int[9];

while(temp[0]<9){

temp[temp.length-1]++;

for(int i=temp.length-1;i>0;i--){

if(temp[i]==9){

temp[i]=0;

temp[i-1]++;

}

}

int []tt=temp.clone();

Arrays.sort(tt);

if(!Arrays.equals(tt,ss)){

continue;

}

String result="";

for(int i=0;i<num.length;i++){

result+=num[temp[i]];

}

System.out.println(result);

}

}

}

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

复制代码 代码如下:

package practice;

import java.util.ArrayList;

import java.util.List;

public class Test1 {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

Object[] tmp={1,2,3,4,5,6};

// ArrayList<Object[]> rs=RandomC(tmp);

ArrayList<Object[]> rs=cmn(tmp,3);

for(int i=0;i<rs.size();i++)

{

// System.out.print(i+"=");

for(int j=0;j<rs.get(i).length;j++)

{

System.out.print(rs.get(i)[j]+",");

}

System.out.println();

}

}

// 求一个数组的任意组合

static ArrayList<Object[]> RandomC(Object[] source)

{

ArrayList<Object[]> result=new ArrayList<Object[]>();

if(source.length==1)

{

result.add(source);

}

else

{

Object[] psource=new Object[source.length-1];

for(int i=0;i<psource.length;i++)

{

psource[i]=source[i];

}

result=RandomC(psource);

int len=result.size();//fn组合的长度

result.add((new Object[]{source[source.length-1]}));

for(int i=0;i<len;i++)

{

Object[] tmp=new Object[result.get(i).length+1];

for(int j=0;j<tmp.length-1;j++)

{

tmp[j]=result.get(i)[j];

}

tmp[tmp.length-1]=source[source.length-1];

result.add(tmp);

}

}

return result;

}

static ArrayList<Object[]> cmn(Object[] source,int n)

{

ArrayList<Object[]> result=new ArrayList<Object[]>();

if(n==1)

{

for(int i=0;i<source.length;i++)

{

result.add(new Object[]{source[i]});

}

}

else if(source.length==n)

{

result.add(source);

}

else

{

Object[] psource=new Object[source.length-1];

for(int i=0;i<psource.length;i++)

{

psource[i]=source[i];

}

result=cmn(psource,n);

ArrayList<Object[]> tmp=cmn(psource,n-1);

for(int i=0;i<tmp.size();i++)

{

Object[] rs=new Object[n];

for(int j=0;j<n-1;j++)

{

rs[j]=tmp.get(i)[j];

}

rs[n-1]=source[source.length-1];

result.add(rs);

}

}

return result;

}

}

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

复制代码 代码如下:

package Acm;

//强大的求组合数

public class MainApp {

public static void main(String[] args) {

int[] num=new int[]{1,2,3,4,5};

String str="";

//求3个数的组合个数

// count(0,str,num,3);

// 求1-n个数的组合个数

count1(0,str,num);

}

private static void count1(int i, String str, int[] num) {

if(i==num.length){

System.out.println(str);

return;

}

count1(i+1,str,num);

count1(i+1,str+num[i]+",",num);

}

private static void count(int i, String str, int[] num,int n) {

if(n==0){

System.out.println(str);

return;

}

if(i==num.length){

return;

}

count(i+1,str+num[i]+",",num,n-1);

count(i+1,str,num,n);

}

}

下面是求排列

复制代码 代码如下:

package Acm;

//求排列,求各种排列或组合后排列

import java.util.Arrays;

import java.util.Scanner;

public class Demo19 {

private static boolean f[];

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int sz=sc.nextInt();

for(int i=0;i<sz;i++){

int sum=sc.nextInt();

f=new boolean[sum];

Arrays.fill(f, true);

int[] num=new int[sum];

for(int j=0;j<sum;j++){

num[j]=j+1;

}

int nn=sc.nextInt();

String str="";

count(num,str,nn);

}

}

/**

*

* @param num 表示要排列的数组

* @param str 以排列好的字符串

* @param nn 剩下需要排列的个数,如果需要全排列,则nn为数组长度

*/

private static void count(int[] num, String str, int nn) {

if(nn==0){

System.out.println(str);

return;

}

for(int i=0;i<num.length;i++){

if(!f[i]){

continue;

}

f[i]=false;

count(num,str+num[i],nn-1);

f[i]=true;

}

}

}

推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关阅读
网友关注
最新Java学习
热门Java学习
编程开发子分类