排列組合算法用途廣泛，需要掌握，為降低門檻，本文主要關(guān)注算法的邏輯和簡(jiǎn)易性，未重視算法效率. 結(jié)合網(wǎng)絡(luò)書本上的實(shí)現(xiàn)和自己的需求，這里列有四個(gè)目標(biāo)：
為平壩等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及平壩網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作、平壩網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！
1. 所有元素的全排列: ab的全排列是ab, ba(順序相關(guān));
2. 所有元素的全組合: ab的全組合是a, b, ab(順序無(wú)關(guān));
3. 求n個(gè)元素中選取m個(gè)元素的組合方式有哪些: abc中選2個(gè)元素的組合是ab, ac, bc;
4. 求n個(gè)元素中選取m個(gè)元素的排列方式有哪些: abc中選2個(gè)元素的排列是ab, ba, ac, ca, bc, cb;
可以發(fā)現(xiàn)，求n個(gè)元素中選取m個(gè)元素的排列方式其實(shí)是在求出n個(gè)元素中選取m個(gè)元素的組合方式后，對(duì)每個(gè)組合組成的元素集(數(shù)組)做全排列，所以它是一個(gè)拼裝函數(shù)，未列出示例，其他三個(gè)目標(biāo)，看代碼:
重慶分公司
重慶分公司
public final class PermutationCombinationHolder {
/** 數(shù)組元素的全組合 */
static void combination(char[] chars) {
char[] subchars = new char[chars.length]; //存儲(chǔ)子組合數(shù)據(jù)的數(shù)組
//全組合問(wèn)題就是所有元素(記為n)中選1個(gè)元素的組合, 加上選2個(gè)元素的組合...加上選n個(gè)元素的組合的和
for (int i = 0; i < chars.length; ++i) {
final int m = i + 1;
combination(chars, chars.length, m, subchars, m);
}
}
/**
* n個(gè)元素選m個(gè)元素的組合問(wèn)題的實(shí)現(xiàn). 原理如下:
* 從后往前選取, 選定位置i后, 再在前i-1個(gè)里面選取m-1個(gè).
* 如: 1, 2, 3, 4, 5 中選取3個(gè)元素.
* 1) 選取5后, 再在前4個(gè)里面選取2個(gè), 而前4個(gè)里面選取2個(gè)又是一個(gè)子問(wèn)題, 遞歸即可;
* 2) 如果不包含5, 直接選定4, 那么再在前3個(gè)里面選取2個(gè), 而前三個(gè)里面選取2個(gè)又是一個(gè)子問(wèn)題, 遞歸即可;
* 3) 如果也不包含4, 直接選取3, 那么再在前2個(gè)里面選取2個(gè), 剛好只有兩個(gè).
* 縱向看, 1與2與3剛好是一個(gè)for循環(huán), 初值為5, 終值為m.
* 橫向看, 該問(wèn)題為一個(gè)前i-1個(gè)中選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) { // 從后往前依次選定一個(gè)
subchars[m - 1] = chars[i - 1]; // 選定一個(gè)后
combination(chars, i - 1, m - 1, subchars, subn); // 從前i-1個(gè)里面選取m-1個(gè)進(jìn)行遞歸
}
}
}
/** 數(shù)組元素的全排列 */
static void permutation(char[] chars) {
permutation(chars, 0, chars.length - 1);
}
/** 數(shù)組中從索引begin到索引end之間的子數(shù)組參與到全排列 */
static void permutation(char[] chars, int begin, int end) {
if (begin == end) { //只剩最后一個(gè)字符時(shí)為出口
for (int i = 0; i < chars.length; ++i) {
System.out.print(chars[i]);
}
System.out.println();
} else {
for (int i = begin; i <= end; ++i) { //每個(gè)字符依次固定到數(shù)組或子數(shù)組的第一個(gè)
if (canSwap(chars, begin, i)) { //去重
swap(chars, begin, i); //交換
permutation(chars, begin + 1, end); //遞歸求子數(shù)組的全排列
swap(chars, begin, i); //還原
}
}
}
}
static void swap(char[] chars, int from, int to) {
char temp = chars[from];
chars[from] = chars[to];
chars[to] = temp;
}
static boolean canSwap(char[] chars, int begin, int end) {
for (int i = begin; i < end; ++i) {
if (chars[i] == chars[end]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
final char[] chars = new char[] {'a', 'b', 'c'};
permutation(chars);
System.out.println("===================");
combination(chars);
}
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。
