简介:
本文主要介绍基于分治方式(递归)和枚举方式(循环)来构建指定字符串的全排列方法,两种方法都可以解决重复元素的全排列
欢迎探讨,如有错误敬请指正
1. 基于分治方式(递归实现)
1)一个元素的全排列只有一种
2)[A0, A1, A2]的全排列等于下面三个全排列的并集
A0开头,拼接上[A1,A2]的所有全排列
A1开头,拼接上[A0,A2]的所有全排列
A2开头,拼接上[A0,A1]的所有全排列
所以,对于[A0, A1, ……,An]的全排列,我们可以将问题转换成n个子问题:
A0开头,拼接上[A1,A2 ……,An]的所有全排列
A1开头,拼接上[A0,A2 ……,An]的所有全排列
……
An开头,拼接上[A0,A2 ……,A(n-1)]的所有全排列
而每个子问题又可以继续向下转化成n-1个子问题,最终可以转化到只有一个元素的全排列问题。
对于数组中有重复元素的情况,我们只要保证,重复元素只能有一次作为子问题的开头元素,这样我们就可以避免重复计算。
2. 基于枚举方式(循环实现)
如果我们将全排列按照大小顺序进行排序,假设我们知道了第i个排列是[A0, A1, A2, A3, ……],那么第i+1个排列就是比[A0, A1, A2, A3, ……]大,且最小的那个。找到i+1个排列的步骤如下
1)从后往前两两比较,找到第一个满足a[i]<a[i+1]的两个元素
2)从a[i+1]开始往后找,找到一个大于a[i]中最小的一个元素,这个元素的下标记为j,交换a[i]和a[j]
3)将[i+1, a.length-1]的元素全部逆序
3. 代码实现
下面是java代码的实现
- package interviewquestion;
- import java.util.HashSet;
- import java.util.LinkedList;
- import java.util.List;
- public class Permutation {
- //返装有回字符串s的全排列的List对象
- public static List < String > byTraverse(String s) {
- char[] chArr = s.toCharArray();
- List < String > list = new LinkedList < String > ();
- byTraverse0(chArr, 0, list);
- return list;
- }
- private static void byTraverse0(char[] arr, int left, List < String > list) {
- if (left >= arr.length - 1) {
- list.add(new String(arr));
- return;
- }
- //用于记录交换到left下标的每一个元素,防止计算重复的排列
- HashSet < Character > hs = new HashSet < Character > ();
- for (int i = left; i < arr.length; i++) {
- //arr[left]后面的每一个元素arr[i]都和arr[left]交换
- swap(arr, left, i);
- if (!hs.contains(arr[left])) {
- hs.add(arr[left]);
- byTraverse0(arr, left + 1, list);
- }
- //将left和i交换回来,防止遗漏,重复
- //已保证下一个交换到left下标的是未交换过的元素
- swap(arr, left, i);
- }
- }
- /*=================================================*/
- //返装有大于等于字符串s的全排列的List对象
- public static List < String > byNext(String s) {
- char[] arr = s.toCharArray();
- List < String > list = new LinkedList < String > ();
- list.add(s);
- while (next(arr)) {
- list.add(new String(arr));
- }
- return list;
- }
- private static boolean next(char[] arr) {
- boolean hasNext = false;
- int i;
- for (i = arr.length - 2; i >= 0; i--) {
- if (arr[i] < arr[i + 1]) {
- hasNext = true;
- break;
- }
- }
- //如果所有元素是从大到小排列,说明是最大的字符串
- if (!hasNext) {
- return false;
- }
- //从i+1的下标往后找(必定是单调递减),找一个比arr[i]大的集合中最小的一个
- int j;
- for (j = i + 1; j < arr.length; j++) {
- if (arr[j] <= arr[i]) {
- break;
- }
- }
- j--;
- //交换这两个元素,然后逆序i+1以后的所有元素
- swap(arr, i, j);
- reverse(arr, i + 1, arr.length - 1);
- return true;
- }
- private static void reverse(char[] arr, int from, int to) {
- for (int i = from, j = to; i < j; i++, j--) {
- swap(arr, i, j);
- }
- }
- /*=================================================*/
- private static void swap(char[] chArr, int i, int j) {
- char t = chArr[i];
- chArr[i] = chArr[j];
- chArr[j] = t;
- }
- public static void main(String[] args) {
- List < String > list1 = Permutation.byNext("1233");
- System.out.println(list1);
- System.out.println(list1.size());
- System.out.println();
- List < String > list2 = Permutation.byTraverse("1233");
- System.out.println(list2);
- System.out.println(list2.size());
- }
- }
运行结果
- [1233, 1323, 1332, 2133, 2313, 2331, 3123, 3132, 3213, 3231, 3312, 3321]
- 12
- [1233, 1323, 1332, 2133, 2313, 2331, 3213, 3231, 3123, 3132, 3312, 3321]
- 12