規(guī)律
當n = 1時， 數(shù)組arr = [A]枣抱，全排列結果為
[A];
當n = 2時豺瘤， 數(shù)組arr = [A, B]，全排列結果為
[A, B]
[B, A];
當n = 3時说订， 數(shù)組arr = [A, B, C]抄瓦，全排列結果為
[A, B, C]
[A, C, B]
[B, A, C]
[B, C, A]
[C, A, B]
[C, B, A]
到n = 3時可以看出全排列有以下規(guī)律
- 固定第一個元素潮瓶，將剩下的元素進行全排列處理；
- 將第一個元素與依次與第i（1<i<=arr.length）個元素互換钙姊，將剩下的元素進行全排列處理毯辅；
- 結束
很適合使用遞歸解決。只要寫一個全排列函數(shù)permutation煞额，能固定一個下標為i的元素思恐，剩下元素再進行全排列即可。
js實現(xiàn)
在ES5中使用閉包將全排列函數(shù)封裝立镶。
// 數(shù)組全排列
function Permutation(arr) {
this.len = 0; // 存儲全排列次數(shù)
this.arr = arr.concat(); // 傳入的數(shù)組
this.result = []; // 存儲全排列結果
// 首次創(chuàng)建對象時初始化方法
if (typeof Permutation.run == 'undefined') {
Permutation.prototype.start = function() {
this.run(0);
}
// 遞歸函數(shù)(核心方法)壁袄，index為數(shù)組下標
Permutation.prototype.run = function(index) {
// 單遍歷到數(shù)組末端時类早，將結果儲存在result數(shù)組中媚媒，全排列次數(shù)加1
if (index == this.arr.length - 1) {
this.result.push(this.arr.slice());
this.len++;
return;
}
for(let i = index; i < this.arr.length; i++) {
this.swap(this.arr, index, i); // 與下標為i的元素交換位置
this.run(index + 1); // 剩下元素全排列
this.swap(this.arr, index, i); // 復原數(shù)組
}
}
// 交換位置
Permutation.prototype.swap = function(array, i, j) {
var t;
t = array[i];
array[i] = array[j];
array[j] = t;
}
}
}
var per = new Permutation(['A', 'B', 'C']);
per.start();
console.log(per.result);
console.log(per.len);
// [ [ 'A', 'B', 'C' ],
// [ 'A', 'C', 'B' ],
// [ 'B', 'A', 'C' ],
// [ 'B', 'C', 'A' ],
// [ 'C', 'B', 'A' ],
// [ 'C', 'A', 'B' ] ]
// 6
ES5代碼使用動態(tài)原型模式創(chuàng)建對象，主要是想讓函數(shù)封裝的盡量像一個類涩僻。在ES6中有class缭召，語法可以更加簡潔高效。
// ES6
class Permutation {
constructor(arr) {
this.arr = Array.from(arr);
this.result = [];
this.len = 0;
this.run(0);
}
run(index) {
if (index == this.arr.length - 1) {
this.result.push(Array.from(this.arr));
this.len++;
return;
}
for(let i = index; i < this.arr.length; i++) {
[this.arr[index], this.arr[i]] = [this.arr[i], this.arr[index]];
this.run(index + 1);
[this.arr[index], this.arr[i]] = [this.arr[i], this.arr[index]];
}
}
}
let p = new Permutation(["A", "B", "C"]);
console.log(p.result);
console.log(p.len);
// [ [ 'A', 'B', 'C' ],
// [ 'A', 'C', 'B' ],
// [ 'B', 'A', 'C' ],
// [ 'B', 'C', 'A' ],
// [ 'C', 'B', 'A' ],
// [ 'C', 'A', 'B' ] ]
// 6
以上就是全排列的js實現(xiàn)沸停。
代碼地址：github
