2014 dxdy logo

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

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




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

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

 
 
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 01:03 
Аватара пользователя
Вы комбинациями называете перестановки?
Существует несколько. Например рекурсивный: пусть вы уже умеете генерировать все перестановки из $n - 1$ элемента, как из них сделать все перестановки $n$ элементов?
Или лексикографический: упорядочим все перестановки лексикографически. Какая будет минимальной? Какая будет следующей за ней? Как по перестановке найти следующую за ней?

 
 
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 01:10 
pogopogo в сообщении #1356643 писал(а):
Есть ли какие-то общие правила о том, как осуществлять перебор? Или эти правила надо придумывать?
Погуглите "генерация перестановок". В общем-то соответствующие алгоритмы относятся к числу базовых, которые рассказываются будущим программистам, так что их изложения встречаются очень часто.

 
 
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 15:16 
Pphantom
mihaild
Спасибо, прочёл.
Похожая тема, где говорится о том, что генерация перестановок очень затратный процесс.
Генерирование перестановок и реальность
https://dxdy.ru/topic88279.html

 
 
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 15:20 
Дык что б вы хотели для так быстро растущей функции? Для вашего примера из десяти элементов — совершенно не очень затратный.

 
 
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение25.11.2018, 15:39 
pogopogo в сообщении #1356730 писал(а):
Похожая тема, где говорится о том, что генерация перестановок очень затратный процесс.
Это не процесс затратный, это перестановок много. :-)

 
 
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение29.12.2018, 13:30 
Аватара пользователя
Когда-то я интересовался похожим вопросом. Ну, или хотя бы мой вопрос был из той же области. В книге Окулов - Программирование в алгоритмах есть ответы на большинство из них, поэтому рекомендую к прочтению.

 
 
 
 Re: Есть ли общий алгоритм перебора всех комбинаций?
Сообщение29.12.2018, 13:43 
B@R5uk в сообщении #1364485 писал(а):
В книге Окулов - Программирование в алгоритмах есть ответы на большинство из них, поэтому рекомендую к прочтению.


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

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group