全排列(分治)(Java语言 +全排列模板)

简介: 全排列(分治)(Java语言 +全排列模板)

题目描述:

用交换的分治法实现前m(m<10)个自然数数的全排列。 提示:通过交换实现的全排列不是字典序的全排列。

输入格式:

输入一个数m,代表要用1-m个自然数的全排列。

输出格式:

输出前m个自然数的全排列。(每个数之间用一个空格隔开,每行结束后有一个空格。最后一行数后面有一个空行,即每输出一行后添加一个换行,不考虑是否是最后一行)

输入样例:

3

输出样例:

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 

解题思路:

题目就是要求实现全排列(使用分治的思路),perm()函数为全排列的模板

分治思路:

分治法求解问题分为三个步骤:

  • 分解:将问题分为若干个子问题。
  • 解决:递归地求解每个子问题。
  • 合并:将每个子问题的解合并成为整个问题的解。

现在我们需要求具有n个元素的数组A的全排列。例如:大小为3的数组A=[a,b,c] ,其实应该是A=[‘a’,‘b’,‘c’]。下同),它的全排列为: [[a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a]] 这是一个大小为 n*n 的二维数组。

使用分治算法求解全排列的过程如下 :

  • 分解:将数组分为子数组 A[1…k-1] 和一个元素 A[k]。 (1≤k≤n)
  • 解决:递归地求解每个子数组 A[1…k-1] 的全排列,直至子数组A[1…k-1]为空时结束递归。
  • 合并:将上一步的结果—A[1…k-1]的全排列(一个二维数组)与元素A[k]合并,得出A[1…k]的全排列。例如: [[]] 与 a 合并得到 [[a]] [[a]] 与 b 合并得到 [[a,b], [b,a]] [[a,b],[b,a]] 与 c 合并得到 [[a,b,c],[a,c,b],[c,a,b],[b,c,a],[c,a,b],[c,b,a]]

代码:

package text2;

import java.util.Scanner;

public class 全排列_分治 {
  static int n;
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner scanner = new Scanner(System.in);
    n = scanner.nextInt();
    int arr[] = new int[n+1];
    for(int i=0;i<=n;i++)
      arr[i] = i;
    perm(arr, 1);
    
  }
  public static void perm(int arr[],int begin) {//确定了begin位置之前的 元素顺序
    if(begin==arr.length) {//生成了一种全排列
      for(int i=1;i<=n;i++) {
        System.out.print(arr[i]+" ");
      }
      System.out.println();
    }
    for(int i=begin;i<arr.length;i++) {
      int t = arr[i];
      arr[i] = arr[begin];
      arr[begin] = t;
      perm(arr, begin+1);
      //必须回溯,保证原来数组的内容
      t = arr[i];
      arr[i] = arr[begin];
      arr[begin] = t;
    }
  }

}

相关文章
|
16天前
|
IDE Java Unix
Java语言开发环境配置详解
Java语言开发环境配置详解
|
16天前
|
安全 Java Unix
Java语言中的日期与时间处理技术
Java语言中的日期与时间处理技术
|
16天前
|
XML JSON 监控
Java语言中的正则表达式技术详解
Java语言中的正则表达式技术详解
|
2天前
|
IDE Oracle Java
[笔记] 疯狂JAVA讲义(第3版) 第1章 Java语言概述与开发环境
[笔记] 疯狂JAVA讲义(第3版) 第1章 Java语言概述与开发环境
|
2天前
|
数据可视化 Java
Java语言使用DL4J实现图片分类
【6月更文挑战第14天】Java语言使用DL4J实现图片分类
13 3
|
5天前
|
安全 Java API
Java一分钟之-GraphQL:查询语言与API设计
【6月更文挑战第11天】GraphQL,一种革命性的查询语言,正在改变Web开发中的API构建和使用方式。它允许客户端按需请求数据,减少冗余,提升性能。本文概述了GraphQL的核心理念,如声明式查询、强类型和统一入口,并讨论了Java开发者常遇问题:过度查询、Schema设计和安全性。解决方案包括使用Dataloader、优化Schema和实现授权机制。通过理解原理、关注性能、重视安全和持续实践,开发者能更好地利用GraphQL构建高效API。
15 2
|
8天前
|
机器学习/深度学习 Java 开发者
Python vs. Java:语言之争的终结
【6月更文挑战第8天】Python与Java,两种影响力巨大的编程语言,各有千秋。Python以简洁语法和强大库支持在数据科学、机器学习领域大放异彩,适合快速原型设计;而Java以其稳定性能、跨平台兼容性在大型系统、企业应用中占据一席之地。语言之争实为互补,开发者应根据项目需求选择合适工具,两者和谐共存,共同推动编程技术进步。
|
9天前
|
存储 设计模式 Java
Java语言中反射动态代理接口的解释与演示
Java语言中反射动态代理接口的解释与演示
8 1
|
10天前
|
算法 Java API
Base64编码介绍及基于Java语言实现
Base64编码介绍及基于Java语言实现
13 0
|
10天前
|
Java Maven 开发者
java一分钟之-Maven Archetypes:项目模板
【6月更文挑战第6天】Maven Archetypes是Java开发中用于快速创建项目模板的工具,简化项目初始化。它们定义了项目结构、必备文件和默认配置。使用Archetypes能实现快速启动、保持项目一致性并易于扩展。常见问题包括查找和使用Archetype、理解项目结构及pom.xml配置。通过命令行工具`mvn archetype:generate`可生成项目,例如使用`maven-archetype-quickstart`创建简单Java应用。熟悉Archetypes能提升开发效率,但也需根据实际需求调整生成的配置。
31 5