關(guān)于各種排列組合java算法實(shí)現(xiàn)方法
一.利用二進(jìn)制狀態(tài)法求排列組合，此種方法比較容易懂，但是運(yùn)行效率不高，小數(shù)據(jù)排列組合可以使用
import java.util.Arrays;
//利用二進(jìn)制算法進(jìn)行全排列
//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();
}
}
// 求一個(gè)數(shù)組的任意組合
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;
}
}
三.利用動(dòng)態(tài)規(guī)劃的思想求排列和組合
package Acm;
//強(qiáng)大的求組合數(shù)
public class MainApp {
public static void main(String[] args) {
int[] num=new int[]{1,2,3,4,5};
String str="";
//求3個(gè)數(shù)的組合個(gè)數(shù)
// count(0,str,num,3);
// 求1-n個(gè)數(shù)的組合個(gè)數(shù)
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 表示要排列的數(shù)組
* @param str 以排列好的字符串
* @param nn 剩下需要排列的個(gè)數(shù)，如果需要全排列，則nn為數(shù)組長度
*/
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;
}
}
}
相關(guān)文章
SpringCloud+MyBatis分頁處理（前后端分離）
這篇文章主要為大家詳細(xì)介紹了SpringCloud+MyBatis分頁處理，前后端分離，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
對Java的面對對象編程中對象和引用以及內(nèi)部類的理解
這篇文章主要介紹了對Java的面對對象編程中對象和引用以及內(nèi)部類的理解,需要的朋友可以參考下2016-01-01
這篇文章主要介紹了聊聊Java并發(fā)中的Synchronized，介紹了同步的基礎(chǔ)，原理，鎖的相關(guān)內(nèi)容，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11
這篇文章主要介紹了深入淺析TomCat Session管理分析,需要的朋友可以參考下2015-11-11
Java 內(nèi)存模型中的happen-before關(guān)系詳解
這篇文章主要為大家介紹了Java 內(nèi)存模型中的happen-before關(guān)系示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-10-10
淺談為什么同一個(gè)java文件只能有一個(gè)public類
這篇文章主要介紹了淺談為什么同一個(gè)java文件只能有一個(gè)public類，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-11-11
Java基礎(chǔ)教程之類數(shù)據(jù)與類方法
這篇文章主要介紹了Java基礎(chǔ)教程之類數(shù)據(jù)與類方法,本文是對類的深入探討,類數(shù)據(jù)指類的一些屬性、參數(shù)等,類方法就是類包含的功能方法,需要的朋友可以參考下2014-08-08
String s = new String(''a '') 到底產(chǎn)生幾個(gè)對象
這篇文章主要介紹了String s = new String(" a ") 到底產(chǎn)生幾個(gè)對象，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05
MybatisPlus多數(shù)據(jù)源及事務(wù)解決思路
這篇文章主要介紹了MybatisPlus多數(shù)據(jù)源及事務(wù)解決思路,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-01-01
這篇文章主要為大家詳細(xì)介紹了基于Java實(shí)現(xiàn)記事本功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12