Создание всех возможных перестановок массива в 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);
}
Такой подход позволяет сократить расход ресурсов при выполнении перестановок больших массивов.
Визуализация
Перестановки можно представить как различные варианты расположения элементов:
Вариант | Состав |
---|---|
1 | 🍎🍌🍍 |
2 | 🍎🍍🍌 |
3 | 🍌🍎🍍 |
4 | 🍌🍍🍎 |
5 | 🍍🍎🍌 |
6 | 🍍🍌🍎 |
Перестановки — это все возможные комбинации из заданных элементов.
Обработка крайних случаев
Качественный код предусматривает обработку крайних случаев:
- Пустой массив: должен возвращать пустой массив.
- Массив из одного элемента: возращается массив, содержащий этот элемент.
- Некорректные входные данные: следует обеспечить валидацию входных данных для предотвращения ошибок.
Втягивайте на помощь математику
Освойте комбинаторику для добавления дополнительных методов генерации перестановок, включая факториалы и степенные множества.
Оптимизация перестановок
- Делайте обмены прямо в массиве для экономии памяти.
- Используйте ленивые вычисления для выполнения алгоритмов только при необходимости.
- Применяйте кэширование для ускорения работы с часто повторяющимися последовательностями.
- Попробуйте итеративный подход, чтобы избежать переполнения стека.
Верь, но проверяй: детальное тестирование
Разработка хорошей техники тестирования подразумевает:
- Простые массивы для начального тестирования.
- Большие массивы для оценки производительности.
- Тесты со сложными типами данных для проверки универсальности.
Используйте возможности ES6
С применением возможностей ES6 ваш код станет более лаконичным и производительным. Например, экспериментируйте с операторами расширения и стрелочными функциями.
Наглядная демонстрация перестановок
Наглядное отображение результатов в консоли поможет лучше презентовать ваши решения:
console.log(result.map(permutation => JSON.stringify(permutation)).join('\n'));
Такой подход к визуализации помогает при отладке и в демонстрации вашего решения.
Развивайте горизонты
Изучив другие алгоритмы перестановок, континуально развивайте алгоритмические техники и оптимизируйте свои решения для достижения наилучших результатов.
Полезные материалы
- Array – JavaScript | MDN — все о манипуляциях с массивами.
- Heap's algorithm – Wikipedia — детальное описание алгоритма Хипа.
- Generating All Permutations of a Set in JavaScript: Implementation Guide | InitJS — руководство по генерации перестановок в JavaScript.
- Permutations – Rosetta Code — примеры решения задачи перестановок на JavaScript и других языках программирования.
- Область видимости переменных, замыкания – JavaScript.info — материал о замыканиях и области видимости, рекомендуемый для понимания функций перестановок.
- Выражения стрелочных функций – JavaScript | MDN — сведения о стрелочных функциях на JavaScript.
- Обозначение большого O | Interview Cake — руководство по сложности алгоритмов, полезное при оптимизации перестановок.