关于各种排列组合java算法实现方法_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;
        }
    }
}

时间: 2024-12-02 18:25:19

关于各种排列组合java算法实现方法_java的相关文章

关于各种排列组合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=S

浅析实现排列组合查询算法

所谓的排列组合查询就相当于GOOGLE高级查询中"包含以下全部的字词"查询,也就是说查询中必须包含所有查询关键词,而且他们的顺序可以是任意.以下程序段实现了这一功能.比如输入查询关键字:tom tina则最一般的情况是在程序中使用类似于"select sex from student where name like '%tom%tina%' or name like '%tina%tom%' ordered by age" 的查询语句实现以上的查询,因此如何得到'%

数组-想找到一个排列组合的算法

问题描述 想找到一个排列组合的算法 比如数组里有1-500的非连续数值, 当传入345这样一个数值进来时, 可以从数组里拿出N个数值相加得到345这个值的方案, 且要求相加数值个数最少,或最接近的组合优先获取出来 解决方案 2009年1月15日 沈阳 晴?? 为解决1月7日遇到的排列组合的难题,进行了以下题目的研究,并用C#实现了一个非递归的算法.有一个List,List中存有N个对象,要求做出这N个对象所有无序组.?数学公式:组合数=C(n1) + C(n2) + ...... + C(nn)

list里的数据排列组合求算法

问题描述 list里的数据排列组合求算法 求算法,(不要for嵌套和递归) 问题:现有几个list集合每个集合的大小不确定有可能size为0(集合个数与size大小都不确定,要考虑size为0没有数据的情况),现想得到把每个集合里的数据进行排列组合. 即 list1 [A,B,C] list2 [D,E,F] list3 [G,H,I] 现在得到 ADG ADH ADI AEG AEH AEI ...... 解决方案 http://bbs.csdn.net/topics/390544278

java实现Spring在XML配置java类的方法_java

1. 创建自己的bean文件:beans.xml <?xml version="1.0" encoding="UTF-8"?> <busi-beans> <beans> <bean id="SysHelloImpl" type="com.cxm.test.SysHello"> <desc>test</desc> <impl-class>com.

精致小巧的java相册制作方法_java

本文实例为大家分享了java相册制作方法,供大家参考,具体内容如下   注: 1)html上的图片是静态指定的.当更新了新的图片时必须手工更新.所以使用Servlet读取本地images中的所有图片,动态显示给用户. 2)如果存在中文名的图片,由于get方式无法直接传递中文,会导致出错. 主页面–index.jsp <%@ page language="java" import="java.util.*" pageEncoding="UTF-8&qu

汇总java调用python方法_java

本文为大家分享了java调用python方法,供大家参考,具体内容如下 一.在java类中直接执行python语句 import org.python.util.PythonInterpreter; public class FirstJavaScript { public static void main(String args[]) { PythonInterpreter interpreter = new PythonInterpreter(); interpreter.exec("day

图文讲解Java中实现quickSort快速排序算法的方法_java

相对冒泡排序.选择排序等算法而言,快速排序的具体算法原理及实现有一定的难度.为了更好地理解快速排序,我们仍然以举例说明的形式来详细描述快速排序的算法原理.在前面的排序算法中,我们以5名运动员的身高排序问题为例进行讲解,为了更好地体现快速排序的特点,这里我们再额外添加3名运动员.实例中的8名运动员及其身高信息详细如下(F.G.H为新增的运动员): A(181).B(169).C(187).D(172).E(163).F(191).G(189).H(182) 在前面的排序算法中,这些排序都是由教练主

详解Java中使用泛型实现快速排序算法的方法_java

快速排序算法概念快速排序一般基于递归实现.其思路是这样的: 1.选定一个合适的值(理想情况中值最好,但实现中一般使用数组第一个值),称为"枢轴"(pivot). 2.基于这个值,将数组分为两部分,较小的分在左边,较大的分在右边. 3.可以肯定,如此一轮下来,这个枢轴的位置一定在最终位置上. 4.对两个子数组分别重复上述过程,直到每个数组只有一个元素. 5.排序完成. 基本实现方式: public static void quickSort(int[] arr){ qsort(arr,