Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями / 7 сообщений из 7, страница 1 из 1
04.02.2012, 21:45
    #37647248
an0nym
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
Есть ли какой-нибудь оптимальный метод генерации i-ого сочетания (из, допустим, миллиардов сочетаний) k из n элементов с ограничениями вида:
- некоторые элементы могут участвовать в сочетании только вместе с определенными другими элементами,
- некоторые элементы не могу участвовать в сочетании с определенными другими элементами?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.02.2012, 22:40
    #37647288
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
Динамическое программирование.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.02.2012, 22:49
    #37647295
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
Да, и почитайте лекции по ДП и посмотрите 11812543 , где есть ссылки на первоначальные книги...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.02.2012, 00:02
    #37647337
an0nym
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
AndreTM,

прошу простить за нетерпение, но вопрос до полного ознакомления с материалами по ссылке: там есть информация по генерации i-ого сочетания именно с ограничениями или только без оных? Как без оных сделать я уже более менее знаю. :(
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.02.2012, 00:12
    #37647342
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
А более полно сформулировать задачу? Дать её, так сказать, в исходном виде...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.02.2012, 00:28
    #37647351
an0nym
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
AndreTM,

не очень понимаю, чего недостаточно в исходном объяснении. Попробую объяснить с позиции графов вместо комбинаторных сочетаний, если чего-то не хватает, скажите.

Есть граф, каждая вершина которого соединена с минимум одной максимум всеми остальными вершинами. Необходимо любым способом пронумеровать все клики размера k и за O(1) найти i-ую.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.02.2012, 00:32
    #37647352
an0nym
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
an0nymНеобходимо любым способом пронумеровать все клики размера k и за O(1) найти i-ую.Необходимо любым способом пронумеровать все клики, не находя их, размера k и за O(1) найти i-ую.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями / 7 сообщений из 7, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 464ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1342465]:
 0ms
get settings:
 7ms
get forum list:
 13ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 163ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 24ms
get tp. blocked users:
 1ms
others: 243ms
total:  464ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]