一 利用二进制状态法求排列组合 此种方法比较容易懂 但是运行效率不高 小数据排列组合可以使用
复制代码 代码如下: 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 practiceimport 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/20148java写高精度运算~~跟C写的差不多。
先开两个数组，每一位数组元素存一位大整数数位
比如456687855就是
0 1 2 3 4 5 6 7 8 9
5 5 8 7 8 6 6 5 4
做+法就是两个数组按位相加然后进位
做减法就是按位相减然后借位
乘法就是取第二数组的数字按位与一数组乘
再把乘到东西累加起来
除法就是你怎么算就怎么写程序就行。
C(1000,500) 这样的东西不能直接去算。
否则算到100000，50000就铁定超时了（1个小时未必算的出来）
你把100000所有质数存在数组里。
算的时候相乘就是把所有因数累加进各质数的变量。除的时候就减
比如质数数列
0 1 2 3 456789//数组位
2 3 5 7 11 13 17 19 23 29 //质数
10 8 3 2 000000//在这个大数字中有多少个质数相乘
现在这个大数字要*210
就变成
11 9 4 3 0 0 0 0 0 0
再除2就是
10 9 4 3 0 0 0 0 0 0
最后再算2^n2+3^n3+………………就行
其实还有更快的方法这个是数论讨论的范围。
想想还是能改进效率的。
但是思路到这就已经清晰了。
[算法基础]Java实现简单的组合计算——从M个数中取出N个
这个应该可以满足的你的要求
根据你的需求编写的，直接导入到eclipse运行即可
