Пример
// Комбинации от 3 от 52 за (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Комбиниран индекс
Всяка комбинация, пермутация, разположение и други комбинаторни обекти могат да бъдат свързани с индекс - това е числото, в което се появява при итерация през този алгоритъм.Тук ще разгледаме по-сложен проблем, чието решение не намерих в RuNet (обаче ще дам една връзка, но тази формула очевидно е неправилна) - въз основа на самата комбинация (в този случай набор от три числа) намерете неговия индекс.
Има опция за търсене "челно". Включваме брояча на комбинациите, вземаме горния алгоритъм и опитваме всичко, докато стигнем до желаната опция. Тази опция има много висока времева сложност, така че ще я отхвърлим.
Да приемем, че входът съдържа числа i1, i2, i3. На първо място, трябва да ги подредим във възходящ ред (имайте предвид, че самият алгоритъм за генериране, даден по-горе, винаги ги произвежда в подредена форма, въпреки че самата концепция за „комбинация“ предполага произволен ред).
Нека приемем, за определеност, след подреждане i1 = 3, i2 = 7, i3 = 12.
Това означава, че „преминахме“ през всички комбинации, където i1 беше равно на 0, 1 и 2.
За i1 = 0, преминахме през C(2, 51) комбинации, тъй като индексите i1, i2 преминават през всички комбинации от 2 от 51 числа.
За i1 = 1 преминахме през C(2, 50) комбинации.
За i1 = 2 преминахме през C(2, 49) комбинации.
Като цяло преминахме през SUM (от n = 0 до n = i1-1) C(2, 51-n).
За i1 = 3, нека разгледаме онези комбинации, през които минахме, докато преминавахме през индекс i2 (и за нас той започва с i2 = i1+1 = 4).
Когато i2 = 4, C(1, 47) комбинации преминаха, когато i2 = 5, C(1, 46) комбинации преминаха, когато i2 = 6, C(1, 45) комбинации преминаха.
По пълна аналогия, с i2 = 7, разглеждаме комбинациите, през които е преминал индексът i3.
Получаваме общата формула:
Индексът на необходимата комбинация = SUM (от n = 0 до i1-1) C(2, 51-n) + SUM (от n = i1+1 до i2-1) C(1, 51-n) + SUM (от n = i2+1 до i3-1) C (0, 51-n).
Индекс на подмножество
В комбинаториката има по-сложен обект - разделянето на подмножества. Например, разделяне на набор от 52 елемента на три подмножества от, да речем, съответно 2, 3 и 47 елемента, където редът на елементите във всяко подмножество е маловажен. (Между другото, комбинация от 2 от 52 е просто специален случайразделяне на две подмножества съответно от 2 и 50 елемента).Типичен алгоритъм за генериране е, че генерираме комбинации от 2 от 52 и за всяка такава комбинация във вложен цикъл генерираме комбинации от 3 от 50 и проверяваме дали индексите (i3, i4, i5) във вложената комбинация правят не съвпадат с индексите (i1, i2) във външна комбинация:
C++ код
// ВЪНШНА КОМБИНАЦИЯ for (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
Отново, всеки такъв дял има свой собствен индекс.
Оказва се, че нашият алгоритъм за намиране на индекса на комбинацията може да бъде модифициран, за да намери индекса на дяла.
Трябва да се отбележи, че трябва да подредим индексите във „външната комбинация“ i1, i2 помежду си, а индексите i3, i4, i5 помежду си, но независимо от първите два.
Трябва също така да се има предвид, че при „вложена комбинация“ по същество работим с набор от 50 елемента, но индексите i3, i4, i5 трябва да бъдат „изместени“ по определен начин, така че да не се променят от 0 до 51, но от 0 до 49:
C++ код
ако (i3 >= i1) --i3; ако (i3 >= i2) --i2; // подобно за i4, i5
(така да се каже, изрязваме индекси i1, i2 от нашия набор от 52 елемента и след това изместваме останалия набор, за да затворим дупките, докато индексите i3-i5 се изместват).
Трябва да се има предвид, че във всяка „външна“ комбинация имаме точно C(3, 50) „вложени“ комбинации.
Тогава алгоритъмът ще се сведе до следното:
COMBINATION_INDEX (i1, i2 от 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 от 50 след изместване на индекса).
Довеждане на алгоритмите до постоянна сложност
Веднага трябва да отбележа, че във формулата възниква „грешка“, ако например i1 = 0 (броим сумата за n = от 0 до -1) или i2 = 1 (броим сумата от 1 до 0). Всъщност в такива случаи трябва да се вземе подходящото количество равно на нула, и резултатът ще бъде правилен.Трябва също да обърна внимание на времевата сложност на нашите алгоритми: те имат линейна сложност, при условие че смятате C за постоянно време. Това вече е много по-добре от грубата сила.
Ама наистина (в нашия случай 52) нищо не ни пречи да намалим алгоритъма до постоянна сложност. За целта ще приложим познания по математика и ще изчислим аналитично всички суми.
Например броят на комбинациите C(2, K), ако го „разширите“ под формата на формула K! / ((K-2)! * 2!), редуцира до полином от 2-ра степен. И тъй като го имаме под знака за сума, можем да приложим формулите сумира Nстепени на числата в естествената серия (вижте Wikipedia) и да получите единичен полином от 3-та степен. Което очевидно има постоянна времева сложност. (Още повече, че „грешката“, която цитирах в началото на подзаглавието, не се проявява по никакъв начин; формулата остава правилна).
Повтарям, това за фиксиран размер на базовия комплект. Сигурен съм обаче, че с помощта на метапрограмирането можете да „научите“ компилатора, така че той да върши тази работа вместо вас.
Примерен код за разделен индекс на 2, 3, 47
int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Индекс на комбинацията от 2 от 52, умножена по C(3, 50) int offset = ((52*51 - ( 51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // „Преиндексиране“ на вътрешната група, така че номерирането да е 0...49, ако (i3 >= i1) --i3; (i3 >= i2) --i3; if (i4 >= i1) --i4; // Сега добавете индекса на комбинацията с 3: / / СУМА за n = 0 от i3-1 КОМБИНАЦИИ (2, 49-n) // = СУМА за m = 50-i3 от 49 (m * (m-1) / 2) отместване += (19600 - ((( 49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // СУМА за n = i3+1 до i4-1 КОМБИНАЦИИ (1, 49-n) отместване += (((48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // SUM за n = i4+1 от i5-1 (1) отместване += (i5 - i4 - 1);
Послеслов
В моя покер симулатор (Texas Hold'em) исках предварително да изчисля и запазя вероятностите за печалба за всички възможни комбинации от моите карти (2 части) и всички карти на флопа (3 карти на масата). наборът от 52 от 2, 3, 47 подмножества.Изчислено и запазено.
Но когато дойде време да прочета данни от файл за конкретна комбинация, наистина не исках да изчислявам нещо дълго време или да търся в гигабайтов файл. Сега просто определям отместването във файла и директно чета това, което ми трябва.
Като цяло бих разделил комбинаторните алгоритми на следните класове:
- Генериране на комбинаторни обекти в един цикъл (тук всичко е просто, дадох примери);
- Преминаване към следващия (или предишен) комбинаторен обект, познавайки предишния (вид итератор напред/назад, изразен в C++ термини) - тук можем да отбележим наръчник за обучение T.I. Fedoryaeva, където е даден алгоритъм с постоянна времева сложност за пермутации и други примери могат да бъдат намерени в RuNet, но само за пермутации - и би било интересно да се видят подобни алгоритми за други комбинаторни обекти;
- Намиране на индекса на обект. Изобщо няма примери, с изключение на ръководството на Федоряева, освен това с линейна сложност и само за пермутация;
- Намиране на обект по индекс.
Всички N елемента и нито един не се повтаря, тогава това е проблем за броя на пермутациите. Решението може да се намери просто. Първото място в реда може да бъде всеки от N елемента, следователно има N опции. На второ място - всяко, с изключение на това, което вече е използвано за първо място. Следователно за всяка от вече намерените N опции има (N - 1) опции за второ място и общият брой комбинации става N*(N - 1).
Същото може да се повтори и за останалите елементи от серията. За най последно мястоОстава само една опция - последният останал елемент. За предпоследния има два варианта и т.н.
Следователно, за серия от N неповтарящи се елемента, възможните пермутации са равни на произведението на всички цели числа от 1 до N. Това произведение се нарича факториел на N и се обозначава с N! (четете „en factorial“).
В предишния случай броят на възможните елементи и броят на местата в реда съвпадаха и техният брой беше равен на N. Но е възможна ситуация, когато в реда има по-малко места, отколкото има възможни елементи. С други думи, броят на елементите в извадката е равен на определено число M и M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Първо, може да се наложи да преброите общия брой възможни начини, по които M елемента от N могат да бъдат подредени в ред. Такива начини се наричат подреждане.
Второ, изследователят може да се интересува от броя на начините, по които M елементи могат да бъдат избрани от N. В този случай редът на елементите вече не е важен, но всеки два варианта трябва да се различават един от друг с поне един елемент . Такива методи се наричат комбинации.
За да намерите броя на разположенията на M елемента от N, можете да прибегнете до същия метод на разсъждение, както в случая с пермутациите. Все още може да има N елемента на първо място, N - 1 на второ място и т.н. Но за последното място количеството възможни вариантине е равно на единица, а на (N - M + 1), тъй като когато поставянето приключи, все още ще останат (N - M) неизползвани елементи.
Така броят на поставянията на M елемента от N е равен на произведението на всички цели числа от (N - M + 1) до N, или, което е същото, частното N!/(N - M)!.
Очевидно броят на комбинациите от M елемента от N ще бъде по-малък от броя на разположенията. За всяка възможна комбинация има М! възможни разположения, в зависимост от реда на елементите на тази комбинация. Следователно, за да намерите това количество, трябва да разделите броя на разположенията на M елемента от N на N!. С други думи, броят на комбинациите от M елемента от N е равен на N!/(M!*(N - M)!).
Брой комбинации
Комбинацияот пот кнаречен набор келементи, избрани от данни пелементи. Набори, които се различават само по реда на елементите (но не и по състава), се считат за идентични, поради което комбинациите се различават от разположенията.
Изрични формули
Брой комбинации от пот к равен на биномния коефициент
За фиксирана стойност пгенерираща функция на числа от комбинации с повторения от пот ке:
Двумерната генерираща функция на числа от комбинации с повторения е:
Връзки
- Р. СтенлиИзброителна комбинаторика. - М.: Мир, 1990.
- Изчислете броя на комбинациите онлайн
Фондация Уикимедия.
2010 г.
Вижте какво е „Брой комбинации“ в други речници:
70 седемдесет 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Факторизация: 2×5×7 Римска нотация: LXX Двоична система: 100 0110 ... Wikipedia Светло число, условно число, което еднозначно изразява външното условия по време на снимане (обикновено яркостта на обекта и фоточувствителността на използвания фотографски материал). Всяка стойност на E. h може да бъде избрана няколко пъти. номера на апертурата на комбинации... ...
Голям енциклопедичен политехнически речник Форма на число, която разграничава два обекта както по отношение на един обект, така и по отношение на много обекти. Тази форма не съществува в съвременния руски език, но остават остатъци от нейното влияние. И така, комбинации от две таблици (вж. множествено число... ...
Речник на лингвистичните термини Комбинаторна математика, комбинаторика, клон на математиката, посветен на решаването на проблеми с избора и подреждането на елементи от определено, обикновено ограничено, множество в съответствие с дадени правила. Всяко такова правило определя метода на изграждане... ...
В комбинаториката комбинация от by е набор от елементи, избрани от даден набор, съдържащ различни елементи. Комплекти, които се различават само по реда на елементите (но не и по състав), се считат за идентични, тези комбинации ... ... Wikipedia
Занимава се с изследване на събития, чието настъпване не е известно със сигурност. Позволява ни да преценим доколко е разумно да очакваме настъпването на някои събития в сравнение с други, въпреки че присвояването на числени стойности на вероятностите за събития често е ненужно... ... Енциклопедия на Collier
1) същото като математическия комбинаторен анализ. 2) Раздел от елементарната математика, свързан с изучаването на броя на комбинациите, при определени условия, които могат да бъдат съставени от даден краен набор от обекти... ... Голям Съветска енциклопедия
- (гръцки paradoxos неочакван, странен) в широк смисъл: твърдение, което рязко се отклонява от общоприетото, установено мнение, отричане на това, което изглежда „безусловно правилно“; в по-тесен смисъл, две противоположни твърдения, за... ... Философска енциклопедия
- (или принципът на включванията и изключванията) комбинаторна формула, която ви позволява да определите силата на обединението на краен брой крайни множества, които в общия случай могат да се пресичат помежду си ... Wikipedia
Математическа теория, занимаваща се с определяне на броя на различните начини за разпределяне на дадени обекти в известен ред; е особено важно в теорията на уравненията и теорията на вероятностите. Най-простите задачи от този вид са... ... Енциклопедичен речникЕ. Brockhaus и I.A. Ефрон
Книги
- учебник по английски език. В две части. Част 2, Н. А. Бонк, Г. А. Котий, Н. А. Лукянова. Книгата е втора част от „Учебник английски език". Състои се от 20 урока, справочник по граматика за урок по урок и справочни граматични таблици. Обемът на новия речник...
Помислете за проблема с преброяването на броя проби от даден набор общ изглед. Нека има някакъв набор Н, състоящ се от п елементи. Всяко подмножество, състоящо се от м елементи могат да се разглеждат, без да се взема предвид техният ред, или да се вземе предвид, т.е. при промяна на реда, преминете към друг м– вземане на проби.
Нека формулираме следните определения:
Разположения без повторение
Поставяне без повторение нап елементи отм Нсъдържащимразлични елементи.
От дефиницията следва, че двете подредби се различават една от друга, както по елементите, така и по реда си, дори ако елементите са еднакви.
Теорема 3. Броят на поставянията без повторение е равен на произведението м фактори, най-големият от които е числото п . Запишете:
Пермутации без повторение
Пермутации отп елементи се наричат различни подреждания на множествотоН.
От това определение следва, че двете пермутации се различават само по реда на елементите и могат да се разглеждат като частен случай на разположения.
Теорема 4. Броят на различните пермутации без повторение се изчислява по формулата
Комбинации без повторения
Комбинация без повторение нап елементи отм всяко неподредено подмножество на множество се извикваНсъдържащим различни елементи.
От дефиницията следва, че двете комбинации се различават само по елементи;
Теорема 5. Броят на комбинациите без повторения се изчислява по една от следните формули:
Пример 1. В стаята има 5 стола. По колко начина можете да ги поставите върху тях?
а) 7 души; б) 5 души; в) 3 души?
Решение:а) Първо, трябва да изберете 5 души от 7, които да седнат на столове. Може да се направи 
начин. С всеки избор на конкретна петица можете да произвеждате 
пренареждания. Според теоремата за умножение необходимият брой методи за кацане е равен.
коментар:Задачата може да се реши само с помощта на теоремата за произведението, като се разсъждава по следния начин: за сядане на 1-ви стол има 7 варианта, на 2-ри стол има 6 варианта, на 3-ти -5, на 4-ти -4 и на 5- та -3. Тогава броят на начините да настаните 7 души на 5 стола е . Решенията и по двата метода са последователни, тъй като
б) Решението е очевидно - 
V) 
- брой избори на заети столове.
- брой места за трима души на три избрани стола.
Общият брой на изборите е .
Не е трудно да проверите формулите 
;
;
Броят на всички подмножества на набор, състоящ се от пелементи.
Повторете разположенията
Чрез поставяне с повторение отп елементи отм всяко подредено подмножество на множество се извикваН, състоящ се отм елементи, така че всеки елемент може да бъде включен в това подмножество от 1 домпъти или изобщо да отсъстват от него.
Броят на поставянията с повторение е означен с 
и се изчислява по формулата, която е следствие от теоремата за умножение:
Пример 2. Нека N = (a, b, c) е набор от три букви. Нека наречем всеки набор от букви, включени в този набор, дума. Намерете броя на думите с дължина 2, които могат да бъдат съставени от тези букви: 
.
коментар:Очевидно поставянията с повторение също могат да бъдат взети предвид, когато 
.
Пример 3. Трябва да използвате буквите (a, b), за да създадете всички възможни думи с дължина 3. По колко начина може да се направи това?
отговор:
