Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Составить алгоритм генерации всех сочетаний 27.01.08 08:32 Число просмотров: 5937
Автор: Vedrus <Serokhvostov Anton> Статус: Member
|
Под «сочетаниями» понимается (Новиков. Дискретная математика для программистов):
1. Число строго монотонных функций, или число размещений n неразличимых предметов по m ящикам, не более чем по одному в ящик, то есть число способов выбрать из m ящиков n ящиков с предметами, называется числом сочетаний и обозначается C(m, n)
2. Число монотонных функций, или число размещений n неразличимых предметов по m ящикам, называется числом сочетаний с повторениями и обозначается V(m, n)
Может кто-нибудь мне разъяснить различие между двумя этими понятиями? Сколько голову не ломал, так и не нашёл.
Теперь к сути вопроса: есть массив из n элементов, элементы могут принимать значения либо 0, либо 1. Нужно найти все варианты заполнения этого массива единицами (общее число единиц = k < n). Алгоритм должен выполняться как можно более быстрее.
Мне это нужно для проведения экспериментов при поиске оптимальной стратегии в игре крестики-нолики.
Перебрал пять книжек по дискретной математике и комбинаторике, перелистал Кнута, но алгоритма так и не нашёл. Придумал я один алгоритм с кучей вложенных циклов, но в плане быстродействия он вообще никакой.
|
- Составить алгоритм генерации всех сочетаний - Vedrus 27.01.08 08:32 [5937]
|
|
|