ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
7 сообщений из 7, страница 1 из 1
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
    #37647248
an0nym
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
an0nym
Участник
Есть ли какой-нибудь оптимальный метод генерации i-ого сочетания (из, допустим, миллиардов сочетаний) k из n элементов с ограничениями вида:
- некоторые элементы могут участвовать в сочетании только вместе с определенными другими элементами,
- некоторые элементы не могу участвовать в сочетании с определенными другими элементами?
...
Рейтинг: 0 / 0
04.02.2012, 21:45
| Ответить | Цитировать | Написать  
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
    #37647288
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Динамическое программирование.
...
Рейтинг: 0 / 0
04.02.2012, 22:40
| Ответить | Цитировать | Написать  
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
    #37647295
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Да, и почитайте лекции по ДП и посмотрите 11812543 , где есть ссылки на первоначальные книги...
...
Рейтинг: 0 / 0
04.02.2012, 22:49
| Ответить | Цитировать | Написать  
Оптимальная генерация лексикографически i-ого сочетания k из n элементов с ограничениями
    #37647337
an0nym
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
an0nym
Участник
AndreTM,

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

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

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


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