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

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

复制代码 代码如下: import java util Arrays

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

public class test { public static void main(String[] args) { long start=System currentTimeMillis()count ()long end=System currentTimeMillis()System out println(end start)} private static void count (){ int[] num=new int []{ }for(int i= i<Math pow( )i++){ String str=Integer toString(i )int sz=str length()for(int j= j<szj++){ str=" "+str} char[] temp=str toCharArray()Arrays sort(temp)String gl=new String(temp)if(!gl equals(" ")){ continue} String result=""for(int m= m<str length()m++){ result+=num[Integer parseInt(str charAt(m)+"")]} System out println(result)} } public static void count (){ int[] num=new int []{ }int[] ss=new int []{ }int[] temp=new int[ ]while(temp[ ]<){ temp[temp length ]++for(int i=temp length i>i ){ if(temp[i]== ){ temp[i]= temp[i ]++} } int []tt=temp clone()Arrays sort(tt)if(!Arrays equals(tt ss)){ continue} String result=""for(int i= i<num lengthi++){ result+=num[temp[i]]} System out println(result)} } }

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

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

import java util ArrayListimport java util List

public class Test {

/** * @param args */ public static void main(String[] args) { // TODO Auto generated method stub Object[] tmp={ }// ArrayList<Object[]>rs=RandomC(tmp)ArrayList<Object[]>rs=cmn(tmp )for(int i= i<rs size()i++) { // System out print(i+"=")for(int j= j<rs get(i) lengthj++) { 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== ) { result add(source)} else { Object[] psource=new Object[source length ]for(int i= i<psource lengthi++) { psource[i]=source[i]} result=RandomC(psource)int len=result size()//fn组合的长度 result add((new Object[]{source[source length ]}))for(int i= i<leni++) { Object[] tmp=new Object[result get(i) length+ ]for(int j= j<tmp length j++) { tmp[j]=result get(i)[j]} tmp[tmp length ]=source[source length ]result add(tmp)} } return result} static ArrayList<Object[]>cmn(Object[] source int n) { ArrayList<Object[]>result=new ArrayList<Object[]>()if(n== ) { for(int i= i<source lengthi++) { result add(new Object[]{source[i]})} } else if(source length==n) { result add(source)} else { Object[] psource=new Object[source length ]for(int i= i<psource lengthi++) { psource[i]=source[i]} result=cmn(psource n)ArrayList<Object[]>tmp=cmn(psource n )for(int i= i<tmp size()i++) { Object[] rs=new Object[n]for(int j= j<n j++) { rs[j]=tmp get(i)[j]} rs[n ]=source[source length ]result add(rs)} } return result}

}

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

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

private static void count (int i String str int[] num) { if(i==num length){ System out println(str)return} count (i+ str num)count (i+ str+num[i]+" " num)}

private static void count(int i String str int[] num int n) { if(n== ){ System out println(str)return} if(i==num length){ return} count(i+ str+num[i]+" " num n )count(i+ str num n)} }

下面是求排列

复制代码 代码如下: lishixinzhi/Article/program/Java/JSP/201311/20148

全排列算法很多，这是其中一个，使用递归——

import java.util.ArrayList

import java.util.List

public class PermAComb {

    static List<int[]>allSorts = new ArrayList<int[]>()

       

    public static void permutation(int[] nums, int start, int end) {

        if (start == end) { // 当只要求对数组中一个数字进行全排列时，只要就按该数组输出即可

            int[] newNums = new int[nums.length]// 为新的排列创建一个数组容器

            for (int i=0i<=endi++) {

                newNums[i] = nums[i]

            }

            allSorts.add(newNums)// 将新的排列组合存放起来

        } else {

            for (int i=starti<=endi++) {

                int temp = nums[start]// 交换数组第一个元素与后续的元素

                nums[start] = nums[i]

                nums[i] = temp

                permutation(nums, start + 1, end)// 后续元伏大素递归全排列

                nums[i] = nums[start]// 将交换后的数组还原

                nums[start] = temp

   老蔽         }

        }

    }

       

    public static void main(String[] args) {

        int[] numArray = {1, 2, 3, 4, 5, 6}

        permutation(numArray, 0, numArray.length - 1)

        int[][] a = new int[allSorts.size()][]// 你要的二侍厅州维数组a

        allSorts.toArray(a)

           

        // 打印验证

        for (int i=0i<a.lengthi++) {

            int[] nums = a[i]

            for (int j=0j<nums.lengthj++) {

                System.out.print(nums[j])

            }

            System.out.println()

        }

        System.out.println(a.length)

    }

}

---