常見算法之全排列 全組合
來源：程序員人生 發(fā)布時間：2015-04-27 08:30:30 閱讀次數(shù)：2485次
全排列算法是1種比較常考的算法，他的做法也比較多樣。
首先我們來看看最符合我們直觀思考的，思路是這樣的：假設沒有重復元素時，傳入1個數(shù)組A，并插入到另外1個數(shù)組B中，假設B中已包括這個元素，則跳過，否則插入數(shù)組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個狀態(tài)位，假設插入過置為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>
固然它也有缺點，我們需要在這之前對他傳入數(shù)組進行轉化。例如
<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>
現(xiàn)在還有另外1種遞歸方法，假設我們的數(shù)組是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) + ....
可以看出每個全排列可以繼續(xù)分成更多的子全排列，而每一個子排列可使看成第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依此類推就能夠得出全部了，但是，這依此類推是怎樣類推法。首先，我們規(guī)定需要將傳入的字符串進行排序，小的在前大的在后。然后我們需要從前想后找前面的數(shù)小于后面的數(shù)的點，我們先叫他替換點，例如：938740，從后往前找，3是1個替換點。找到替換點以后，我們繼續(xù)從后往前找，找到第1個大于他的數(shù)，照舊是上面這個例子:937840,那這個數(shù)就是4了。好了，現(xiàn)在將他們進行替換，現(xiàn)在這個數(shù)變成947830了。然后我們需要把它從替換點這，進行反轉，把7840轉為0478，并與之前的數(shù)進行合并930478。然后從重復這個動作，就可以找到全部的數(shù)了。
<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},,{c},{ab}.....
到這我們似乎可以看到1些規(guī)律:
{} => 000
{a} => 001 => 010
...
我們可以把他們和對逐一對應,如此，我們1個值在0~size(asse(p))的值就一定代表1個唯1的值。
所以我們可以:
<span style="font-size:14px;">public static void assembly(char[] array){
int num; //全組合的組數(shù)
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>
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
