关于各种排列组合java算法实现方法
发布时间:2023-11-15 05:46:55
一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用
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;
}
}
}
猜你喜欢
- 本节我们来探讨如何使用Feign构造多参数的请求。笔者以GET以及POST方法的请求为例进行讲解,其他方法(例如DELETE、PUT等)的请
- 下载UEditorhttps://ueditor.baidu.com/website/download.html下载完整源码和JSP版本Sp
- 前言研究表明,Java堆中对象占据最大比重的就是字符串对象,所以弄清楚字符串知识很重要,本文主要重点聊聊字符串常量池。Java中的字符串常量
- 一、项目简述功能javaweb 网上商城系统,前台+后台管理,用户注册,登录,上哦展示,分组展示,搜索,收货地址管理,购物车管理,添加,购买
- 工厂模式Spring中bean的创建,默认是框架利用反射new出来的bean实例。有时候也会有一些复杂的情况。假设有一个飞机,属性如下,现在
- SpringMVC异常处理机制(一)项目前准备首先参照文章Spring课程工程构建+SpringMVC简介及其快速入门搭建项目搭建好一个项目
- 摘要:介绍使用Java Stream流排序器Comparator对List集合进行多字段排序的方法,包括复杂实体对象多字段升降序排序方法。综
- 前文本章是关于Java流程控制语句的最全汇总,本篇为汇总中篇。流程是人们生活中不可或缺的一部分,它表示人们每天都在按照一定的流程做事。比如出
- 本文实例为大家分享了Android九宫格图片展示的具体代码,供大家参考,具体内容如下首先来看一下我们要做成的而效果:主页面要显示一个view
- 介绍随着当今处理器中可用的核心数量的增加, 随着对实现更高吞吐量的需求的不断增长,多线程 API 变得非常流行。 Java 提供了自己的多线
- 克隆,想必大家都有耳闻,世界上第一只克隆羊多莉就是利用细胞核移植技术将哺乳动物的成年体细胞培育出新个体,甚为神奇。其实在Java中也存在克隆
- 需求场景最近项目中要做一个音乐播放悬浮按钮的功能,最终实现效果如下:问题暴露悬浮窗布局文件就不放了,就是水平LinearLayout里面放几
- 为什么需要全局异常处理在传统 Spring Boot 应用中, 我们 @ControllerAdvice 来处理全局的异常,进行统一包装返回
- namespace ConsoleApplication1{ using System; &n
- 1. 基本用法<dependency> <groupId>org.redisson</groupI
- 1、什么是FeignFeign 是 Spring Cloud Netflix 组件中的一个轻量级 RESTful 的 HTTP 服务客户端,
- 最近正式入坑Flutter,首先从环境搭建开始,看了网上好多关于Windows环境搭建的资料,基本都是按官方文档写的,看完的感受是,还不如直
- //计算字符串的MD5值 public string G
- 一、业务需求实现省份与城市的二级联动二、实现效果三、代码实现1. province_city.jsp前端界面实现<%@ p
- 1.基本知识介绍首先,C#中的.net的常用对话框中没有映射网络驱动映射对话框,所以需要用windows的API函数去实现弹出映射网络驱动器