Bemutató - kombinatorika
Permutációk Adjunk egy n elemet. Ezen elemek rendelését permutációnak nevezik. Néha "n elemből" adnak hozzá. Általában egy, alapvető vagy természetes rendelést, amit triviális permutációnak neveznek, különválasztják. Az A készlet elemei maguk nem érdekelnek. Gyakran az elemek egész számokként 1-től n-ig vagy 0-tól n-1-ig kerülnek. Az n elemek permutációinak halmazát Pn-vel jelöljük. és a hatalma Pn-n keresztül. Mindhárom kérdést megkérdezzük: mi a Pn, hogyan rendezzük el a Pn elemeit? hogyan kell újraszámozni őket.
A permutációk számának tétele Az n elemek permutációinak száma egyenlő n-vel! - a számok terméke 1-től n-ig. (n! olvassa az n-faktort). Indukcióval. N = 1 esetén a képlet nyilvánvalóan igaz. Tegyük fel, hogy az n-1-re igaz, bizonyítjuk, hogy n-re igaz. Az első rendelési elem n módon választható, a többi pedig hozzárendelhető a kiválasztott első elemhez. Ezért a Pn = Pn-1 n képlet tartja. Ha Pn-1 = (n-1). akkor Pn = n!
Számozás permutációk felsorolni azokat a permutációk, meg fog jelenni egy csomó Pn kölcsönösen egyetlen másik set Tn, amely bevezeti a számozás sokkal könnyebb lesz, majd minden elem p Pn mint a számok, hogy egy számát a kép Tn. TN készlet közvetlen terméke több numerikus intervallumok Tn = (0: (n-1)) (0 :. (N-2) ... Azaz, mindegyik elem TN gyűjteménye nemnegatív számok i1, i2, ..., in- 1, in, ik nk.
Kijelző Mi egy permutációt veszünk és egy triviális permutációt írunk mellé. Az első indexként az első elem helyét (nullától számítva) helyezzük el a triviális permutációban. A triviális permutáció helyett írjuk meg a maradék szimbólumok karaktersorát. A második indexként vegyük át a második permutációs elemet ebben a sorban. Ismételje meg a folyamatot a végéig. Nyilvánvaló, hogy a k-es index kisebb lesz a k-sor hosszánál, és az utolsó index nulla lesz. Lássuk ezt a folyamatot egy példának.
Minta 0 1 2 3 4 5 6 Index cadfgbeabcdefg 2 2 adfgbeabdefg 0 2 0 dfgbebdefg 1 2 0 1 fgbebefg 2 2 0 1 2 gbebeg 2 2 0 1 2 2 bebe 0 2 0 1 2 2 0 ee 0 2 0 1 2 2 0 0 nyilvánvaló, hogy ez a folyamat visszafordítható, és az inverz leképezés építeni egy sor indexek kezdeti permutáció.
A készlet Tn számozása A rendezett készletek bármely közvetlen terméke változó bázisú számrendszer lehet. Ne felejtsd el a példát az első előadás másodpercével, vagy vegye figyelembe a régi méretméretet: 1 udvar = 3 láb, 1 láb = 12 hüvelyk, 1 hüvelyk = 12 vonal, 1 vonal = 6 pont. (2, 0, 4, 2, 3) = 2 méter 0 láb 4 hüvelyk 2 sor 3 pont, hány ilyen elem van? Meg kell számolni (ez a Horner áramkör) ((2 3 + 0) 12 + 4) 12 + 2) 6 + 3
A számozás a készlet Tn - 2 Formula # hogy találja szoba egy sor indexek i1, i2, ..., in-1, az azt szívesebben írnak formájában visszatérő kifejezések # (i1, i2, ..., in) = a (i1, i2, ... , in-1, n-1); egy (I1, I2, ..., ik, k) = a (i1, i2, ..., ik-1, k-1) (n-k + 1) + ik; a (üres, 0) = 0; E szerint a képlet # (2,0,1,2,2,0,0) = a (2,0,1,2,2,0,6). Van egy (2,1) = 2; a (2,0,2) = 2 6 + 0 = 12; a (2,0,1,3) = 12 5 + 1 = 61; a (2,0,1,2,4) = 4 + 2 61 = 246; a (2,0,1,2,2,5) = 3 246 + 2 = 740; a (2,0,1,2,2,0,6) = 740 2 + 0 = 1480;
Indexkészletek felsorolása A fentiekből kiindulva könnyű átrendezni a permutaciókat: meg kell haladnod az összes készletből származó indexkészleteket a megfelelő permutáció létrehozásához. Az indexkészletek felsorolásához jegyezzük meg, hogy gyakorlatilag minden készlet egy számot tartalmaz egy speciális számrendszerben, változó bázissal (a rendszert faktorikusnak nevezik). Az ebben a rendszerben 1 hozzáadásának szabályai szinte ugyanolyan egyszerűek, mint a bináris: az utolsó számjegyről való áttérés esetén próbálj meg hozzáadni az aktuális számjegyet 1. Ha lehetséges, akkor add 1 megállítani. Ha ez nem lehetséges, írjon nullára, és menjen a következő számjegyre.
Példa: 7 6 5 4 3 2 1 Ezek alapváltozók 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Vegyük észre, hogy 3 4 4 2 2 1 0 minden sor kezdete 3 4 4 3 0 0 0 ugyanaz, mint az előző, 3 4 4 3 0 1 0 akkor az elem megy, szigorúan 3 4 4 3 1 0 0 nagyobb. és a 3 4 4 3 1 1 0 nem lényeges. 3 4 4 3 2 0 0 Így minden sor 3 4 4 3 2 1 0 leksikográfiásán nagyobb mint 3 5 0 0 0 0 0 előző. 3 5 0 0 0 1 0
Tézis a permutációk lexicográfiai keresésére Az algoritmus itt leírja a permutációkat a lexikográfiai növekedés sorrendjében. Bizonyítás. Elég bizonyítani, hogy ha két I1 és I2 indikátora van, és I1 leksikográfiásan megelőzi az I2-et, akkor a permutáció (I1) leksikográfiásan megelőzi (I2). Ezek a permutációk egymás után keletkeznek, és eddig I1 és I2 egybeesik, permutációik is egybeesnek. És egy nagyobb elem megfelel az index nagyobb értékének.
Közvetlen algoritmus lexikográfiai válogató permutációk Tekintsünk permutáció p és közvetlenül megtalálja a lexikografikusan következő. Kezdjük az elejét - az első elemeket. Kiterjesztései közül ismeretes a minimális, amelyben minden elem növekvő sorrendben van elrendezve, és a legmagasabb, ahol leereszkednek. Például, a permutációs p = (4, 2, 1, 7, 3, 6, 5) az összes továbbra is (4, 2, 1) ezek között (3, 5, 6, 7) és a (7, 6, 5, 3). A meglévő bővítmény kisebb, mint a maximális, és a harmadik elem nem módosítható. És a negyedik is. És az ötödiket meg kell változtatni. Ehhez a fennmaradó elemek közül a következőnek kell megtennie a sorrendet, be kell állítani az ötödiket, és minimális folytatást kell adni. Kiderül (4, 2, 1, 7, 5, 3, 6).
Permutációk lexikografikus keresésének közvetlen algoritmusa - 2 A következő több permutációt írjuk le. (4, 2, 1, 7, 5, 3, 6) (4,2,1,7,5,6,3) (4,2,1,7,6,5,3) (4, 2, 3, 1, 5, 7, 6) (4, 2, 3, 1, 6, 5, 7) (4, 2, 3, 1, (4, 2, 3, 1, 7, 6, 5) (4, 2, 3, 5, 1, 6, 7)
Az algoritmus formális leírása Munkaállapot: Permutation p és Boolean isActive. Kezdeti állapot: Triviális permutáció van írva és isActive = True. Standard lépés: Ha az isActive, kiadja a permutációt. A végétõl kiindulva találja meg a permutációban a legnagyobb monoton szempontból csökkenő utótagot. Legyen k az utótag előtt. Put isActive: = (k gt; 0). Ha az isActive, akkor keresse meg az utótag legkisebb elemét, amely meghaladja a pk-t, cserélje ki a pk-val, majd a "flip" utótagot.
Egy másik algoritmus a permutációk számozásához Most próbáljuk átrendezni a permutációkat, hogy két egymást követő permutáció kevésbé különbözzen egymástól. Milyen kevés? Egy elemi átültetéshez, amelyben két szomszédos elem kerül egymásra. Lehetséges? Megmutatjuk egy ilyen algoritmus alapszerkezetét, érdekelni fogjuk. Képzeld el az n-1 elemi "mechanizmusokat", amelyek mindegyike mozgatja elemét a készleten belül. Minden egyes lépésnél a mechanizmus balra vagy jobbra történő elmozdulást tesz lehetővé. Az irány megváltozik, amikor az elem eléri a szélét. Az irányt egy lépéssel cserélik le, amely alatt a lépést a következő mechanizmus végzi, amely azonban megváltoztathatja az irányt.
Egy másik algoritmus a permutációk számozásához. 2 Lássunk egy példát. 1 2 3 4 May, amelyek játéka 1 2 3 4 5 soron a b c d e a c d a b e a b a c d e a c d b a e a b c d e a c d b e a b b c d a e a c d e b a a b c d e a b c d e a b a c b d e a a c d a e B A C B D A E A C A d e b A C B A d e a a c d e b c c A B D E a a d c e b a a c b d e b d a c e b a a c d b e a d c egy e B A C A D B E a d c e a b a
Permutációk felsorolása. 1 függvény ExistsNextPerm (var kCh: egész): Boolean; var iV, iP, iVC, iPC: egész szám; kezdő eredmény: = hamis; iV: = nV lefelé 2-ig, ha számlálás [iV] lt; iV-1 majd indítsa el az Inc (szám [iV]); iP: = pos [iV]; iPC: = iP + dir [iV]; iVC: = perm [iPC]; perm [iP]: = iVC; perm [iPC]: = iV; pos [iVC]: = iP; pos [iV]: = iPC; kCh: = iP; ha dir [iV] lt; 0, majd Dec (kCh); eredmény: = Igaz; exit; end else kezd számolni [iV]: = 0; dir [iV]: = - dir [iV]; végén; végén;
A páronkénti termékek minimális összegének problémája Nézzünk két n számot, mondjuk, és. Ezek a számok párokra oszlanak (ak, bk), és kiszámítják k 1: n akbk páros termékek összegét. Módosíthatja a számozást és. Olyan számozást kell választania, amelynél az összeg minimális. Ebben a problémában rögzíthet néhány számozást, és keressen egy permutációt. amelyhez a legkisebb összegű k 1: n akb (k) értéket elérjük. A számokat a növekvő sorrendben, csökkenő sorrendben rendezzük.
A páros termékek összegének minimális tétele A páros termékek összegének minimális értéke triviális permutációval érhető el. Bizonyítás. Tegyük fel, hogy létezik két k és r indexe, hogy ak lt; ar és bk lt; br. Ebben az esetben (ar ak) (br bk) gt; 0, azaz. ar br + ak bk gt; ar bk + ak br. Számozásunk növekvő sorrendben történik. Ha nem növekvő sorrendben vannak, akkor van egy pár k és r, amint fent említettük. Ez a pár bk és br. csökkentjük az összeg értékét. Ezért az optimális megoldásban növekvő sorrendben vannak. Ez az egyszerű tétel a jövőben többször is előfordul.
A maximális növekedési algoritmus problémája Az n hosszúságú szekvenciák sorrendje. Meg kell találni a legnagyobb hosszúságú sorozatot, amelyben a számok növekvő sorrendben mennek. Például a 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9 sorokban a maximális 2, 11, 14, 16, 37, 41 Permutációval ez a probléma annak a ténynek köszönhető, hogy az eredeti szekvencia permutáció lehet. Csak arra fogunk koncentrálni, hogy megmutassuk, hogyan oldják meg ezt a feladatot, és formalizálják és igazolják az algoritmust a hallgatóknak.
Megtalálni a maximális növekvő alszekvencia Mi lehetséges gazdaságosan, hogy szét a csökkenő sorrendben (példa változott) 9 12 11 14 18 16 6 17 15 13 37 19 21 8 7 5 9 6 5 12 11 8 7 14 13 18 16 15 17 37 19 21 Minden a következő számot a legfelső sorra írja, ahol nem sérti a sorrendet. Vessük a számot az alsó sorból, 21. Miért van a 8. sorban? Ez megakadályozza a 19. számú 19 17. és megakadályozza, 16. t. D. Sequence 9, 11, 14, 16, 17, 19, 21 nő, és a hossza 7. Bármely szekvenciája nagyobb hosszúságú tartalmaz két szám egyetlen vonal ( Dirichlet-elv), és nem növelhető.
Az inversziók minimális számának problémája Az n hosszúságú sorszámot adjuk meg. Az inverzió azt mondják, hogy fut a helyszínen tükörképe annak bármely részsztring - szilárd podposledovatelnosti.Trebuetsya a minimális számú visszaírása elhelyezni elemek sorozatából növekvő sorrendben. Például a permutáció „szilárd” így konvertálni (piros betűkkel átrendeződött nagy már a helyükön vannak) Szilárd sploanShYa naolPSShYa AnolPSShYa AnlOPSShYa ALNOPSSHYA (öt inverzió)
Vizsgálati kérdések. A keresés és a számozás. A skaláris termék minimális problémája. A legnagyobb növekvő algoritmus problémája.
1. feladat: Kétirányú átmeneti permutációs szám 2. Keresse meg a permutációt, ami egy adott számú lépés. 3. Permutációk felsorolása elemi átvitelekkel. 4. Tegyen példát a skalár termék minimalizálására.