写点什么

递归全排列问题(两种方法 Java 实现)

用户头像
若尘
关注
发布于: 2021 年 06 月 09 日
递归全排列问题(两种方法 Java实现)

递归全排列问题(Java 实现)

问题描述

  • 生成 {1,2,…,n} 的所有 n! 个排列

算法

1. 固定位置放元素



  • 算法思想

  • 生成元素{2,3,…,n}的所有排列,并且将元素 1 放到每个排列的开头

  • 生成元素{1,3,…,n}的所有排列,并将数字 2 放到每个排列的开头

  • 重复这个过程,直到元素{2,3,…,n-1}的所有排列都产生,并将元素 n 放到每个排列的开头

  • Java 源代码


/* * 若尘 */package perm;
import java.util.Arrays;
/** * 全排列问题(递归) * @author ruochen * @version 1.0 */public class GeneratiingPerm {
public static int count = 0; public static void main(String[] args) { char[] arr = {'a', 'b', 'c'}; int start = 0; int end = arr.length - 1; perm(arr, start, end); System.out.println("共有 " + count + " 种排列方式"); } /** * 实现全排列 * @param arr 待求全排列数组 * @param start 开始位置 * @param end 结束位置 */ public static void perm(char[] arr, int start, int end) { if (start == end) { count++; System.out.println(Arrays.toString(arr)); } else { for (int i = start; i <= end; i++) { swap(arr, start, i); perm(arr, start + 1, end); // 为了排列不会丢失,我们这里在交换回来,使得每次都是以一个固定序列开始 swap(arr, start, i); } } } /** * 交换两个数组元素 * @param arr 数组 * @param i 第一个元素下标 * @param j 第二个元素下标 */ public static void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}
复制代码


  • 时间复杂度 $T(n) = \begin{cases}θ(1) & n = 1 \nT(n - 1) + n & n > 1 \\end{cases}$

2. 固定元素找位置

  • 算法思想

  • 首先,我们把 n 放在的位置 P[1]上,并且用子数组 P[2..n]来产生前 n-1 个数的排列

  • 接着,我们将 n 放在 P[2]上,并且用子数组 P[1]和 P[3..n]来产生前 n-1 个数的排列

  • 然后,我们将 n 放在 P[3]上,并且用子数组 P[1..2]和 P[4..n]来产生前 n-1 个数的排列

  • 重复上述过程直到我们将 n 放在 P[n]上,并且用子数组 P[1..n]来产生前 n-1 个数的排列

  • Java 源代码


public static void perm2(char[] arr, int start, int end) {  if (end == 0) {    System.out.println(Arrays.toString(arr));  } else {    for (int i = start; i <= end; i++) {      if (arr[i] == 0) {        arr[i] = (char) end;        perm2(arr, start, end - 1);        arr[i] = 0;      }    }  }}
复制代码


  • 时间复杂度 $T(n) = \begin{cases}θ(1) & n = 1 \nT(n - 1) + n & n > 1 \\end{cases}$

发布于: 2021 年 06 月 09 日阅读数: 7
用户头像

若尘

关注

还未添加个人签名 2021.01.11 加入

还未添加个人简介

评论

发布
暂无评论
递归全排列问题(两种方法 Java实现)