Как перебрать все возможные комбинации из n объектов?
Доброго дня, пытаюсь написать программу которая бы перебрала все возможные комбинации из n объектов или конкретнее у нас есть массив содержащий целые числа без повторений. Например из [1,3,2] и нужно получить список массивов [1,3,2], [1,2,3], [2,1,3] и так далее
не могу придумать как это сделать, а в учебниках нашел только как посчитать общее число таких комбинаций. Подскажите, пожалуйста, где можно найти подобные алгоритмы и/или их реализации на языках программирования
- Вопрос задан более трёх лет назад
- 25547 просмотров
1 комментарий
Оценить 1 комментарий
Перебрать все возможные комбинации элементов массива друг с другом
Такая задачка — есть одномерный массив, размер которого может изменяться.
Как в цикле перебрать все возможные комбинации элементов массива друг с другом?
Порядок элементов роли не играет, т.е. 123==213==321..
Вот пример для массива с 4-мя элементами:
1, 12, 13, 14, 123, 124, 134, 1234,
2, 23, 24, 234,
3, 34,
4
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Перебрать все возможные суммы элементов массива
Подскажите, пожалуйста, как перебрать все возможные суммы элементов массива. Допустим на вход.
Все возможные комбинации цифр в массиве
Доброго времени суток,у меня такой вопрос. функция принимает массив из целых чисел и его велечину.
Отобрать все возможные значения элементов исходного массива в новый
Итак. Есть массив, к примеру int a=. В нем есть элементы, значения которых.
27695 / 17314 / 3809
Регистрация: 24.12.2010
Сообщений: 38,979
Алгоритм перебора всех сочетаний из N по K на форуме неоднократно попадался. И даже встречались рабочие алгоритмы! Дальше вам остается этот алгоритм обернуть в цикл по K от 1 до N и — вуаля!
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Перебрать все возможные комбинации
Доброго времени суток. Столкнулся с такой задачей и не знаю, как подступится. Опишу своими.
Перебрать все возможные комбинации цифр
Помогите написать код, котрый будет выводить все числа, например, в троичной системе. Т. е. Нам.
Перебрать все возможные комбинации заданных символов
нужно программа, которая перебирает все возможные комбинации заданных символов,
Как перебрать все возможные комбинации из n объектов?
Доброго дня, пытаюсь написать программу которая бы перебрала все возможные комбинации из n объектов.
Перечислить комбинации элементов массива
Здраствуйте, помогите разбить массив, у меня есть массив ls = [51, 56, 58, 59, 61]. Нужно зделать [51,56,58], [51,56,59], [51,56,61], [51,58,59], [51, 58,61], [51,59,61], [56,58,59], [56,58,61], [56,59,61], [58,59,61].
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
комбинации элементов массива
всем привет! коллеги, очень нужна помощь. есть массив с точками place_id: $array = ;
Комбинации всех возможных элементов массива
Добрый день форумчане. Есть такая задачка, как реализовать комбинацию всех возможных элементов.
Все возможные комбинации элементов массива
добрый день уважаемые форумчанин! помогите с моим вопросом! надо комбинировать элементы.
Все комбинации элементов массива с учетом ключей
Что то сегодня голова не дает идеи. Может у вас есть готовый кусочек кода, а то мне надо побыстрее.
Найти все возможные комбинации по n элементов массива
задание есть массив из k елементов, нужно найти все возможные комбинации по n элементов этого.
6175 / 3410 / 1026
Регистрация: 07.09.2019
Сообщений: 5,457
Здравствуйте.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
function foo(arr, length) { const combinations = []; if (length == 1) { combinations.push(. arr.map((el) => [el])); } else { for (let i = 0; i arr.length; i++) { combinations.push( . foo(arr.slice(i + 1), length - 1).map((array) => [arr[i], . array]) ); } } return combinations; } const ls = [51, 56, 58, 59, 61]; console.log(foo(ls, 3));
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Вывод всех возможных комбинации элементов массива
Дан массив из n элементов вывести все возможные комбинации элементов массива
Комбинации произведений элементов массива без повторений
Здравствуйте, мне нужно создать комбинацию произведений значений вектора без повторений. Например.
Перебрать все возможные комбинации элементов массива друг с другом
Такая задачка — есть одномерный массив, размер которого может изменяться. Как в цикле перебрать.
Перечислить перестановки из N элементов путем транспозиции смежных элементов с рекурсией и без нее
Перечислить перестановки из N элементов путем транспозиции смежных элементов с рекурсией и без нее.
Перечислить перестановки из N элементов путем транспозиции смежных элементов с рекурсией и без нее
Перечислить перестановки из N элементов путем транспозиции смежных элементов с рекурсией и без нее.
Мощь алгоритмов: автоматический поиск всех возможных комбинаций
Это история об информатике, алгоритмах и понимании мощи компьютеров.
Представим такую ситуацию: компания по продаже компьютеров хочет написать самую эффективную рассылку для своих клиентов. Маркетологи сказали, что в письме обязательно должно быть 4 блока:
- предложение скидки;
- анонс новых товаров;
- блок с самыми популярными товарами;
- рассказ о том, почему нужно выбрать именно эту компанию.
Но никто не знал, в каком порядке лучше всего расположить эти блоки, чтобы рассылка сработала максимально круто. В итоге решили перебрать все комбинации и отправить много разных рассылок. Для этого позвали программиста, который написал для них простой скрипт — он выводит все варианты расположения блоков. Сегодня мы попробуем это повторить.
О чём речь
В математике это называется перестановками без повторений: мы просто перебираем все разные варианты, в каком порядке могут идти элементы. В нашем случае может быть так:
- Скидка → анонс → популярное → рассказ
- Рассказ → скидка → анонс → популярное
- Анонс → рассказ → скидка → популярное
Таких вариантов можно составить 4! («четыре факториал») — то есть 24 штуки. Восклицательный знак означает факториал, то есть нам нужно перемножить все числа от 1 до этого числа:
4! = 1 × 2 × 3 × 4 = 24
Получается, из четырёх блоков можно сделать 24 разных варианта письма. Вручную перебирать их все сложно, да и нет смысла: компьютер с этим справится гораздо быстрее. Для этого и сделаем алгоритм.
В чём идея
Чтобы перебрать все варианты, можно сделать так:
- Смотрим, сколько у нас блоков — 4 штуки.
- Делаем первый цикл.
- Делаем второй цикл.
- Делаем третий цикл.
- Делаем четвёртый вложенный цикл.
- Внутри этого перебираем все варианты и каждый раз проверяем, чтобы один блок не встречался два раза или больше.
- Если условие выполняется — добавляем результат в итоговые варианты
- На выходе получаем все варианты.
Но это сложно: нам нужно заводить для каждого цикла свою переменную, а потом следить, чтобы они не перепутались между собой. А ещё нужно не забыть:
- про проверку на дубли;
- собирание всех последовательностей в какой-то новый массив;
- новые вложенные циклы и увеличение сложности условия, если блоков станет больше.
А можно подойти к вопросу иначе:
- Берём массив с блоками.
- Берём оттуда первый элемент, откладываем его в сторону и дальше пока работаем с оставшимся массивом.
- В оставшемся массиве тоже берём первый элемент, откладываем его в сторону и снова работаем с оставшимся массивом.
- Так погружаемся в массив до тех пор, пока в нём не останется ни одного элемента.
- А теперь на каждом этапе возврата назад мы переставляем наш отложенный первый элемент на соседнее место и запоминаем получившуюся комбинацию.
- Так на каждом шаге мы будем получать всё новые и новые комбинации перестановок — сначала это будут перестановки из двух элементов, потом из трёх и так далее.
- Возвращаемся к пункту 2 и делаем то же самое со вторым элементом.
- Так проходим все элементы до последнего.
Обратите внимание, что у нас получился только один цикл, который перебирает по очереди все элементы массива. А вот внутри этого цикла и происходит вся магия: мы погружаемся всё глубже и глубже по одним и тем же правилам, а потом начинаем собирать результаты с конца.
На самом деле мы только что описали рекурсию: функцию, которая вызывает сама себя, но на каждом шаге с новыми условиями.
Почему рекурсия лучше вложенных циклов
Когда вложенных циклов мало, то с ними проще: можно контролировать всё вручную. А вот когда циклов становится не три, а 10 или 50, то сильно вырастает вероятность ошибиться в переменной или забыть про какое-то условие. В рекурсии такой проблемы нет: мы один раз описываем, как нырнуть и как оттуда вынырнуть, и всё, остальное компьютер сделает сам.
Ещё бывает такое, что мы заранее не знаем, сколько будет блоков для перестановок — 4 или 40, например. Рекурсия здесь тоже выигрывает: достаточно в одном цикле перебрать все элементы массива, а дальше всё сработает само.
Алгоритм
Единственное, что нам понадобится нового для рекурсии, о чём мы ещё не говорили, — это мемоизация.
В программировании мемоизацией называют временное хранение промежуточных результатов вычислений, чтобы не вычислять их по сто раз. Один раз посчитал, добавил в переменную-кеш — и отлично.
В нашем случае за это будет отвечать такая строчка:
Она появляется в самом начале рекурсии и означает вот что:
- Если в переменной memo уже что-то было — используется то, что было.
- Если на момент запуска рекурсии в этой переменной ничего не было — создаётся пустой массив.
Так мы избавляемся от необходимости высчитывать промежуточные последовательности заново, а вместо этого используем временное хранилище.
Теперь смотрите код и читайте комментарии:
var email = ['скидка', 'анонс', 'популярное', 'рассказ']; // массив для результатов перестановок var results = []; // рекурсивная функция // на вход получает текущий массив и массив с памятью предыдущих вычислений function permute(arr, memo) < // переменная для хранения фрагмента массива var cur; // делаем переменную для хранения промежуточных результатов // в программировании это называется «мемоизация» var memo = memo || []; // какой размер входного массива — такой длины и делаем цикл, чтобы перебрать все элементы for (var i = 0; i < arr.length; i++) < // получаем новый массив cur, удаляя из входного массива один элемент, начиная с текущей позиции // при этом из входного массива этот элемент тоже удалится cur = arr.splice(i, 1); // если от входного массива ничего не осталось if (arr.length === 0) < // то приклеиваем текущее значение нарезки к варианту, который лежит в памяти, // и добавляем получившийся результат в итоговый массив results.push(memo.concat(cur)); >// вызываем новый виток рекурсии // в качестве аргументов передаём копию входящего массива и добавляем к кешу памяти то, что получилось после удаления одного символа из входящего массива permute(arr.slice(), memo.concat(cur)); // возвращаем в исходный массив первый элемент из нового массива, но уже на другую позицию arr.splice(i, 0, cur[0]); > // возвращаем обратно массив с результатами перестановок return results; > permute(email);Запустим код в консоли браузера:
Видно, что мы получили 24 перестановки, как и должно было быть. Они все разные, ни в одной нет повторений — то, что нам нужно. Теперь можно отдать эти последовательности дальше, чтобы по каждой из них собрали своё письмо для клиентов.
Если интересно, как рекурсия справится со сложными вариантами и сколько их получится, — сделайте в исходном массиве в коде не 4, а 10 элементов.
Что дальше
Попробуем использовать этот же подход в задаче коммивояжёра — там тоже есть много вложенных циклов. Должно сработать.