Generation of permutations in lexicographic order (JavaScript, NodeJS)

permutations.js

// The MIT License (MIT)

// Copyright (c) 2015 Oleksii Rudenko

// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

/**
 * Generates items.length! permutations of the array in lexicographic order
 * See https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
 */
function permutations(items) {
  const results = [[...items]];
  while ((p = permutation(items))) {
    results.push([...p]);
  }
  return results;
}

//test
a = [1, 2, 3];
assert.deepEqual(permutations(a), [
  [1, 2, 3],
  [1, 3, 2],
  [2, 1, 3],
  [2, 3, 1],
  [3, 1, 2],
  [3, 2, 1],
]);

/**
 * Generates one permutation in-place in lexicographic order
 * See https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
 */
function permutation(items) {
  var len = items.length;
  for (var k = len - 2; items[k] >= items[k + 1]; k--) {}
  if (k < 0) {
    return undefined;
  }
  for (var l = len - 1; items[k] >= items[l]; l--) {}
  if (l < 0) {
    return undefined;
  }
  swap(items, l, k);
  reverse(items, k + 1, len - 1);
  return items;
}

// test
a = [1, 2, 3];

assert.deepEqual(permutation(a), [1, 3, 2]);
assert.deepEqual(permutation(a), [2, 1, 3]);
assert.deepEqual(permutation(a), [2, 3, 1]);
assert.deepEqual(permutation(a), [3, 1, 2]);
assert.deepEqual(permutation(a), [3, 2, 1]);
assert.deepEqual(permutation(a), undefined);

var assert = require('assert'),
  a;

/**
 * Swaps two elements of an array in-place by their indexes
 */
function swap(items, left, right) {
  var tmp = items[left];
  items[left] = items[right];
  items[right] = tmp;
  return items;
}

// test
assert.deepEqual(swap([1, 2], 0, 1), [2, 1]);

/**
 * Reverses a part of an array identified by start & end (included) in-place
 */
function reverse(items, start, end) {
  var middle = start + (end - start) / 2;
  for (var i = start; i < middle; i++) {
    swap(items, i, end - (i - start));
  }
  return items;
}

// test
assert.deepEqual(reverse([1, 2], 0, 1), [2, 1]);

// test
assert.deepEqual(reverse([1, 2, 3, 4, 5, 6, 7], 2, 5), [1, 2, 6, 5, 4, 3, 7]);