排列組合算法用途廣泛，需要掌握，為降低門檻，本文主要關(guān)注算法的邏輯和簡(jiǎn)易性，未重視算法效率. 結(jié)合網(wǎng)絡(luò)書本上的實(shí)現(xiàn)和自己的需求，這里列有四個(gè)目標(biāo)：
1. 所有元素的全排列: ab的全排列是ab, ba(順序相關(guān));
2. 所有元素的全組合: ab的全組合是a, b, ab(順序無關(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)，看代碼:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
public final class PermutationCombinationHolder { /** 數(shù)組元素的全組合 */ static void combination(char[] chars) { char[] subchars = new char[chars.length]; //存儲(chǔ)子組合數(shù)據(jù)的數(shù)組 //全組合問題就是所有元素(記為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è)元素的組合問題的實(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è)子問題, 遞歸即可; * 2) 如果不包含5, 直接選定4, 那么再在前3個(gè)里面選取2個(gè), 而前三個(gè)里面選取2個(gè)又是一個(gè)子問題, 遞歸即可; * 3) 如果也不包含4, 直接選取3, 那么再在前2個(gè)里面選取2個(gè), 剛好只有兩個(gè). * 縱向看, 1與2與3剛好是一個(gè)for循環(huán), 初值為5, 終值為m. * 橫向看, 該問題為一個(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í)有所幫助，也希望大家多多支持服務(wù)器之家。
