Быстрая и эффективная перестановка с максимальной длиной

Question

Я хочу сделать функцию перестановки в javascript, которая очень быстро находит все перестановки массива, с каждой длиной до него (я приведу пример, объясняющий это далее).Он должен быть максимально быстрым и эффективным и не должен иметь дубликатов.Например, функция будет принимать ввод списка, который будет выглядеть как

[0, 1, 2]

, а ожидаемый результат будет

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

В массиве не будет дубликатов(например, [0, 0] не будет работать), и поменяемые значения также не должны быть там ([1, 0] и [0, 1] оба не будут там. Только один из них).

Я смотрел на этот вопрос и на этот вопрос , но все еще не могу получить то, что хотел.

Наиболее важным является то, что это должно быть максимально эффективным (требуется как можно меньше времени для выполнения)

Answer 1

Словарный урок: на самом деле это комбинации, а не перестановки.С перестановками другой порядок - это разные перестановки.Кроме того, технически вам нужны не все комбинации, так как есть пустая комбинация [], и кажется, что вы не хотите, чтобы она включалась.

В любом случае, вот что я подхватил.

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]))

Answer 2

Отрабатывая ответ Мейсона, я подумал, что настроил бы его немного больше для повышения производительности, избежав накладных расходов при копировании с использованием Array.prototype.concat() и неявного использования итератора массива с использованием 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);

Ниже я предоставил тест для сравнения с ответом Мейсона:

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));
}