1 | |
Распечатать все перестановки из N цифр16.05.2016, 16:44. Показов 2543. Ответов 17
Метки нет (Все метки)
Задача такая. Допустим для простоты дано 5 цифр.
Причем цифры могут быть и одинаковые, например 77777 Требуется распечатать все перестановки из этих цифр. (В приведенном примере только одна перестановка 77777) Решение. Для числа 5 это конечно можно решить. Всего максимум 5! = 120 вариантов. Можно перебрать все варианты и в случае с равными цифрами просто выбросить лишнее. Может существует алгоритм, который не создает "лишние" перестановки? Ну рекурсивный что-ли? В общем не знаю. Буду рад любым предложениям на сей счет.
0
|
16.05.2016, 16:44 | |
Ответы с готовыми решениями:
17
Найти все возможные перестановки цифр Распечатать все перестановки используя рекурсию (2) Распечатать все перестановки используя рекурсию Вывести все возможные перестановки N заданных цифр, формируя при этом последовательность из K цифр |
Модератор
3079 / 2228 / 462
Регистрация: 26.03.2015
Сообщений: 8,647
|
|||||||||||
16.05.2016, 17:46 | 2 | ||||||||||
Для начала напишем простую перестановку (все элементы разные):
Функция allpos elem list добавляет elem в list на каждую из позиций (то есть, возвращает список списков). Например, allpos 'a' "bc" вернёт ["abc","bac","bca"] Если у нас возможны одинаковые элементы, то нужно elem вставлять только на позиции впереди любого другого элемента с таким же значением. Например, allpos2 'a' "bac" вернёт ["abac","baac"] Сама функция perm остаётся такой же, только allpos заменяем на allpos2:
1
|
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
|
||||||
16.05.2016, 18:02 | 3 | |||||
Пример на Js
или я не правильно понял суть задачи
0
|
16.05.2016, 18:11 [ТС] | 4 |
Shamil1
Спасибо! Однако мудрёно очень! Не могли бы Вы привести ваши рассуждения на простом примере, скажем 1122? Добавлено через 4 минуты Poznakomlus Это же перестановки! Для пяти элементов не может быть более 5!=120 вариантов. Вот простой пример (для пяти цифр) 11117 11171 11711 17111 71111 Все! Иного не дано!
0
|
Модератор
3079 / 2228 / 462
Регистрация: 26.03.2015
Сообщений: 8,647
|
|
16.05.2016, 18:46 | 5 |
Сообщение было отмечено echs как решение
Решение
Начинаем с конца.
1. Последняя цифра '2' Все перестановки числа "2": ["2"]. (всего одна перестановка) 2. Следующая цифра '2'. Во все числа из п.1 (их - одно) добавляем цифру '2' на все позиции... с одним запретом: нельзя ставить нашу цифру '2' правее цифры '2', если в числе встретится цифра '2'. Все варианты добавления цифры '2' к числу "2": ["22"] Объединяем все списки: ["22"] 3. Следующая цифра '1'. Во все числа из п.2 (их - одно) добавляем цифру '1' на все позиции... с одним запретом: нельзя ставить нашу цифру '1' правее цифры '1', если в числе встретится цифра '1'. Все варианты добавления цифры '1' к числу "22": ["122", "212", "221"] Объединяем все списки: ["122", "212", "221"] 4. Следующая цифра '1'. Во все числа из п.3 (их - три) добавляем цифру '1' на все позиции... с одним запретом: нельзя ставить нашу цифру '1' правее цифры '1', если в числе встретится цифра '1'. Все варианты добавления цифры '1' к числу "122": ["1122"] Все варианты добавления цифры '1' к числу "212": ["1212","2112"] Все варианты добавления цифры '1' к числу "221": ["1221","2121","2211"] Объединяем все списки: ["1122","1212","2112","1221","2121","2211"]
2
|
16.05.2016, 18:49 [ТС] | 6 |
Shamil1
Я тут подумал вот о чем. Пусть дано число 11355 Нельзя ли так организовать перестановку цифр, чтобы это число каждый раз увеличивалось до максимума 55311. И тем самым избежать повторений? Добавлено через 2 минуты Shamil1 Вы гений! Спасибо!
0
|
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
|
|
16.05.2016, 21:04 | 7 |
это у вас 5^5 получилось, видимо вы посчитали количество Размещений с возвращениями, т.е. учитывали, что каждой цифры ограниченное количество
geh, можно смотреть на набор чисел 11355 как на набор 3-х видов элементов (единицы, тройки, пятёрки), причем единиц и пятёрок по 2 и одна тройка И используем рекурсивный алгоритм 1. Цикл: выбираем один из имеющихся видов, количество которых ещё не кончилось 1.1. ставим выбранное число в текущую позицию 1.2. если позиция последняя, выводим новую комбинацию и выходим из цикла (других свободных чисел у нас не будет) 1.3. иначе уменьшаем количество чисел выбранного вида 1.4. переходим на новый уровень рекурсии, выполняя этот алгоритм с увеличенной на единицу позицией 1.5. возвращаем количество чисел выбранного вида и продолжаем цикл
0
|
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
|
||||||
16.05.2016, 22:08 | 8 | |||||
здесь длина 5, а цифр - 2 (1,7)
неудачный пример. так как достаточно пройти циклом по 5 массивам и заменить одну позицию
0
|
Модератор
3079 / 2228 / 462
Регистрация: 26.03.2015
Сообщений: 8,647
|
|
17.05.2016, 00:23 | 9 |
нужен код, который будет работать и для двух и для пяти цифр, а не только для двух
Добавлено через 2 минуты как выбираем?
0
|
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
|
||||||
17.05.2016, 01:28 | 10 | |||||
вариант, прямой перебор
0
|
Модератор
3079 / 2228 / 462
Регистрация: 26.03.2015
Сообщений: 8,647
|
|
17.05.2016, 01:34 | 11 |
0
|
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
|
|
17.05.2016, 01:42 | 12 |
[1,2,3,4,4] так ничего же не мешает данную операцию с индексами проводить
0
|
Модератор
3079 / 2228 / 462
Регистрация: 26.03.2015
Сообщений: 8,647
|
|
17.05.2016, 01:58 | 13 |
1
|
17.05.2016, 08:44 [ТС] | 14 |
Shamil1
Я нашел еще один довольно забавный алгоритм решения этой задачи. Пример 13335. Надо это число (в цикле) увеличивать на 1 до 53331. И проверять есть ли в этом числе заданные цифры. Конечно это не практично, но алгоритм очень простой. Он существует. И я считаю своим долгом поделиться им с вами. Может он еще Вам пригодиться! Добавлено через 3 минуты Shamil1 Этот алгоритм можно усовершенствовать, если использовать только заданные цифры...
0
|
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
|
|
17.05.2016, 09:15 | 15 |
0
|
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
|
||||||
17.05.2016, 16:57 | 16 | |||||
Вариант решения Js
0
|
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
|
||||||
18.05.2016, 01:10 | 18 | |||||
Вариант решения Php
алгоритм таков берем массив, создаем таблицу количества оригинальных символов массива далее делаем этот массив уникальным создаем массив из этих уникальных массивов и нашей длиной запускаем reduce функцию в ней два for в результате фильтруем, чтоб не добавить одинаковых символов сверяясь с таблицой table Объяснил как смог
1
|
18.05.2016, 01:10 | |
18.05.2016, 01:10 | |
Помогаю со студенческими работами здесь
18
Получить все перестановки из цифр 1, 2, 3, 4 Получить все перестановки из цифр 1, 2, 3, 4 Среди цифр введенной строки распечатать ту, которая появлялась чаще других. Если таких цифр было несколько, распечатать ту, что встречалась первой Вывести все варианты перестановки цифр числа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи | |||||
Что такое хорошо и что такое плохо, вид сбоку. Индивид и общество - грань не нарушения.
Hrethgir 18.01.2025
В моей личной жизни и времени, я рассуждаю категорией "хуже-лучше", в том плане, когда меня спросили например - "а зачем ты делаешь свой процессор?", то я ответил - "чтобы сделать свою жизнь лучше". . .
|
Передача по ссылке или по значению в Java?
InfoMaster 18.01.2025
В мире программирования на Java одним из ключевых аспектов, требующих глубокого понимания, является механизм передачи параметров в методы. Этот фундаментальный концепт часто становится источником. . .
|
Тернарный условный оператор в Python
InfoMaster 18.01.2025
В мире программирования существует множество инструментов и конструкций, позволяющих создавать эффективный и лаконичный код. Одним из таких инструментов является тернарный условный оператор, который. . .
|
Как удалить неотслеживаемые файлы из рабочего дерева Git
InfoMaster 18.01.2025
В процессе разработки программного обеспечения с использованием системы контроля версий Git часто возникает необходимость в управлении неотслеживаемыми файлами. Неотслеживаемые файлы (untracked. . .
|
Что делает код if __name__ == "__main__": в Python
InfoMaster 18.01.2025
В мире программирования на Python существует множество важных концепций, и одной из наиболее интересных является конструкция if __name__ == "__main__". Эта специальная конструкция играет ключевую. . .
|
Как заставить Git забыть об отслеживаемом файле, добавленном в .gitignore
InfoMaster 18.01.2025
В мире разработки программного обеспечения система контроля версий Git стала неотъемлемой частью рабочего процесса, позволяя эффективно отслеживать изменения в коде и управлять ими. Однако. . .
|
Что означает use strict в JavaScript и для чего используется
InfoMaster 18.01.2025
В мире современной веб-разработки JavaScript играет ключевую роль как один из основных языков программирования. По мере его эволюции возникла необходимость в механизмах, которые помогли бы. . .
|
Как работать со скрытыми (hidden) элементами в jQuery
InfoMaster 18.01.2025
В современной веб-разработке управление видимостью элементов на странице является одним из ключевых аспектов создания интерактивных пользовательских интерфейсов. jQuery предоставляет мощный набор. . .
|
Как переключаться между ветками (Branch) с помощью checkout в Git
InfoMaster 18.01.2025
Ветки в Git являются одной из ключевых концепций для управления версионностью кода, позволяя разработчикам эффективно работать в команде и параллельно развивать программные проекты. Каждый новый. . .
|
Что такое стек и куча, чем они отличаются и где находятся
InfoMaster 18.01.2025
Понимание основных концепций памяти в программировании
В мире современного программирования эффективное управление памятью играет ключевую роль в создании производительных и надежных приложений. . . .
|
Как использовать комментарии в JSON
InfoMaster 18.01.2025
JSON (JavaScript Object Notation) представляет собой легкий и широко используемый формат обмена данными, который стал стандартом де-факто для веб-приложений и программных интерфейсов. При работе с. . .
|
Как заставить git pull перезаписать локальные файлы в Git
InfoMaster 18.01.2025
Проблема перезаписи локальных файлов в Git
При работе с системой контроля версий Git разработчики часто сталкиваются с ситуацией, когда необходимо синхронизировать локальный репозиторий с. . .
|