排列算法: 假设字符串为abcd,
模仿小学初中枚举时手写的排列过程,很自然的写出:
abcd abdc acbd acdb adbc adcb
bacd badc bcad bcda bdac bdca
cabd cadb cbad cbda cdab cdba
dabc dacb dbac dbca dcab dcba
仔细观察手写的时候的规律:
添加,然后标记,如果长度够了就退栈,否则继续寻找未标记,继续添加。
编程实现:
创建辅助布尔数组index,其下标与字符串下标一致。true代表该下标的字符被标记了,反之同理。
tp为某个排列,res为TreeSet,当字符串有重复字符时自动去除重复排列
public static void permulation() {
for (int i = 0; i < len ; i++) {
if (index[i]) continue;//遍历字符串直到找到未标记的字符对应的下标
tp.append(original.charAt(i));//将此字符加入tp
index[i] = true;//标记以便下次跳过
if (tp.length() < len) {
permulation();
} else {
res.add(new String(tp));//如果tp长度等于一个排列的长度,存入res
}
//退栈
index[i] = false ;
tp.deleteCharAt(tp.length() - 1);
}
}
求组合算法:
假设abcdef选m个,m=4,手写规律为
abcd abce abcf abde abdf abef acde acdf acef adef//10
bcde bcdf bcef bdef//4
cdef //1
观察发现不重复的算法为:
选定一个元素后,每次向后找元素,绝不往前找。但是向后寻找的距离最大为len-m
我们把abcdef看成整体,假设有一个四个字符大小的箱子,开始时框住了abcd。假设有一个力将箱子向右推,最后只能框住cdef。箱子的位移正是每个下标最多向后推移长度len-m=2!
记向后移动次数为movetime<=len-m;初始为0;
pointer为下一个需要添加进tp的字符在original数组中的下标,即以不变的字符串数组为参考。如pointer=1时指b(original[1]=b),根据向后找原则,接下来只能添加ac**,ad**形式字符串,即pointer变为2或3,因为original[2]=c,original[3]=d。所以可用movetime控制pointer的值。
如前面排列算法相似,一边循环,一边递归。但是只能向后查找。
public static void combination_iteration(int pointer) {
int movetime = 0;
while (movetime <= len - public_m) {
if (pointer + movetime >= len) return;
tp.append(original.charAt(pointer + movetime));
if (tp.length() == public_m) {
res.add(new String(tp));
System.out.println(tp);
} else {
if (pointer + movetime + 1 < len)
combination _iteration(pointer + movetime + 1);
}
tp.deleteCharAt(tp.length() - 1);
movetime++;
}
}
如果有重复字符的组合复杂很多。如abcda5选3应该拆成a+bcd3选2 并上 aa+bcd3选1
但是多种重复字符的话情况会很复杂。。暂时不考虑。。
完整的排列+组合程序:
package Permutation_Combination;
import java.util.*;
public class Permutation {
private static String original;
private static boolean[] index;
private static int len;
private static int public_m;
private static StringBuilder tp;
private static Set<String> res = new TreeSet<>();
private static int pointer;
public static void main(String[] args) {
while(true) {
Scanner i = new Scanner(System.in);
tp= new StringBuilder();
System.out.println("请输入字符串:");
original = i.nextLine();
System.out.println(original);
len = original.length();
index = new boolean[len];
System.out.print("1.排列n2.组合n");
long begin = System.currentTimeMillis();
if (i.nextInt() == 1) {
permulation();
} else {
System.out.println("请输入从中选择的字符数");
int mt = i.nextInt();
combination(mt);
}
long end = System.currentTimeMillis();
for (String k : res) {
System.out.println(k);
}
System.out.printf(" Costing %d msn", end - begin);
System.out.println(res.size());
res.clear();
}
}
public static void combination_iteration(int pointer) {
int movetime = 0;
while (movetime <= len - public_m) {
if (pointer + movetime >= len) return;
tp.append(original.charAt(pointer + movetime));
if (tp.length() == public_m) {
res.add(new String(tp));
} else {
if (pointer + movetime + 1 < len)
combination_iteration(pointer + movetime + 1);
}
tp.deleteCharAt(tp.length() - 1);
movetime++;
}
}
public static void combination(int m) {
//n个选m个
public_m = m;
combination_iteration(0);
}
public static void permulation() {
for (int i = 0; i < len; i++) {
// if(sta.contains(i)) continue;
if (index[i]) continue;
tp.append(original.charAt(i));
// sta.push(i);
index[i] = true;
if (tp.length() < len) {
permulation();
} else {
res.add(new String(tp));
}
// sta.pop();
index[i] = false;
tp.deleteCharAt(tp.length() - 1);
}
}
}