Создание всех возможных перестановок массива в JavaScript

Быстрый ответ

Для эффективного получения перестановок применяется алгоритм Хипа:

function permute(arr) {
  const result = [];
  const swap = (a, i, j) => ([a[i], a[j]] = [a[j], a[i]]);
  const generate = (k, heapArr) => {
    if (k === 1) {
      result.push(heapArr.slice());
      return;
    }
    generate(k – 1, heapArr);
    for (let i = 0; i < k – 1; i++) {
      swap(heapArr, k % 2 ? 0 : i, k – 1);
      generate(k – 1, heapArr);
    }
  };
  generate(arr.length, arr.slice());
  return result;
}

console.log(permute([1, 2, 3]));

Функция permute рекурсивно меняет порядок элементов массива, формируя все возможные перестановки.

Эффективное устранение дубликатов

Если ваш набор содержит дубликаты, примените множества для отсеивания уникальных перестановок:

function permuteUnique(arr) {
  const result = [];
  const swap = (a, i, j) => ([a[i], a[j]] = [a[j], a[i]]);
  const generate = (k, heapArr) => {
    if (k === 1) {
      const permutationStr = JSON.stringify(heapArr);
      if (!result.includes(permutationStr)) {
        result.push(permutationStr);
      }
      return;
    }
    generate(k – 1, heapArr);
    for (let i = 0; i < k – 1; i++) {
      swap(heapArr, k % 2 ? 0 : i, k – 1);
      generate(k – 1, heapArr);
    }
  };
  generate(arr.length, arr.slice());
  return result.map(JSON.parse);
}

console.log(permuteUnique([1, 1, 2]));

Этот метод исключает повторяющиеся перестановки, преобразуя массивы в строки для последующей проверки уникальности.

Оптимизация производительности с генераторами

Для обработки больших объемов данных генераторы выдают перестановки последовательно, что позволяет достичь пространственной эффективности O(N):

function* permuteGenerator(arr) {
  const swap = (a, i, j) => ([a[i], a[j]] = [a[j], a[i]]);
  function* doGenerate(k, heapArr) {
    if (k === 1) {
      yield heapArr.slice();
    } else {
      yield* doGenerate(k – 1, heapArr);
      for (let i = 0; i < k – 1; i++) {
        swap(heapArr, k % 2 ? 0 : i, k – 1);
        yield* doGenerate(k – 1, heapArr);
      }
    }
  }
  yield* doGenerate(arr.length, arr.slice());
}

const generator = permuteGenerator([1, 2, 3]);
for (let permutation of generator) {
  console.log(permutation);
}

Такой подход позволяет сократить расход ресурсов при выполнении перестановок больших массивов.

Визуализация

Перестановки можно представить как различные варианты расположения элементов:

Перестановки — это все возможные комбинации из заданных элементов.

Обработка крайних случаев

Качественный код предусматривает обработку крайних случаев:

• Пустой массив: должен возвращать пустой массив.
• Массив из одного элемента: возращается массив, содержащий этот элемент.
• Некорректные входные данные: следует обеспечить валидацию входных данных для предотвращения ошибок.

Втягивайте на помощь математику

Освойте комбинаторику для добавления дополнительных методов генерации перестановок, включая факториалы и степенные множества.

Оптимизация перестановок

• Делайте обмены прямо в массиве для экономии памяти.
• Используйте ленивые вычисления для выполнения алгоритмов только при необходимости.
• Применяйте кэширование для ускорения работы с часто повторяющимися последовательностями.
• Попробуйте итеративный подход, чтобы избежать переполнения стека.

Верь, но проверяй: детальное тестирование

Разработка хорошей техники тестирования подразумевает:

• Простые массивы для начального тестирования.
• Большие массивы для оценки производительности.
• Тесты со сложными типами данных для проверки универсальности.

Используйте возможности ES6

С применением возможностей ES6 ваш код станет более лаконичным и производительным. Например, экспериментируйте с операторами расширения и стрелочными функциями.

Наглядная демонстрация перестановок

Наглядное отображение результатов в консоли поможет лучше презентовать ваши решения:

console.log(result.map(permutation => JSON.stringify(permutation)).join('\n'));

Такой подход к визуализации помогает при отладке и в демонстрации вашего решения.

Развивайте горизонты

Изучив другие алгоритмы перестановок, континуально развивайте алгоритмические техники и оптимизируйте свои решения для достижения наилучших результатов.

Полезные материалы

1. Array – JavaScript | MDN — все о манипуляциях с массивами.
2. Heap's algorithm – Wikipedia — детальное описание алгоритма Хипа.
3. Generating All Permutations of a Set in JavaScript: Implementation Guide | InitJS — руководство по генерации перестановок в JavaScript.
4. Permutations – Rosetta Code — примеры решения задачи перестановок на JavaScript и других языках программирования.
5. Область видимости переменных, замыкания – JavaScript.info — материал о замыканиях и области видимости, рекомендуемый для понимания функций перестановок.
6. Выражения стрелочных функций – JavaScript | MDN — сведения о стрелочных функциях на JavaScript.
7. Обозначение большого O | Interview Cake — руководство по сложности алгоритмов, полезное при оптимизации перестановок.