常见算法之全排列 全组合
来源：程序员人生 发布时间：2015-04-27 08:30:30 阅读次数：2344次
全排列算法是1种比较常考的算法，他的做法也比较多样。
首先我们来看看最符合我们直观思考的，思路是这样的：假设没有重复元素时，传入1个数组A，并插入到另外1个数组B中，假设B中已包括这个元素，则跳过，否则插入数组B。我们来看看具体代码：
<span style="font-size:14px;">public static void permutation1(final String str, String buffer){
if (str.length() == buffer.length()){
System.out.println((num++) + ":" + buffer);
return;
}
for (int i = 0; i < str.length(); i++){
if (buffer.indexOf((int)str.charAt(i)) < 0){
permutation1(str, buffer + str.charAt(i));
}
}
}</span>
这个看代码就比较容易理解，所以就不多说了，它有缺点，就是不能有重复，那我们改1改，给每个值都安置1个状态位，假设插入过置为1，没有则是0，所以，我们又有了第2种方法：
<span style="font-size:14px;">public static void permutation2(final char[][] array, String result, int len){
if (result.length() == len){
System.out.println(result);
}else{
for (int i = 0; i < len; i++){
if (array[i][1] == 0){
array[i][1] = 1;
permutation2(array, result + array[i][0], len);
array[i][1] = 0;
}
}
}
}</span>
固然它也有缺点，我们需要在这之前对他传入数组进行转化。例如
<span style="font-size:14px;">public static void main(String[] args) {
String str = "abcd";
char[][] array = new char[str.length()][2];
for (int i = 0; i < str.length(); i++){
array[i][0] = str.charAt(i);
array[i][1] = 0;
}
String result = new String();
permutation2(array, result, str.length());
}</span>
现在还有另外1种递归方法，假设我们的数组是abc 那末全排列的话有abc,acb,bac,bca,cba,cab。
也就是说，a开头的和{b,c}的全排列,b开头的和{a,c}的全排列，c开头的和{a,b}全排列。
p = {r1,r2,r3,r4...} , 设 pn = p - {rn}
perm(p) = r1perm(p1) + r2perm(p2) + r3perm(p3) + ....
可以看出每个全排列可以继续分成更多的子全排列，而每一个子排列可使看成第1个字母与别的字母调换位置得来的。所以，我们还可以用以下代码求结果：
<span style="font-size:14px;">public static void swap(char[] array, int from, int to){
char temp = array[from];
array[from] = array[to];
array[to] = temp;
}
public static void permutation3(char[] array, int n){
if (n == array.length){
System.out.println(new String(array));
}else {
for (int i = n; i < array.length; i++){
swap(array, i, n);
permutation3(array, n + 1);
swap(array, i, n);
}
}
}</span>
但是呢，我们介绍的全部都是递归的算法，想要非递归怎样办呢。
首先我们来看这样1个字符串1234,需要他的全排列，怎样求呢，1243,1342依此类推就能够得出全部了，但是，这依此类推是怎样类推法。首先，我们规定需要将传入的字符串进行排序，小的在前大的在后。然后我们需要从前想后找前面的数小于后面的数的点，我们先叫他替换点，例如：938740，从后往前找，3是1个替换点。找到替换点以后，我们继续从后往前找，找到第1个大于他的数，照旧是上面这个例子:937840,那这个数就是4了。好了，现在将他们进行替换，现在这个数变成947830了。然后我们需要把它从替换点这，进行反转，把7840转为0478，并与之前的数进行合并930478。然后从重复这个动作，就可以找到全部的数了。
<span style="font-size:14px;">public static void reversal(char array[], int from, int to){
while (from < to){
swap(array, from++, to--);
}
}
public static boolean hasNext(char[] array){
if (array.length == 0 || array == null){
return false;
}
int endIndex = array.length - 1;
int q = endIndex - 1;
int p = endIndex;
while (q >= 0){
if (array[q] < array[q + 1]){
while (array[q] > array[p]){
p--;
}
swap(array, p, q);
reversal(array, q + 1, array.length - 1);
return true;
}
q--;
}
reversal(array, 0, array.length - 1);
return false;
}
public static void main(String[] args) {
char[] array = "abc".toCharArray();
do {
System.out.println(array);
} while (hasNext(array));
}</span>
但是，但是，但是，假设有是有重复字符的字符串，那要怎样办呢。还有假设某些字符是需要依照某种顺序呢，我表示我还在想，假设你知道的话，欢迎知道留言邮件都行：630841816@qq.com
以上是全排列，下面我们来讲全组合
首先我们来看个例子，p={a,b,c}的全组合：asse(p) = {}，{a},{b},{c},{ab}.....
到这我们似乎可以看到1些规律:
{} => 000
{a} => 001 {b} => 010
...
我们可以把他们和对逐一对应,如此，我们1个值在0~size(asse(p))的值就一定代表1个唯1的值。
所以我们可以:
<span style="font-size:14px;">public static void assembly(char[] array){
int num; //全组合的组数
num = 1 << array.length;
for (int i = 0; i < num; i++){
StringBuffer buffer = new StringBuffer();
for (int j = 0; j < array.length; j++){
if ((i & (1 << j)) > 0){
buffer.append(array[j]);
}
}
System.out.println(buffer);
}
}</span>
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
