算法笔记_025:字符串的全排列(Java)

时间:2021-05-10 09:53:52

目录

1 问题描述

2 解决方案

2.1 递归实现

2.2 字典序排列实现

 


1 问题描述

输入一个字符串,打印出该字符串的所有排列。例如,输入字符串”abc”,则输出有字符’a’,’b’,’c’所能排列出来的所有字符串”abc”,”acb”,”bac”,”bca”,”cab”,”cba”。

 


2 解决方案

2.1 递归实现

从字符串中选出一个字符作为排列的第一个字符,然后对剩余的字符进行全排列。如此递归处理,从而得到所有字符的全排列。

具体代码如下:

package com.liuzhen.string_1;

public class StringArrange {//方法1:递归实现
/*
* 参数arrayA:给定字符串的字符数组
* 参数start:开始遍历字符与其后面各个字符将要进行交换的位置
* 参数end:字符串数组的最后一位
* 函数功能:输出字符串数字的各个字符全排列
*/
public void recursionArrange(char[] arrayA,int start,int end){
if(end <= 1)
return;
if(start == end){
for(int i = 0;i < arrayA.length;i++)
System.out.print(arrayA[i]);
System.out.println();
}
else{
for(int i = start;i <= end;i++){
swap(arrayA,i,start);
recursionArrange(arrayA,start
+1,end);
swap(arrayA,i,start);
}
}

}
//交换数组m位置和n位置上的值
public void swap(char[] arrayA,int m,int n){
char temp = arrayA[m];
arrayA[m]
= arrayA[n];
arrayA[n]
= temp;
}

public static void main(String[] args){
StringArrange test
= new StringArrange();
String A
= "abc";
char[] arrayA = A.toCharArray();
test.recursionArrange(arrayA,
0,arrayA.length-1);
}
}

运行结果:

abc
acb
bac
bca
cba
cab

 

2.2 字典序排列实现

思想如下:

(1)找到排列中最后(最右)一个升序的首位位置i

(2)找到排列中第i位右边最后一个比ai大的位置j

(3)交换aiaj的值。

(4)把第i+1位到最后一位的部分进行逆序反转。

具体代码如下:

package com.liuzhen.string_1;

public class StringArrange {
//方法2:字典序排列
/*
* 参数arrayA:给定字符串的字符数组
* 函数功能:输出字符串数组的所有字符的字典序全排列
*/
public void dictionaryArrange(char[] arrayA){
System.out.println(String.valueOf(arrayA));
while(allArrange(arrayA))
System.out.println(String.valueOf(arrayA));
}
//判断当前数组arrayA序列是否可以进行字典序排列,如可以则进行排列并返回true,否则返回false
public boolean allArrange(char[] arrayA){
int i;
for(i = arrayA.length-2;(i >= 0) && arrayA[i] > arrayA[i+1];--i);
if(i < 0)
return false;
int k;
for(k = arrayA.length-1;(k > i) && arrayA[i] >= arrayA[k];--k);
swap(arrayA,i,k);
reverseArray(arrayA,i
+1,arrayA.length-1);
return true;
}
//将数组中a[m]到a[n]一段元素反序排列
public void reverseArray(char[] arrayN,int m,int n){
while(m < n){
char temp = arrayN[m];
arrayN[m
++] = arrayN[n];
arrayN[n
--] = temp;
}
}
//交换数组m位置和n位置上的值
public void swap(char[] arrayA,int m,int n){
char temp = arrayA[m];
arrayA[m]
= arrayA[n];
arrayA[n]
= temp;
}
public static void main(String[] args){
StringArrange test
= new StringArrange();
String A
= "abc";
char[] arrayA = A.toCharArray();
test.dictionaryArrange(arrayA);
}
}

 运行结果:

abc
acb
bac
bca
cab
cba