3.permutations.md

Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

JavaScript

function Lexico(nums) {
    this._array = nums.sort();
}

Lexico.prototype.next = function () {

    for (var i = this._array.length - 1; i > 0; --i) {
        if (this._array[i] > this._array[i - 1]) {
            var pivot = i - 1;
            for (var j = this._array.length - 1; j > pivot; --j) {
                if (this._array[j] > this._array[pivot]) {
                    //swap
                    let c = this._array[j];
                    this._array[j] = this._array[pivot];
                    this._array[pivot] = c;

                    let newArray = this._array.slice(0);
                    let firstPart = newArray.slice(0, pivot + 1);
                    let secondPart = newArray.slice(pivot + 1, this._array.length).reverse();
                    newArray = firstPart.concat(secondPart);
                    this._array = newArray;
                    console.log(this._array);

                    return newArray.slice(0);
                }
            }
        }
    }

    return false;

}

Lexico.prototype.value = function () {
    return this._array.slice(0);
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    var result = [];

    if (nums.length === 1) {
        return [nums];
    }

    let lexico = new Lexico(nums);

    result.push(lexico.value());
    console.log();
    while (true) {
        if (val = lexico.next()) {
            result.push(val);
        } else {
            break;
        }
    }

    return result;
};