大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
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
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
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
result+=num[temp[i]];
}
System.out.println(result);
}
}
}
一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用
二.用递归的思想来求排列跟组合,代码量比较大
package practice;
import java.util.ArrayList;
import java.util.List;public classTest1 {/**
* @param args*/
public static voidmain(String[] args) {//TODO Auto-generated method stub
Object[] tmp={1,2,3,4,5,6};//ArrayList rs=RandomC(tmp);
ArrayList rs=cmn(tmp,3);for(int i=0;i
{//System.out.print(i+”=”);
for(int j=0;j
{
System.out.print(rs.get(i)[j]+”,”);
}
System.out.println();
}
}//求一个数组的任意组合
static ArrayListRandomC(Object[] source)
{
ArrayList result=new ArrayList();if(source.length==1)
{
result.add(source);
}else{
Object[] psource=new Object[source.length-1];for(int i=0;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
{
Object[] tmp=new Object[result.get(i).length+1];for(int j=0;j
{
tmp[j]=result.get(i)[j];
}
tmp[tmp.length-1]=source[source.length-1];
result.add(tmp);
}
}returnresult;
}static ArrayList cmn(Object[] source,intn)
{
ArrayList result=new ArrayList();if(n==1)
{for(int i=0;i
{
result.add(newObject[]{source[i]});
}
}else if(source.length==n)
{
result.add(source);
}else{
Object[] psource=new Object[source.length-1];for(int i=0;i
{
psource[i]=source[i];
}
result=cmn(psource,n);
ArrayList tmp=cmn(psource,n-1);for(int i=0;i
{
Object[] rs=newObject[n];for(int j=0;j
{
rs[j]=tmp.get(i)[j];
}
rs[n-1]=source[source.length-1];
result.add(rs);
}
}returnresult;
}
}
三.利用动态规划的思想求排列和组合
packageAcm;//强大的求组合数
public classMainApp {public static voidmain(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,intn) {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);
}
}
下面是求排列
packageAcm;//求排列,求各种排列或组合后排列
importjava.util.Arrays;importjava.util.Scanner;public classDemo19 {private static booleanf[];public static voidmain(String[] args) {
Scanner sc=newScanner(System.in);int sz=sc.nextInt();for(int i=0;i
f=new boolean[sum];
Arrays.fill(f,true);int[] num=new int[sum];for(int j=0;j
num[j]=j+1;
}int nn=sc.nextInt();
String str=””;
count(num,str,nn);
}
}/***
*@paramnum 表示要排列的数组
*@paramstr 以排列好的字符串
*@paramnn 剩下需要排列的个数,如果需要全排列,则nn为数组长度*/
private static void count(int[] num, String str, intnn) {if(nn==0){
System.out.println(str);return;
}for(int i=0;i
}
f[i]=false;
count(num,str+num[i],nn-1);
f[i]=true;
}
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/179096.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...