声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
给定一个字符串，求一个字符串的全排列组合
起点：字典序最小的排列，例如12345
终点：字典序最大的排列，例如54321
过程：从当前排列生成字典序列刚好比它大的下一个排列
如：21453的下一个排列是23145
解题步骤：
1、给定一个字符串S[N], 从字符串从后往找中最后一个升序的位置即S[k]>Sk+1, S[i]<S[i+1];
2、在S[i+1...N-1]中比Ai大的最小值Sj
3、交换：Si, Sj;
4、翻转：S[i+1...N-1]
Java版本非递归算法如下:
package com.mystudy.algorithm;
/**
* 字符串全排列的非递归算法,找到下一个比本身大的字符串
*
*/
public class GetNextPermutation {
public static void main(String[] args) {
int[] arr = {1,4,2,5};
print(arr);
System.out.println("nextPermutation is : ");
while(getNextPermutation(arr, arr.length)){
print(arr);
}
}
/**
* 把一个数组从from到to做反转
* @param arr
* @param from
* @param to
*/
public static void reverse(int arr[], int from, int to){
int t;
while(from < to){
t = arr[from];
arr[from] = arr[to];
arr[to] = t;
from++;
to--;
}
}
public static boolean getNextPermutation(int[] arr, int size) {
int i = size-2;//后找
while(i>=0 && arr[i]>=arr[i+1]){
i--;
}
if (i<0) {
return false;
}
//小大
int j = size - 1;
while(arr[j] <= arr[i]){
j--;
}
//交换
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
//反转
reverse(arr,i+1,size-1);
return true;
}
public static void print(int arr[]){
for (int i : arr) {
System.out.print(i + "\t");
}
System.out.println();
}
}
Java版本递归算法如下：
package com.mystudy.algorithm;
/**
* 求字符串的全排列
* 递归的思想
* 比如 abcde 先求出abcd的全排列，然后将e分别插入全排列的5个位置
* a 全排列 a
* ab 全排列 ab ba
* abd 全排列即是 cab acb abc cba bca bac
*
*/
public class Permutation {
public static void main(String[] args) {
int a[] = {1,3,3,4};
permutation1(a, 0);
}
public static void print(int[] a){
for (int i : a) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* 一个字符串的全排列递归算法,时间复杂度O((n+1)!)
* @param a
* @param n
*/
public static void permutation(int a[], int n){
if (n == a.length - 1) {
print(a);
return;
}
for(int i = n; i < a.length; i++){
int temp = a[i];//交换a[i],a[n]
a[i] = a[n];
a[n] = temp;
permutation(a, n+1);
temp = a[i];//交换a[i],a[n]
a[i] = a[n];
a[n] = temp;
}
}
/**
* 判断一个数字是否在数组中
* @param a
* @param n
* @param t
* @return
*/
public static boolean isDuplicate(int[] a, int n, int t){
while(n < t){
if (a[n] == a[t]) {
return false;
}
n++;
}
return true;
}
/**
* 去除重复元素的全排列
* @param a
* @param n
*/
public static void permutation1(int a[], int n){
if (n == a.length - 1) {
print(a);
return;
}
for(int i = n; i < a.length; i++){
if (!isDuplicate(a, n, i)) {//a[i]是否与[n,i)重复
continue;
}
int temp = a[i];//交换a[i],a[n]
a[i] = a[n];
a[n] = temp;
permutation1(a, n+1);
temp = a[i];//交换a[i],a[n]
a[i] = a[n];
a[n] = temp;
}
}
}
去除重复的排列的结果：
1 3 3 4
1 3 4 3
1 4 3 3
3 1 3 4
3 1 4 3
3 3 1 4
3 3 4 1
3 4 3 1
3 4 1 3
4 3 3 1
4 3 1 3
4 1 3 3
不去重复的排列结果：
1 3 3 4
1 3 4 3
1 3 3 4
1 3 4 3
1 4 3 3
1 4 3 3
3 1 3 4
3 1 4 3
3 3 1 4
3 3 4 1
3 4 3 1
3 4 1 3
3 3 1 4
3 3 4 1
3 1 3 4
3 1 4 3
3 4 1 3
3 4 3 1
4 3 3 1
4 3 1 3
4 3 3 1
4 3 1 3
4 1 3 3
4 1 3 3
