字符串的全排列，普通递归如下：
import org.junit.Test;
public class AllSort {
public void permutation(char[] buf, int start, int end) {
if (start == end) {// 当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可
for (int i = 0; i <= end; i++) {
System.out.print(buf[i]);
}
System.out.println();
} else {// 多个字母全排列
for (int i = start; i <= end; i++) {
char temp = buf[start];// 交换数组第一个元素与后续的元素
buf[start] = buf[i];
buf[i] = temp;
permutation(buf, start + 1, end);// 后续元素递归全排列
temp = buf[start];// 将交换后的数组还原
buf[start] = buf[i];
buf[i] = temp;
}
}
}
@Test
public void testPermutation() throws Exception {
char[] buf = new char[] { 'a', 'b', 'c' };
permutation(buf, 0, 2);
}
}
详细的解析：
http://blog.csdn.net/randyjiawenjie/article/details/6313729
字典序算法如下：
假设这n个数的某一个排列为 P: P1 P2 P3...Pj-1 Pj Pj+1...Pk-1 Pk Pk+1...Pn
1.从该序列的最右端开始向左找出第一个比与自己相邻的右边数小的数，记其下标为j，即j = max{i|Pi<Pi+1}.
2.找出Pj右边比Pj大的最小数Pk.
3.交换Pj,Pk.此时序列变为 P’: P1 P2 P3...Pj-1 Pk Pj+1...Pk-1 Pj Pk+1...Pn
4.将Pj+1...Pn 倒转，即得到此序列的后一个序列 P”: P1 P2 P3...Pj-1 Pn...Pk+1 Pj Pk-1...Pj+1
例：
1 2 3 5 7 4 6 10 9 8为1-10的一个排列
1.从该序列的最右端开始向左找出第一个比与自己相邻的右边数小的数6，其下标为7
2.6右边比6大的最小数为8
3.交换6,8得到1 2 3 5 7 4 8 10 9 6
4.将P8-P10倒转得到：1 2 3 5 7 4 8 6 9 10即为下一个序列
实现如下：
package July.第一章;
import java.util.Arrays;
import java.util.stream.StreamSupport;
/**
* Created by lenovo on 2016/12/1.
* 字典序排列
*/
public class CalcAllPermutation_2 {
//1，从右端开始扫描，若出现前一个比后一个小，记录前一个的元素下表index
void getDictionary(char[] input){
System.out.println(new String(input));
int i=0;
while (true){
for ( i=input.length-1;i>0;i--){
if (input[i-1]<input[i]) break;
}
if (i==0) break;//该循环只有在i==0时才会break!
int minIndex=getMin(input,i-1);
exchange(input,i-1,minIndex);
reverse(input,i,input.length-1);
System.out.println(new String(input));
}
}
//2，找出index以后比该元素大的中的最小值的下标minIndex,index为找见的满足1的下标
int getMin(char[] input,int index){
char min=input[index];
char result='z';
int minIndex = index+1;
for (int i=index+1;i<input.length;i++){
if (input[i]>min&&input[i]<result){
result=input[i];
minIndex=i;
}
}
return minIndex;
}
//3.交换下标为index和minIndex中的值
void exchange(char[] input,int index,int minIndex){
char temp=input[index];
input[index]=input[minIndex];
input[minIndex]=temp;
}
//index开始后面的字符进行逆序
void reverse(char[] input,int start,int end){
while (start<end){
exchange(input,start,end);
start++;
end--;
}
}
public static void main(String[] args){
String input="adew";
char [] c=input.toCharArray();
Arrays.sort(c);
new CalcAllPermutation_2().getDictionary(c);
}
}
字符的所有组合：
package July.第一章;
import java.util.Arrays;
import java.util.stream.StreamSupport;
/**
* Created by lenovo on 2016/12/1.
* 字典序排列
*/
public class CalcAllPermutation_2 {
//1，从右端开始扫描，若出现前一个比后一个小，记录前一个的元素下表index
void getDictionary(char[] input){
System.out.println(new String(input));
int i=0;
while (true){
for ( i=input.length-1;i>0;i--){
if (input[i-1]<input[i]) break;
}
if (i==0) break;
int minIndex=getMin(input,i-1);
exchange(input,i-1,minIndex);
reverse(input,i,input.length-1);
System.out.println(new String(input));
}
}
//2，找出index以后比该元素大的中的最小值的下标minIndex,index为找见的满足1的下标
int getMin(char[] input,int index){
char min=input[index];
char result='z';
int minIndex = index+1;
for (int i=index+1;i<input.length;i++){
if (input[i]>min&&input[i]<result){
result=input[i];
minIndex=i;
}
}
return minIndex;
}
//3.交换下标为index和minIndex中的值
void exchange(char[] input,int index,int minIndex){
char temp=input[index];
input[index]=input[minIndex];
input[minIndex]=temp;
}
//index开始后面的字符进行逆序
void reverse(char[] input,int start,int end){
while (start<end){
exchange(input,start,end);
start++;
end--;
}
}
/** 数组元素的全组合 */
static void combination(char[] chars) {
char[] subchars = new char[chars.length]; //存储子组合数据的数组
//全组合问题就是所有元素(记为n)中选1个元素的组合, 加上选2个元素的组合...加上选n个元素的组合的和
for (int i = 0; i < chars.length; ++i) {
final int m = i + 1;
combination(chars, chars.length, m, subchars, m);
}
}
/**
* n个元素选m个元素的组合问题的实现. 原理如下:
* 从后往前选取, 选定位置i后, 再在前i-1个里面选取m-1个.
* 如: 1, 2, 3, 4, 5 中选取3个元素.
* 1) 选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可;
* 2) 如果不包含5, 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可;
* 3) 如果也不包含4, 直接选取3, 那么再在前2个里面选取2个, 刚好只有两个.
* 纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m.
* 横向看, 该问题为一个前i-1个中选m-1的递归.
*/
static void combination(char[] chars, int n, int m, char[] subchars, int subn) {
if (m == 0) { //出口
for (int i = 0; i < subn; ++i) {
System.out.print(subchars[i]);
}
System.out.println();
} else {
for (int i = n; i >= m; --i) { // 从后往前依次选定一个
subchars[m - 1] = chars[i - 1]; // 选定一个后
combination(chars, i - 1, m - 1, subchars, subn); // 从前i-1个里面选取m-1个进行递归
}
}
}
public static void main(String[] args){
String input="adew";
char [] c=input.toCharArray();
// Arrays.sort(c);
// new CalcAllPermutation_2().getDictionary(c);
combination(c);
}
}
网友评论