資訊專欄INFORMATION COLUMN
摘要：數(shù)字全排列問題描述給一個(gè)不重復(fù)的數(shù)字?jǐn)?shù)組，寫一個(gè)程序，輸出全排列。那么兩個(gè)數(shù)字的全排列怎么算呢，以為例，就是第一個(gè)數(shù)字為的剩下的數(shù)的全排列第一個(gè)數(shù)字為的剩下的數(shù)的全排列。依次類推到個(gè)數(shù)字的全排列設(shè)數(shù)組，設(shè)的全排列為，設(shè)。
數(shù)字全排列 問題描述
給一個(gè)不重復(fù)的數(shù)字?jǐn)?shù)組，寫一個(gè)程序，輸出全排列。
比如給定數(shù)組：
[1, 2, 3]
輸出：
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]解決思路
這個(gè)問題很經(jīng)典，接下來嘗試使用數(shù)學(xué)歸納法的思想來解決這個(gè)問題。
在中學(xué)的時(shí)候，我們就知道一個(gè)長(zhǎng)度為n的數(shù)列有n!個(gè)排列。因?yàn)榈谝粋€(gè)數(shù)字有n種情況，第二個(gè)數(shù)字有n-1種情況，第三個(gè)數(shù)字有n-2種情況……第n個(gè)數(shù)字只有一種情況了，用公式表示就是n*(n-1)*(n-2)….*1 = n!
我們換一個(gè)思維來考慮，以數(shù)組[1,2,3]為例，它的全排列為：
第一個(gè)數(shù)字為1的其他兩個(gè)數(shù)字的全排列 + 第一個(gè)數(shù)字為2的其他兩個(gè)數(shù)字的全排列 + 第一個(gè)數(shù)字為3的其他兩個(gè)數(shù)字的全排列。
那么兩個(gè)數(shù)字的全排列怎么算呢，以[1,2]為例，就是：
第一個(gè)數(shù)字為1的剩下的數(shù)的全排列 + 第一個(gè)數(shù)字為2的剩下的數(shù)的全排列。
因?yàn)槭Ｏ碌闹挥幸粋€(gè)數(shù)，就不用繼續(xù)了，到這就可以輸出了。
依次類推到n個(gè)數(shù)字的全排列：
設(shè)數(shù)組 p = {r1, r2, r3, r4, r5…., rn}，設(shè)p的全排列為perm(p)，設(shè)pn = p - {rn}。
那么perm(p) = { r1, perm(p1) } + { r2, perm(p2) } + {r3, perm(p3) } + …… + {rn, perm(pn) }。
同樣思路，也可以算出perm(p1), perm(p2), perm(p3)……perm(pn)。
繼續(xù)，就可以使用遞歸求解了，遞歸的出口就是perm求的全排列數(shù)組里面只有一個(gè)值。
代碼實(shí)現(xiàn)下面是java的實(shí)現(xiàn)代碼：
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {1,2,3};
Test t = new Test();
t.perm(arr, 0, arr.length);
}
//求數(shù)組全排列
public void perm(int[] nums, int start, int len) {
//判斷遞歸出口，當(dāng)start == len - 1時(shí)，也就是要做的全排列只有一個(gè)值 ，那么就可以輸出了
if(start == len - 1) {
System.out.println(Arrays.toString(nums));
}else {
/*
* 沒有到遞歸出口時(shí)，這一段代碼是關(guān)鍵
* for循環(huán)模擬的是：
* { r1, perm(p1) } + { r2, perm(p2) } + {r3, perm(p3) } + …… + {rn, perm(pn) }
* 從r1, r2, r3 一直到 rn 作為第一位，求剩下的全排列
*/
for(int i = start; i < len; i++) {
swap(nums, start, i);//通過交換，依次將每個(gè)數(shù)放在第一位
perm(nums, start + 1, len);//遞歸調(diào)用
swap(nums, start, i);//交換回來，保證原數(shù)組不會(huì)變，以進(jìn)行下一輪全排列
}
}
}
//交換數(shù)組中的兩個(gè)值
public void swap(int[] nums, int i, int j) {
int tem = nums[i];
nums[i] = nums[j];
nums[j] = tem;
}
}
輸出結(jié)果：
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2]
參考：http://www.cnblogs.com/nokiag...
https://blog.csdn.net/randyji...
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/69313.html
摘要：找規(guī)律復(fù)雜度時(shí)間空間思路由于我們只要得到第個(gè)全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì)，我們可以總結(jié)出一個(gè)規(guī)律假設(shè)全排列有個(gè)數(shù)組成，則第個(gè)全排列的第一位是。然后將得到，這個(gè)就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...
摘要：謎題三階幻方。試將這個(gè)不同整數(shù)填入一個(gè)的表格，使得每行每列以及每條對(duì)角線上的數(shù)字之和相同。列出所有的整數(shù)填充方案，然后進(jìn)行過濾。 /* * 謎題--三階幻方。 * 試將1~9這9個(gè)不同整數(shù)填入一個(gè)3×3的表格，使得每行、每列以及每條對(duì)角線上的數(shù)字之和相同。 * 策略 * 窮舉搜索。列出所有的整數(shù)填充方案，然后進(jìn)行過濾。 * 亮點(diǎn)為遞歸函數(shù)getPermut...
摘要：周末閑來無事，看到隔壁家的老王在和隔壁家的媳婦玩點(diǎn)，就進(jìn)屋看了看。發(fā)現(xiàn)老王是真不行啊，那不行，這也不行。什么是點(diǎn)我們先來約定下老王和他媳婦玩的點(diǎn)規(guī)則給定個(gè)任意數(shù)字，然后通過，將這個(gè)數(shù)字計(jì)算出。 showImg(https://segmentfault.com/img/remote/1460000019900384?w=472&h=200); 周末閑來無事，看到隔壁家的老王在和隔壁家的媳...
摘要：每一輪搜索選擇一個(gè)數(shù)加入列表中，同時(shí)我們還要維護(hù)一個(gè)全局的布爾數(shù)組，來標(biāo)記哪些元素已經(jīng)被加入列表了，這樣在下一輪搜索中要跳過這些元素。 Permutations I Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permu...
閱讀 1684·2021-11-23 09:51
閱讀 3174·2021-09-26 10:21
閱讀 798·2021-09-09 09:32
閱讀 881·2019-08-29 16:06
閱讀 3308·2019-08-26 13:36
閱讀 772·2019-08-26 10:56
閱讀 2564·2019-08-26 10:44
閱讀 1143·2019-08-23 14:04
