Random kombinációi
számítási komplexitás
Ez végrehajtása szükségessé k működését szorzás és osztás. Azaz, a számítási komplexitás O (k).
Az algoritmus gyorsabb, de ez már bizonyos hátrányai. Még a kis n ez túlcsordul egész, mert n szoroz a binomiális együttható, amely kellően nagy szám. Így, ha egész szám - egy előjel nélküli egészszám, amely négy bájt, a túlcsordulás következik be akkor is, ha n = 50, és k = 8.
Random kombinációi véletlen permutáció módszer
Az első algoritmus leírjuk, egészen egyszerű és nyilvánvaló.
Az ötlet az algoritmus a következő. Vegyük a objektumok listáját n elemek G = (g1. G2. ... gn). Ez lesz a sor, amiből épít a pályára. A kombinációs H K n lesz az úgynevezett sor n bit, ahol pontosan k egységek. Egység a i-edik helyen azt jelenti, hogy ez a kombináció magában foglalja gi elem. Így például a H egyenlő lehet H „= (1, ... 1, 0, ... 0), ahol az első k elemei az egységek, a többi - nulla. Ezután a véletlenszerű kombinációja a H - egy véletlen permutációja H „vonalon.
Az STL van random_shuffle () függvény. amely létrehoz egy véletlenszerű permutáció.
Az első függvény egy véletlenszám-generátor alapértelmezés szerint, a második -, mint a paraméter. RandomNumberGenerator - funkcionális egység, amely megkapja paraméterként száma n-típusú működtetésének megfelelő eredmény Last First és visszatér a véletlen szám r: 0≤r A végrehajtás az algoritmus nagyon egyszerű, hiszen ez alapján a generáció egy véletlen permutáció - algoritmus, amely már készen végrehajtását. Ez az algoritmus végrehajtása számos funkciót. Itt vannak. RandomFunc - funkcionális egység, amely a hívás RandomFunc (Max) visszaad egy véletlenszámot x származó 0≤x tartományban Funkciók úgynevezett RandomCombination () metódus generáló véletlenszerű kombinációja véletlenszerű változások ebben a formában „részhalmaza”. N paramétert (amennyiben rendelkezésre áll) - ez a mérete az eredeti készlet, k - méret a generált ezek kombinációi. RandomAccessIterator - bejáró közvetlen elérésű segítségével ez a típus paraméter határozza meg a bemeneti sorozat. OutputIterator - iterátort O, amelyben van rögzítve az eredmény. InputIterator - bemeneti bejáró. Az első két ilyen funkció, hogy a bemeneti sorozat véletlenszerű hozzáférés iterátorokat. Idejéhez kiszámítása a kifejezést std :: távolság (első, utolsó). Tulajdonképpen ezen végződik felhasználásukat a véletlen hozzáférésű iterátorokat. Ha a bejáró nem biztosított bejáró véletlen hozzáférésű, akkor lehetséges, hogy a funkciók, amelyek elfogadják n paraméter - bemenet hossza szekvencia. Egyébként ezek a funkciók ugyanazok. Nagyon fontos, hogy továbbítja RandomFunc funkcionális egység a linkre, nem utolsósorban azért, mert a legtöbb véletlenszám-generátor a saját belső állapotát. Így, ha a forrás generátort a funkciót, másolás és nem továbbítja a linket két hívás RandomCombination () sor vezethet ugyanazt az eredményt. Az alábbiakban bemutatjuk a végrehajtását az itt ismertetett funkciókat. Az ötlet az algoritmus, hogy valahogy felsorolni valamennyi kombinációját n k, hogy kerül levelezést és minden szám i tartományban 0≤i Tehát először meghatározzuk egy rendezést a sor kombinációk n a k. Az egyértelműség kedvéért rögzítjük kombinációja ebben a formában „listáját bool». A hozzáállás a lexikográfiai sorrendben. Az egyértelműség érdekében intézkedik, például minden kombinációja 7-3, ebben a sorrendben. Ha jobban megnézed ezeket a kombinációkat a saját érdekében könnyen nyomon a rekurzív sorozat. Tekintsük első elem kombinációja. Először is minden kombinációja, amelyben 0, akkor - az összes, amelyben egyenlő 1. Továbbá, a sorrendben a kombináció mindkét alcsoportban megismételjük - az egyes alcsoportokban először kombináció, amelyben a második elem - 0, majd - amelyben ez egyenlő 1, stb A kombinációk száma, amelyekben az első elem a nullával egyenlő, egyenlő a kombinációk száma az n-1-k, és a kombinációk száma, amelyekben az első elem egyenlő eggyel, egyenlő a kombinációk száma az n-1-k-1 (a válasz a kérdésre, hogy miért ez történik ez a lábjegyzet a második tulajdonság binomiális együttható). Így, ha a kombináció a száma kisebb, mint a kombinációk száma az n-1-k, akkor az első elemet a készlet nem tartalmazza ezt a kombinációt, különben - tartalmazza. Összefoglalva, mi jön a következő algoritmus. Bemenet. CombNumber - szám kombináció, n, k - több bemeneti felbontását és méretét kombinációk, Src - bemeneti beállított (szekvenciát), amely kombináció választott, Dest - több kimeneti, amelyben a kombináció lesz írva az algoritmus. Nyomot. kombináció rögzített Cél. Ez algoritmus nagyrészt kiszámításához binomiális együttható, így a hatékonysága attól függ, hogy a hatékonyság számításához a binomiális együttható. A maximális iterációk száma n (minimum - k). Ezen túlmenően, a K hozzárendelés műveleteket. Vannak még kisebb műveleteket, mint a növekmény és kivonva egészek. Ők is nem több, mint n. Tegyük fel, hogy az első algoritmus leírt a cikkben (további memória) használunk az algoritmus kiszámításához a binomiális együttható. Az idő, komplexitás O (nk), ha a kívánt értéket a C (n, k) nem számítjuk, amíg a hívás, és az O (1), ha az már a gyorsítótárban. Ezután a kiszámítása C (n, k), az algoritmus alapján, az összes többi szükséges értékek kiszámítása, mint a binomiális együttható. Ez azt jelenti, sőt, ki kell számítani a binomiális együttható csak egyszer, minden további hívásokat az értékeket kiolvassuk a cache. Így, az idő összetettsége a teljes véletlenszerű kombinációja kiválasztási algoritmus O (nk), ha a gyorsítótár üres, és O (n), ha tele van a kívánt velünk binomiális együtthatók. Ami a jövőt illeti, azt mondjuk, hogy a jelenléte töltött cache ismertetett algoritmus hatékonyabb, mint a kombinált algoritmus generál véletlen permutáció módszer. Azaz, ha az ébred többször (például legalább 5-10 alkalommal), akkor kap a teljesítmény növekedés (töltelék fizet cache). Ha szükséges generálni csak egy kombináció, akkor természetesen jobban használható algoritmus generál egy véletlenszerű kombinációja véletlen permutáció módszer. Kapcsolódó funkciók ez az algoritmus, egy csomó, de nem kell félni - ezek mind azonos típusú. A paraméterek GetBinomialCoefficient, RandomFunc, n, k, Src, cél, első, utolsó típusok RandomAccessIterator, InputIterator, OutputIterator átfedésben ugyanezen korlátozásoknak és követelményeknek, és hogy a megvalósító függvények egy véletlen permutáció algoritmussal módszer. Paraméter CombNumber (ha van) meg kell felelniük a feltételt 0≤CombNumber≤C (n, k) - a sorozatszáma kombinációja. Funkciók úgynevezett CombinationFromNumberBool () létrehoz egy kombinációja egy előre meghatározott számú „formátumú listát bool». A bejáratnál szolgált kombinációja száma, mérete, esetleg egy függvény objektum, amely kiszámítja a kombinációk száma (ha nem, akkor így az alapértelmezés). A kilépés, akkor meg kell írni a Cél elemsorozatával szintaktikailag kompatibilisek bool (ami lehet rendelni egy bool). Funkciók úgynevezett CombinationFromNumber () létrehoz egy kombinációja egy előre meghatározott számú ebben a formában „részhalmaza”. A bemeneti kapnak azonos, és hogy CombinationFromNumberBool (), és iterator (iterátorok) leírja a bemeneti sorozat. A kilépés, kell alkotniuk a kívánt alszekvencia (más szóval ezek kombinációja), és mentse el a Cél. RandomCombinationFromNumberBool funkció nevek () és RandomCombinationFromNumber () generál véletlen kombinációja formátumok listája”bool» és »részhalmaza«, ill. A bemeneti, hogy ugyanazokat a paramétereket, mint a megfelelő funkciókat előtag nélkül «Véletlen», kivéve a beállítás RandomFunc, amelyet át helyette CombNumber. Ok a megfelelő funkció (előtag nélkül «Random») paraméterrel az CombNumber = RandomFunc (GetBinomialCoefficient (n, k)). Az alábbiakban bemutatjuk a végrehajtását az itt ismertetett funkciókat. Megvalósított funkciók használatához szemantika iterátorokat STL, ezért azokat fel lehet használni, amely egyaránt, mint egy hagyományos tömb, és konténerek C ++ Standard Template Library, sőt egyéni adattípusok. A legjobb, hogy hívja különböző változatai funkciók mutatunk be a következő kis programot. Demo.cpp fájlt a program letölthető a link végén. Az algoritmus generál véletlenszerű kombinációja ebben a formában „részhalmaza” metódus létrehoz egy véletlenszerű permutációs vektor Algoritmus generál egy kombinációja a szám önmagában nem használja a memóriát. De használ GetBinomialCoefficient () függvény, amely (egy megvalósítás GetBinomialCoefficient algoritmus) használ O (nk) bájt memóriát cache együttható értékeket. Mint már korábban említettük, a teljesítmény és az algoritmusok különböző körülmények között különböző. Hogy bemutassák a relatív teljesítményét megvalósított algoritmusok, írj egy egyszerű programot. Itt CTimer - egy osztály a mérési idő. A kód itt elhagyjuk rövidség kedvéért. 1 - egy egyszerű időmérés algoritmus RandomCombination (). 2 - a mérése a futási ideje az algoritmus RandomCombinationFromNumber () azzal a feltétellel, hogy a cache binomiális együttható értéke üres. Mint később látni fogjuk, ezen feltétel mellett munkája során elfogadhatatlan. 3 - a mérése a futási ideje az algoritmus RandomCombinationFromNumber () azzal a feltétellel, hogy a gyorsítótár megtelik binomiális együttható értékeket. 4. készül összehasonlítására az időben a két algoritmus valós körülmények között. Összesen leírásban RandomCombinationFromNumber () függvény azonos számú alkalommal a RandomCombination (a) az első példa, de a cache binomiális együttható értéke visszaáll minden 25 hívásokat. Ez a következtetés a program a processzor Core 2 Duo E7500. Ebből levonhatjuk az alábbi következtetéseket. Így, ha n = 500, és k = 275 alkalmazni RandomCombinationFromNumber (), akkor fizetni is szempontjából végrehajtási ideje a hívás C, ahol C<25. Если n и k меньше, то C также уменьшается. Например, для n=250 и k=135 RandomCombinationFromNumber() окупается уже за C<12 вызовов. Эти данные, разумеется, справедливы лишь для целых 32-битных чисел. В общем случае мы имеем объекты некоторых классов, которые, возможно, копируются медленнее. Тогда C может уменьшиться ещё больше. Tegyük fel, van néhány előre ismert és változatlan szekvencia elemek n hosszúságú. Akárhogyan is, nem számít, hogy mit választottunk szekvenciarésznek ezt a sorozatot, amelyben az elemek nem ismétlődik. k-val jelölt hosszúsága. Nyilvánvaló, az említett alszekvencia a kombinációk n k. Következésképpen, lehetséges, hogy létrehoz a korábban leírt generáló algoritmus kombinációja sorszám kombinációk. Mivel az algoritmus determinisztikus, alszekvencia teljesen határozza meg a kezdeti szekvencia és a kombináció száma. Összefoglalva, az algoritmus könnyen megvalósítható védelmi alszekvenciája. Ehhez mi hiányzik az egyik több funkció - NumberFromCombination (). Mentéséhez mix, meg kell írni egy fájlt csak a paramétereket k és szám kombinációk. Így például, fenntartására egy lista a K 32-bites számok, mentjük 8 4k bájtos összesen 8 bájt rögzítési helyett 4k (természetesen, azzal a megkötéssel, hogy k és n elég kicsi ahhoz, hogy a kombináció nem haladja meg a 2-es szám 32 -1) . Az alábbiakban bemutatjuk a végrehajtás a bejelentett funkciókat. Két különböző megközelítések véletlenszerű kombinációi ismétlések nélkül tartják a cikkben leírt. Szintén adott teljesítmény összehasonlítása módszerek és tisztázni a körülményeket, amelyben meg kell, hogy egy bizonyos algoritmus. Megvalósult könyvtár lehetővé teszi a könnyen használható az algoritmusok minden, STL-kompatibilis konténerek és tömbök.Értékelés időbonyolultsága
végrehajtás
Működési leírás
forrás
Által generált kombinációja a szám
Értékelés időbonyolultsága
végrehajtás
Működési leírás
forrás
A megvalósított funkciók
Összehasonlítása két algoritmus
memória-felhasználás
termelékenység
Néhány hasznos tulajdonságai az algoritmus generál kombináció a száma
Kompakt tárolási kombinációk
következtetés
Kapcsolódó cikkek