2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Поиск минимума среди произведений перестановок
Сообщение07.01.2018, 11:19 
Аватара пользователя


11/08/11
1135
Есть некоторое множество перестановок заданной длины $a_1, a_2, ..., a_n$, и есть некая перестановка $b$. Считаем, что перестановка $x$ меньше перестановки $y$, если первые $k$ элементов в них совпадают, и элемент перестановки $x$ с номером $k+1$ меньше элемента перестановки $y$ с номером $k+1$ (ну то есть обычный лексикографический порядок). Можно ли найти наименьшую перестановку среди всех $a_1 b, a_2 b, ..., a_n b$ быстрее, чем выполнив все умножения и собственно найдя перебором из всех результатов?

 Профиль  
                  
 
 Re: Поиск минимума среди произведений перестановок
Сообщение07.01.2018, 11:40 
Заслуженный участник
Аватара пользователя


09/09/14
6328
INGELRII в сообщении #1281954 писал(а):
Можно ли найти наименьшую перестановку среди всех $a_1 b, a_2 b, ..., a_n b$ быстрее, чем выполнив все умножения и собственно найдя перебором из всех результатов?
Наверняка можно. Вот что сразу приходит в голову. Найдём первые элементы всех этих перестановок и отбросим лишние. Если заданные перестановки разные, то какая-то оптимизация гарантированно будет.

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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