关于各种排列组合java算法实现方法
一.利用二进制状态法求排列组合，此种方法比较容易懂，但是运行效率不高，小数据排列组合可以使用
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;
}
}
}