сложността на изчисленията
Тази реализация изисква к операции на умножение и деление. Това означава, че неговата изчислителна сложност е O (к).
Алгоритъмът е по-бързо, но има някои недостатъци. Дори и най-малката п тя прелива числа, защото н умножава по коефициент биномно, който е достатъчно голям брой. Така, ако цяло число - неподписан число, състояща се от четири байта, преливникът настъпва дори когато п = 50 и к = 8.
Генериране на случайни комбинации на случаен метод пермутация
Първият алгоритъм, който описваме е съвсем проста и очевидна.
Идеята на алгоритъма е следната. Вземете списъка с обекти от наш елементи G = (g1. G2. ... GN). Това ще бъде нашата поредица, от която ще се изгражда комбинация. Комбинация от Н к с п ще се нарича низ от п бита, където точно к единици. Отдел в I-то място означава, че тази комбинация включва GI елемент. Например, Н може да бъде равно Н '= (1, ... 1, 0, ... 0), където първите к елементи на единици, а останалата част - нула. Тогава случайна комбинация от Н - е случайни пермутации на линия H ".
В STL има random_shuffle (функция). който генерира случайни пермутации.
Първата функция използва генератор на случайни числа по подразбиране, а вторият - като параметър. RandomNumberGenerator - функционална единица, която получава като параметър на броя на п-тип, съответстващ на резултата от операцията последната На първо място, и връща случайно число R: 0≤r Изпълнението на алгоритъма е съвсем проста, тъй като се основава на генериране на случайни пермутации - алгоритъм, който вече има готов изпълнение. Този алгоритъм за прилагане на няколко функции. Ето кои са те. RandomFunc - функционална единица, че обаждането RandomFunc (Max) връща случайно число х от 0≤x гама Функции наречени RandomCombination () метод за генериране на произволна комбинация от случайни промени във формата на "подгрупа". Параметърът п (където е налице) - това е размерът на първоначалния комплект, К - размера на генерираните техни комбинации. RandomAccessIterator - итератор с произволен достъп, като се използва този тип параметър определя вход последователност. OutputIterator - итератор О, в която се записва резултата. InputIterator - вход итератор. Първите две от тези функции вземе входната последователност с помощта на случайни итератори за достъп. дължина й се изчислява с помощта на станд :: разстоянието изразяване (първа, последна). Всъщност, по този въпрос и завършва с тяхното използване като случаен итератори за достъп. Ако итератора не е предвидено итератор с произволен достъп, е възможно да се използват функциите, които приемат параметър N - дължината на входната последователност. В противен случай, всички тези функции са едни и същи. Много е важно да се предават RandomFunc функционална единица на линка, и не на последно място, защото по-голямата част от генератори на случайни числа използва своето вътрешно състояние. По този начин, ако генератора източник на функцията, копиране и не предава връзка с две повиквания RandomCombination () на ред може да доведе до същия резултат. Следните показва изпълнение на функциите, описани тук. Идеята на алгоритъма е по някакъв начин да се изброят всички комбинации от п на к, който се поставя в съответствие с всеки брой и в 0≤i диапазона Така че, първо ние определяме подреждането на снимачната площадка на комбинации от п на к. За по-голяма яснота, ние ще запише една комбинация в "списъка с формат на булев». Нашата нагласа е лексикографски ред. За яснота организира, например, всички комбинации от 7 до 3 са в тази последователност. Ако се вгледате внимателно в тези комбинации в реда им лесно се проследи връзката рецидив. Помислете за първите комбинации елемент. Първо са всички комбинации, в които е 0, тогава - всички в които е равно на 1. Освен това, редът на комбинация от тези две подгрупи се повтаря - във всяка подгрупа са първо комбинация, при която вторият елемент - 0, и след това - при което то е равно на 1, и т.н. Броят на комбинации, в които първият елемент е равна на нула, равен на броя на комбинациите от п-1 до К, и броя на комбинации, в които първият елемент е равна на един, равен на броя на комбинациите от п-1 до К-1 (отговорът на въпроса защо това се случи Тя е описана в бележка под линия към втория имота биномен коефициент). Така, ако комбинацията от броя малък от броя на комбинациите от п-1 до к, тогава първият елемент на комплекта не е включена в тази комбинация, в противен случай - е включена. В обобщение, ние стигаме до следния алгоритъм. Input. CombNumber - брой комбинация, п, к - множество вход резолюция и комбинации размер, Src - вход избран (последователност), която комбинация е избран, Цел - множество изход, в който комбинацията ще бъде написана от алгоритъма. Imprint. комбинация записва в Цел. Този алгоритъм използва до голяма степен изчисляване на биномно коефициент, така че неговата ефективност зависи от ефективността на изчисляване на коефициента биномиално. Максималният брой повторения е N (минимум - к). В допълнение, при използване на операции за присвояване к. Има и малки операции като нарастване и изваждане числа. Те също са не повече от п. Да приемем, че първият алгоритъм, описан в статията (като се използва допълнителна памет) се използва като алгоритъм за изчисляване на коефициента биномно. Нейното време е сложност O (НК), ако е необходимо стойността С (н, к) не се изчислява, докато повикването, и O (1), ако то вече е в кеша. След изчисляване на С (п к), на базата на алгоритъм, всички други необходими стойности се изчисляват като биномно коефициент. Това е, в действителност, е необходимо да се изчисли коефициентът биномиално само веднъж, всички следващи разговори към стойностите са извлечени от кеша. По този начин, сложността време на целия случаен алгоритъм комбинация подбор е O (НК), ако кеша е празна, и O (N), ако тя е пълна с нас желаните двучленни коефициентите. Гледайки напред, ние казваме, че присъствието попълнено кеш описан алгоритъм е по-ефективен от комбинация алгоритъм генерира произволен метод пермутация. Това означава, че ако тя се позовава на няколко пъти (например, поне 5-10 пъти), можете да получите печалби за успешно представяне (пълнене плаща кеш). Ако е необходимо да се генерира само една комбинация, разбира се, е по-добре да се използва алгоритъм за генериране на произволна комбинация от метода на случайната пермутация. Функции, свързани с този алгоритъм, много, но не се страхувайте - всички те са от същия тип. На параметри GetBinomialCoefficient, RandomFunc, п, к, Src, Цел, първа, последна, видове RandomAccessIterator, InputIterator, OutputIterator припокриват същите тези ограничения и изисквания, както и с това, че функциите, които изпълняват произволен метод алгоритъм поколение пермутация. Параметър CombNumber (когато присъства) трябва да отговаря на състояние 0≤CombNumber≤C (п, к) - е сериен номер комбинация. Функции наречени CombinationFromNumberBool () генерират комбинация от предварително определен брой в "списъка с формат на булев». На входа те сервира комбинация от броя, размера, може би един обект функция, която изчислява броят на комбинациите (ако не, тогава, така е по подразбиране). На изхода, те трябва да бъдат написани на местоназначението от последователност от елементи е синтактично съвместим с булев (която можете да зададете булев). Функции наречени CombinationFromNumber () генерират комбинация от предварително определен брой под формата на "подгрупа". Входът те получават същата, и че CombinationFromNumberBool () и итератора (итератори) описва вход последователност. На изхода, те трябва да се образува желаната подпоследователност (с други думи, комбинация) и го запишете в Цел. имената на функциите RandomCombinationFromNumberBool () и RandomCombinationFromNumber () генериране на случайни комбинация от формати "списък на булев» и "подмножество", съответно. Входът да има същите параметри като съответните функции без префикс «Разни», с изключение на определянето RandomFunc, която се предава вместо CombNumber. Причина съответната функция (без префикс «Разни») с параметъра CombNumber = RandomFunc (GetBinomialCoefficient (п, к)). Следните показва изпълнение на функциите, описани тук. Реализирани функции използват семантиката итератори STL и следователно могат да бъдат използвани, което е еднакво като конвенционален масив, и контейнери C ++ стандарт шаблон библиотека, и дори с типове потребителски данни. Най-добре е да се обадите на различни версии на функциите може да се докаже с помощта на следната малка програма. Demo.cpp файл с програмата може да бъде изтеглен от линка в края. Алгоритъмът генерира произволна комбинация под формата на метод "подмножество" създава случайни пермутации вектор Алгоритъм за генериране на комбинация от себе си номера му не използва допълнителната памет. Но той използва функция GetBinomialCoefficient (), който (в едно изпълнение GetBinomialCoefficient алгоритъм) използва O (NK) байта памет за коефициент кеширане стойности. Както беше отбелязано по-рано, на изпълнението на алгоритмите при различни условия е различен. За да се покаже относителното представяне на реализирани алгоритми, напишете проста програма. Тук CTimer - клас за измерване на времето. Неговият код е пропуснато тук за краткост. 1 - е проста време алгоритъм измерване RandomCombination (). 2 - представлява измерване на времето за изпълнение на алгоритъма RandomCombinationFromNumber () при условие, че кеш двучленни стойностите на коефициента е празна. Както ще видим по-късно, при това състояние по време на работата му е неприемливо. 3 - е мярка за времето за изпълнение на алгоритъма RandomCombinationFromNumber () при условие, че на кеш паметта е пълна двучленни стойности на коефициента. 4 се прави за сравняване на времето на два алгоритъма в реални условия. Общо тук RandomCombinationFromNumber () се нарича същия брой пъти като RandomCombination () в първия пример, но кеш двучленни стойностите на коефициента е нулиран на всеки 25 повиквания. Това е заключението на програмата на процесор Core 2 Duo E7500. От това можем да се направят следните изводи. По този начин, ако п = 500 и 275 к = прилага RandomCombinationFromNumber (), тя ще плати за себе си от гледна точка на времето за изпълнение на повикване C където C<25. Если n и k меньше, то C также уменьшается. Например, для n=250 и k=135 RandomCombinationFromNumber() окупается уже за C<12 вызовов. Эти данные, разумеется, справедливы лишь для целых 32-битных чисел. В общем случае мы имеем объекты некоторых классов, которые, возможно, копируются медленнее. Тогда C может уменьшиться ещё больше. Да приемем, има някои предварително известни и неизменни последователност елементи с дължина п. В никакъв начин, без значение каква е избран последователност на тази последователност, в която елементи не се повтарят. обозначен с к дължината му. Очевидно е, споменатата последователност е една от комбинациите на п от к. Следователно е възможно да се генерират по-рано описан алгоритъм за генериране на комбинация от серийни комбинации цифри. Тъй като алгоритъм е детерминирана, последователност напълно определя от началната последователност и номера на комбинация. В обобщение, алгоритъмът може лесно да се реализира опазване последователност. За това, на нас ни липсва още една функция - NumberFromCombination (). За да запазите микс, ние трябва да пиша във файл само параметри к и брой комбинации. Така, например, поддържа списък на номерата на к 32-битови, ние спаси 8 4k байта общо запис 8 байта вместо 4k (разбира се, с уговорката, че к и п са достатъчно малки, така че композицията не надвишава броя 2 32 -1) , По-долу показва изпълнението на декларираните функции. Две различни подходи за генериране на произволни комбинации без повторение се считат в статията е описано. Също така дава сравнение на ефективността на методите и изяснени обстоятелствата, при които трябва да се използват определен алгоритъм. Реализирани библиотека ви позволява лесно да се използват алгоритмите за всички, STL-съвместим контейнери и масиви.Оценка сложност време
изпълнение
Описание на функциите
източник
Генериран от комбинацията на неговия номер
Оценка сложност време
изпълнение
Описание на функциите
източник
Използването на изпълнените функции
Сравнение на два алгоритъма
изразходването на паметта
продуктивност
Някои полезни свойства на алгоритъм, генериращи комбинация от неговия номер
Компактните комбинации съхранение
заключение
Свързани статии