Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Как узнать индекс сочетания (комбинаторика), зная выбранное подмножество?  [new]
an0nym
Member

Откуда:
Сообщений: 7078
Существует ли какая-нибудь общая формула, чтобы узнать номер по порядку сочетания из всех возможных, зная, какие элементы множества использованы при построении данного сочетания, если построение идет упорядоченно от меньшего к большему? (ниже приведен код упорядоченного перебора всех сочетаний 5 элементов из 20 возможных - 20!/(5!*(20-5)!)=15504 шт.)

i=0;
for(a=0;a<20;++a){
	for(b=a+1;b<20;++b){
		for(c=b+1;c<20;++c){
			for(d=c+1;d<20;++d){
				for(e=d+1;e<20;++e){
					permutations[++i]={a,b,c,d,e};
				}
			}
		}
	}
}

Как, зная a, b, c, d и e для некоторого конкретного сочетания узнать, какое оно по счету (i), не делая перебор, как на примере выше?

Т. е., например, зная что a=0, b=1, c=2, d=3, e=4 узнать, что i=1, или зная, что a=15, b=16, c=17, d=18, e=19, узнать, что i=15504... и так для любого случая.
27 мар 09, 19:36    [6986730]     Ответить | Цитировать Сообщить модератору
 Re: Как узнать индекс сочетания (комбинаторика), зная выбранное подмножество?  [new]
an0nym
Member

Откуда:
Сообщений: 7078
Сам нашел ответ.
i=C(e,5)+C(d,4)+C(c,3)+C(b,2)+C(a,1), где C(n,r) - количество сочетаний для подмножества r элементов множества n элементов
27 мар 09, 21:53    [6987068]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить