2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 01:00 


08/01/18
9
Пример для наглядности:
У меня есть 10 элементов. Я хочу построить все возможные варианты последовательностей из этих 10 элементов. По комбинаторике это, вроде, формула $n!$ - т.е. $100! = 3628800$ комбинаций.

Есть ли какие-то общие правила о том, как осуществлять перебор? Или эти правила надо придумывать? Или генерировать случайную последовательность и проверять, была ли она уже?
А если даже проверять, то существует способ, как это сделать быстро, кроме как использование алгоритмов поиска и их вариаций?

 Профиль  
                  
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 01:03 
Заслуженный участник
Аватара пользователя


16/07/14
8334
Цюрих
Вы комбинациями называете перестановки?
Существует несколько. Например рекурсивный: пусть вы уже умеете генерировать все перестановки из $n - 1$ элемента, как из них сделать все перестановки $n$ элементов?
Или лексикографический: упорядочим все перестановки лексикографически. Какая будет минимальной? Какая будет следующей за ней? Как по перестановке найти следующую за ней?

 Профиль  
                  
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 01:10 
Заслуженный участник


09/05/12
25179
pogopogo в сообщении #1356643 писал(а):
Есть ли какие-то общие правила о том, как осуществлять перебор? Или эти правила надо придумывать?
Погуглите "генерация перестановок". В общем-то соответствующие алгоритмы относятся к числу базовых, которые рассказываются будущим программистам, так что их изложения встречаются очень часто.

 Профиль  
                  
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 15:16 


08/01/18
9
Pphantom
mihaild
Спасибо, прочёл.
Похожая тема, где говорится о том, что генерация перестановок очень затратный процесс.
Генерирование перестановок и реальность
https://dxdy.ru/topic88279.html

 Профиль  
                  
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 15:20 
Заслуженный участник


16/02/13
4105
Владивосток
Дык что б вы хотели для так быстро растущей функции? Для вашего примера из десяти элементов — совершенно не очень затратный.

 Профиль  
                  
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 15:39 
Заслуженный участник


09/05/12
25179
pogopogo в сообщении #1356730 писал(а):
Похожая тема, где говорится о том, что генерация перестановок очень затратный процесс.
Это не процесс затратный, это перестановок много. :-)

 Профиль  
                  
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение29.12.2018, 13:30 
Аватара пользователя


26/05/12
1534
приходит весна?
Когда-то я интересовался похожим вопросом. Ну, или хотя бы мой вопрос был из той же области. В книге Окулов - Программирование в алгоритмах есть ответы на большинство из них, поэтому рекомендую к прочтению.

 Профиль  
                  
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение29.12.2018, 13:43 


10/04/12
704
B@R5uk в сообщении #1364485 писал(а):
В книге Окулов - Программирование в алгоритмах есть ответы на большинство из них, поэтому рекомендую к прочтению.


Почему не четвёртый том TAoCP?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group