Quick and efficient permutations with max length

Question

I want to make a permutation function in javascript that very quickly finds all permutations of an array, with every length before it (I'll give an example explaining this further). It needs to be as quick and efficient as possible, and should not have any duplicates. For example, the function would take an input of a list which would be like

[0, 1, 2]

and the expected output would be

[[0], [1], [2], [0, 1], [0, 2], [1, 2], [1, 2, 3]]

There wouldn't be any duplicates in the array (like [0, 0] wouldn't work), and swapped values shouldn't be there either ([1, 0] and [0, 1] both wouldn't be there. Only one of them).

I've looked at this question and this question but am still unable to get what I wanted.

The most important thing is that this needs to be as efficient as possible (take as little time to execute as possible)

`but am still unable to get what I wanted`. What did they fail to address in your case? Be specific and detailed. Your question contains a general lack of apparent effort, because you haven't made any concrete requirements. "As efficient as possible" is not concrete. What are the specific timing limitations you are trying to meet? Beyond that is wasted effort in optimization. — Patrick Roberts, Sep 19 '19 at 17:43
@PatrickRoberts it was too slow. the amount of times I had to run it, then go through the results to make it how I wanted took too long — Aniket Gupta, Sep 19 '19 at 18:17
Based on your comment, and your question as-is, the only assumption I can make is that you're saying generating `[[0], [1], [2], [0, 1], [0, 2], [1, 2], [1, 2, 3]]` is too slow. I find that hard to believe. — Patrick Roberts, Sep 19 '19 at 18:34
@PatrickRoberts I made it a smaller example, if there were 6 digits, it would take longer. If there were more, it would take longer. Etc. — Aniket Gupta, Sep 20 '19 at 01:44
FYI, for an array of length _n_, there are _2^n_ combinations. — Patrick Roberts, Sep 20 '19 at 12:13

score 1 · Accepted Answer · answered Sep 19 '19 at 17:31

Vocabulary lesson: these are actually combinations, not permutations. With permutations, a different order is a different permutations. Also, what you want technically isn't all combinations, as there is the empty combination [] and it seems you don't want that included.

Anyway, here's something I whipped up.

function getCombinations(array) {
    let combinations = [];
    for (let value of array) {
        combinations = combinations
            .concat(combinations.map(value0 => value0.concat([value])))
            .concat([[value]]);
    }
    
    return combinations;
}

console.log(getCombinations([0, 1, 2, 3]))

Thanks for your response! It's exactly what I'm looking for – Aniket Gupta Sep 20 '19 at 17:00 — Aniket Gupta, Sep 20 '19 at 17:00

Patrick Roberts · Answer 2 · 2019-09-20T17:41:00.200

Working off of Mason's answer, I thought I'd tune it a bit more for performance, avoiding the overhead of copying using Array.prototype.concat(), and implicit array iterator usage with for...of:

function getCombinations (array) {
  const combinations = [];

  for (let i = 0; i < array.length; ++i) {
    const value = array[i];
    const { length } = combinations;

    combinations.push([value]);

    for (let j = 0; j < length; ++j) {
      const oldCombination = combinations[j];
      const oldLength = oldCombination.length;
      const newCombination = [];

      for (let k = 0; k < oldLength; ++k) {
        newCombination.push(oldCombination[k]);
      }

      newCombination.push(value);
      combinations.push(newCombination);
    }
  }

  return combinations;
}

const input = Array.from({ length: 23 }, (_, i) => i);
const start = performance.now();
getCombinations(input);
console.log(performance.now() - start);

Below, I've provided a benchmark to compare with Mason's answer:

function getCombinationsMason(array) {
  let combinations = [];
  for (let value of array) {
    combinations = combinations
      .concat(combinations.map(value0 => value0.concat([value])))
      .concat([
        [value]
      ]);
  }

  return combinations;
}

function getCombinationsPatrick(array) {
  const combinations = [];

  for (let i = 0; i < array.length; ++i) {
    const value = array[i];
    const {
      length
    } = combinations;

    combinations.push([value]);

    for (let j = 0; j < length; ++j) {
      const oldCombination = combinations[j];
      const oldLength = oldCombination.length;
      const newCombination = [];

      for (let k = 0; k < oldLength; ++k) {
        newCombination.push(oldCombination[k]);
      }

      newCombination.push(value);
      combinations.push(newCombination);
    }
  }

  return combinations;
}

function average(algorithm, input, times) {
  let total = 0;

  for (let i = 0; i < times; ++i) {
    total -= performance.now();
    algorithm(input);
    total += performance.now();
  }

  return `${algorithm.name}(): ${(total / times).toFixed(2)}ms average over ${times} times`;
}

const input = Array.from({
  length: 18
}, (_, i) => i);

console.log('input.length:', input.length);

// randomize order of testing
if (Math.random() > 0.5) {
  // warmup
  average(getCombinationsMason, input, 2);
  average(getCombinationsPatrick, input, 2);
  // benchmark
  console.log(average(getCombinationsMason, input, 20));
  console.log(average(getCombinationsPatrick, input, 20));
} else {
  // warmup
  average(getCombinationsPatrick, input, 2);
  average(getCombinationsMason, input, 2);
  // benchmark
  console.log(average(getCombinationsPatrick, input, 20));
  console.log(average(getCombinationsMason, input, 20));
}

Thanks for your response. Mason's is actually faster, so I'll accept his answer. But yours works as well, and is significantly better than what I was using earlier. — Aniket Gupta, Sep 20 '19 at 17:02
I didn't know `for...of` was so much less performant, thanks for the info — Mason, Sep 20 '19 at 22:30
@Mason it might not be that way for long; under certain circumstances the optimizer can completely bypass the overhead of all the iterator function calls and get close to the performance of a plain `for` loop, but it's not always possible to predict when those optimizations will kick in. — Patrick Roberts, Sep 20 '19 at 22:31

Quick and efficient permutations with max length

2 Answers2