About various permutations and combinations of Java algorithm implementation methods
- 2020-04-01 02:06:01
- OfStack
1. Using binary state method to find permutation and combination, this method is easy to understand, but the operation efficiency is not high, small data permutation and combination can be used
import java.util.Arrays;
//A binary algorithm is used for full permutation
//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);
}
}
}
Two. With the idea of recursion to find permutation and combination, the amount of code is relatively large
package practice;
import java.util.ArrayList;
import java.util.List;
public class Test1 {
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();
}
}
//Find an arbitrary combination of arrays
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();//The length of the fn combination
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;
}
}
Third, using the idea of dynamic programming to find the arrangement and combination
package Acm;
//Powerful number of combinations
public class MainApp {
public static void main(String[] args) {
int[] num=new int[]{1,2,3,4,5};
String str="";
//The number of combinations of three Numbers
// count(0,str,num,3);
// The number of combinations of 1 minus n Numbers
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);
}
}
So let's do the permutation
package Acm;
//Arrange, arrange, arrange, arrange, arrange
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);
}
}
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;
}
}
}