Permutări Permiteți să se dea un set de elemente n. Ordonarea acestor elemente se numește o permutare. Uneori adaugă "din n elemente". De obicei, este o singură ordine, de bază sau naturală, care este numită permutare trivială. Elementele setului A nu ne interesează ele însele. Adesea, elementele sunt luate ca întregi de la 1 la n sau de la 0 la n-1. Denumim setul de permutări ale elementelor n de Pn. și puterea lui prin Pn. Solicităm toate aceleași trei întrebări: ce este Pn, cum să rezolve elementele lui Pn. cum să le renumiți.
Teorema privind numărul de permutări de numărul de permutări de n elemente este egal cu n! - produsul numerelor de la 1 la n. (n! citeste n-factorialul). Prin inducție. Pentru n = 1, formula este evident adevărată. Să presupunem că este adevărat pentru n-1, demonstrăm că este adevărat pentru n. Primul element de Streamline n poate fi ales prin metode bine la primul element selectat atribut metode se pot odihni. Prin urmare, formula Pn = Pn-1 n este valabilă. Dacă Pn-1 = (n-1). atunci Pn = n!
Numerotarea permutări de a enumera permutări, vom afișa o mulțime de Pn reciproc singur într-un alt set TN, care introduce numerotarea va fi mult mai ușor, și apoi pentru orice element p Pn ca numerele lui să ia o serie de imaginea sa în TN. Tn- set este un produs direct al mai multor intervale numerice Tn = (0: (n-1)) (0 :. (N-2) ... Aceasta înseamnă că fiecare element Tn- o colecție de numere nenegative i1, i2, ..., in- 1, în, cu ik nk.
Afișare Facem o permutare și scriem o permutare trivială lângă ea. Ca primul indice luam locul primului element (numarand de la zero) in permutarea triviala. Să scriem șirul de simboluri rămase în locul permutării triviale. Ca al doilea indice, să luăm locul celui de-al doilea element de permutare în acest rând. Repetați procesul până la sfârșit. Evident, indicele k va fi mai mic decât lungimea liniei k, iar ultimul indice va fi zero. Să vedem acest proces ca exemplu.
Proba 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 este evident că acest proces este reversibil, iar invers maparea pentru a construi pe un set de indici de permutare inițială.
Numerotarea setului Tn Orice produs direct al seturilor comandate poate fi considerat ca un sistem numeric cu o bază variabilă. Amintiți-vă exemplul cu secundele de la prima prelegere sau luați în considerare orice dimensiune veche de dimensiuni: 1 yard = 3 picioare, 1 picior = 12 cm, 1 inch = 12 linii, 1 linie = 6 puncte. (2, 0, 4, 2, 3) = 2 metri 0 picioare 4 inchi 2 linii 3 puncte, câte sunt aceste elemente? Este necesar să numărăm (acest lucru se numește circuitul Horner) (((2 3 + 0) 12 + 4) 12 + 2) 6 + 3
Numerotarea Tn set - 2 Formula # care își găsește loc pentru un set de indici i1, i2, ..., in-1, în, preferăm să scrie în formă de expresii recurente # (i1, i2, ..., in) = a (i1, i2, ... , în-1, n-1); un (i1, i2, ..., ik, k) = a (i1, i2, ..., ik-1, k-1) (n-k + 1) + ik; a (gol, 0) = 0; Conform acestei formule, # (2,0,1,2,2,0,0) = a (2,0,1,2,2,0,6). Avem o (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) = 61 4 + 2 = 246; a (2,0,1,2,2,5) = 246 3 + 2 = 740; a (2,0,1,2,2,0,6) = 740 2 + 0 = 1480;
Enumerarea seturilor de indici Urmând cele de mai sus, este ușor să sortați prin permutări: trebuie să treceți prin toate seturile de indexuri din și pentru fiecare set pentru a construi permutarea corespunzătoare. Pentru a enumera seturile de indexuri, rețineți că practic fiecare set este o înregistrare a unui număr dintr-un sistem cu numere speciale cu o bază variabilă (sistemul este numit factorial). Regulile pentru adăugarea 1 în acest sistem sunt aproape la fel de simple ca în binar: deplasând de la ultima cifră, încercați să adăugați cifra curentă 1. Dacă este posibil, adăugați 1 pentru a opri. Dacă nu este posibil, scrieți la zero și treceți la următoarea cifră.
Iterarea stabilește indici - 2 Să considerăm exemplul 7 6 5 4 3 2 1 Această bază variabilă 3 4 4 2 1 1 0 3 4 4 2 2 0 0 3 Rețineți că pornire 4 4 2 2 1 0 fiecare linie este 3 april 4 3 0 0 0 la fel ca în precedent, 3 4 4 3 0 1 0, atunci elementul vine strict 3 4 4 3 1 0 0 mai mare. și 3 4 4 3 1 1 0 nu este esențial. 3 4 4 3 2 0 0 De aceea, fiecare rând 3 4 4 3 2 1 0 lexicografic mai mari de 3 5 0 0 0 0 0 ultima. 3 5 0 0 0 1 0
Teoremă privind căutarea lexicografică a permutărilor Algoritmul descris aici sortează permutările în ordinea cresterii lexicografice. Dovada. Este suficient să arătăm că dacă avem două seturi de indici I1 și I2 și I1 precede lexicografic I2, atunci permutarea (I1) precede lexicografic (I2). Aceste permutări se formează secvențial, iar până în prezent I1 și I2 coincid, permutările lor coincid. Și un element mai mare corespunde unei valori mai mari a indicelui.
Algoritmul direct de căutare lexicografică a permutărilor Luăm câteva permutări p și le găsim direct lexicografic următoarele. Să luăm începutul - primele elemente k. Printre prelungirile sale, este cunoscută minimul, în care toate elementele sunt aranjate în ordine ascendentă și maximul în care acestea coboară. De exemplu, în permutarea p = (4, 2, 1, 7, 3, 6, 5), toate prelungirile pentru (4, 2, 1) se situează între (3,5,6,7) 3). Extensia existentă este mai mică decât maximul, iar al treilea element nu poate fi modificat. Și al patrulea. Și al cincilea trebuie schimbat. Pentru a face acest lucru, din restul elementelor, trebuie să luați alta în ordine, să o puneți pe a 5-a și să alocați o continuare minimă. Se pare (4, 2, 1, 7, 5, 3, 6).
Algoritmul direct al căutării lexicografice a permutărilor - 2 Se scriu următoarele permutări. (4, 2, 1, 7, 5, 3, 6) (4, 2, 1, 7, 5, 6, 3) (4, 2, 3, 1, 5, 7, 6) (4, 2, 3, 1, 6, 5, 7) (4, 2, 3, 1, 7, 5, 6) (4, 2, 3, 1, 7, 6, 5)
Descrierea oficială a algoritmului Starea de lucru: Permutarea p și Boolean isActive. Starea inițială: este scrisă o permutare trivială și isActive = True. Etapa standard: Dacă isActive, emite o permutare ca rezultat. Trecând de la capăt, găsiți în permutare cel mai mare sufix descrescător monotonic. Fie k poziția în fața sufixului. Punctul isActive: = (k gt; 0). Dacă esteActive, atunci găsiți cel mai mic element din sufix care depășește pk, schimbați-l cu pk și apoi sufixul "flip".
Un alt algoritm pentru enumerarea permutărilor Să încercăm acum să rearanjăm permutările astfel încât două permutări succesive să difere puțin una de cealaltă. Cât de puțin? Pentru o transpunere elementară, în care se schimbă două elemente adiacente. Este posibil? Arătăm schema de bază a unui astfel de algoritm, vom fi interesați de el. Imaginați-vă n-1 "mecanisme" elementare, fiecare dintre ele mutându-și elementul în set. La fiecare pas, mecanismul face o deplasare spre stânga sau spre dreapta. Direcția se schimbă când elementul atinge marginea. Direcția este înlocuită de o etapă, în care etapa este făcută de următorul mecanism, care, totuși, poate schimba direcția.
Un alt algoritm pentru enumerarea permutărilor -2 Să vedem un exemplu. 1 2 3 4 mai cui joacă 1 2 3 4 5 A cui rândul său, a b c d e a c d a b e b a c d e a c d b a e a b c a 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 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 a e b a c a d b e a d c e a b a
Enumerarea permutărilor. 1 funcția ExistsNextPerm (var kCh: integer): Boolean; var iV, iP, iVC, iPC: întreg; începe rezultatul: = False; pentru iV: = nV downto 2 face dacă numără [iV] lt; iV-1 începe apoi Inc (număr [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; dacă dir [iV] lt; 0 apoi Dec (kCh); rezultat: = Adevărat; ieșire; incepe sa incete sa numere [iV]: = 0; dir [iV]: = - dir [iV]; se încheie; se încheie;
Problema cu suma minimă a produselor pereche Fie două seturi de numere n, să zicem și. Aceste numere sunt împărțite în perechi (ak, bk) este calculată și suma produselor k 1 pereche: n akbk. Puteți schimba numerotarea și. Este necesar să se aleagă o astfel de numerotare, la care suma este minimă. În această problemă, puteți remedia unele numerotări și puteți căuta o permutare. pentru care se atinge minimul sumei k 1: n akb (k). Vom alege numerele atunci când sunt aranjate în ordine ascendentă și în ordine descrescătoare.
Teorema de suma minimă de produse Suma minimă a perechilor de produse a ajuns pe perechi permutarea trivial. Dovada. Să presupunem că există doi indici k și r astfel încât ak lt; ar și bk lt; br. În acest caz (ark) (br bk) gt; 0, adică ar br + ak bk gt; ar bk + ak br. În numerotarea noastră sunt aranjate în ordine ascendentă. Dacă nu sunt în ordine ascendentă, atunci există o pereche de k și r, după cum sa menționat mai sus. Rearanjarea acestei perechi de bk și br. noi reducem valoarea sumei. Prin urmare, în soluția optimă, ele sunt în ordine ascendentă. Această teoremă simplă se va întâlni de mai multe ori în viitor.
Problema unei subsecvente maximale crescătoare O secvență de numere de lungime n este dată. Este necesar să se găsească succesiunea sa de cea mai mare lungime, în care numerele ar merge în ordine crescătoare. De exemplu, în secvența 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9, maximul va subsequence 2, 11, 14, 16, 17, 25, 37, 41 Cu permutări, această problemă se datorează faptului că secvența inițială poate fi o permutare. Ne limităm pe noi înșine pentru a arăta modul în care se rezolvă această problemă, iar formalizarea și justificarea algoritmului va da ascultătorilor.
Găsirea subsecventa maximă în creștere Ne este economic posibil să împartă noastre descrescătoare secvenței (exemplul modificat) 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 Fiecare numărul următor este scris în partea superioară a liniilor, în cazul în care acesta nu va perturba ordinea. Ia numărul de linii de fund, 21. De ce este necesar pentru linia 8-a? Acesta previne 19. Un număr de 19 17. previne 16. t. D. Sequence 9, 11, 14, 16, 17, 19, 21 crește, și are o lungime 7. Orice secvență de lungime mai mare cuprinde două numere ale unei singure linii ( principiul Dirichlet) și poate fi în creștere.
Problema numărului minim de inversiuni sunt date o secvență de numere de lungime n. Inversiunea este declarat a fi difuzate pe imaginea în oglindă la fața locului a oricărei subsirului sale - solide podposledovatelnosti.Trebuetsya pentru numărul minim de reluări pentru a plasa elemente ale unei secvențe în ordine crescătoare. De exemplu, permutarea de „solide“, astfel încât să puteți converti (litere roșii rearanjate mari sunt deja) Solid sploanShYa naolPSShYa AnolPSShYa AnlOPSShYa ALNOPSSHYA (cinci inversiuni)
Întrebări de examinare. Căutarea și numerotarea lor. Problema minimului unui produs scalar. Problema celei mai mari subsecvente în creștere.
Sarcina 1. Numărul de permutare în tranziție în două sensuri 2. Găsiți permutarea, care este un număr dat de pași. 3. Enumerarea permutărilor prin transpoziții elementare. 4. Executați un exemplu pentru problema minimizării produsului scalar.
Articole similare
Trimiteți-le prietenilor: