M ASARYKOVA UNIVERZITA FAKULTA INFORMATIKY
Knihovna kombinatorických funkcí ˇ B AKALÁ RSKÁ PRÁCE
Jiˇrí Smejkal
Brno, jaro 2010
Prohlášení Prohlašuji, že tato bakaláˇrská práce je mým puvodním ˚ autorským dílem, které jsem vypracoval samostatnˇe. Všechny zdroje, prameny a literaturu, které jsem pˇri vypracování používal nebo z nich cˇ erpal, v práci rˇ ádnˇe cituji s uvedením úplného odkazu na pˇríslušný zdroj.
Vedoucí práce: RNDr. Aleš Zlámal ii
Podˇekování Na tomto místˇe bych rád podˇekoval vedoucímu této práce panu RNDr. Aleši Zlámalovi za vstˇrícnost a trpˇelivost. Dále pak mé rodinˇe za podporu ve studiu a všem, kteˇrí se se mnou podílili o své rady a zkušenosti.
iii
Klíˇcová slova funkce, knihovna, kombinatorika, permutace, variace, kombinace, jazyk C
iv
Shrnutí Cílem bakaláˇrské práce je vytvoˇrit kombinatorickou knihovnu pro programovací jazyk C, jejíž funkce mohou sloužit k programování problému˚ kombinatorické povahy.
v
Obsah 1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2 Konvence pro pojmenování funkcí v jazyce C . . . . . . . . . . . . . . . . . . . . .
2
2.1
Popis problematiky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.2
Analýza stávajícího systému pojmenování funkcí . . . . . . . . . . . . . . . .
3
2.2.1
Trigonometrické funkce . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2.2
Exponenciální a logaritmické funkce . . . . . . . . . . . . . . . . . . . .
4
2.2.3
Aritmetické funkce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
Tvorba názvu˚ funkcí pro kombinatorickou knihovnu . . . . . . . . . . . . . .
5
2.3.1
Tvoˇrení názvu˚ podle funkcionality . . . . . . . . . . . . . . . . . . . . .
5
2.3.2
Zkratky pro typy parametru˚ a návratové hodnoty . . . . . . . . . . . .
5
2.3.3
Zpusob ˚ rˇ azení zkratek za sebe . . . . . . . . . . . . . . . . . . . . . . .
6
3 Funkce kombinatorické knihovny . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3
3.1
3.2
Permutace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.1.1
Alokace permutace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.1.2
Délka permutace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.1.3
Inicializace permutace typu int . . . . . . . . . . . . . . . . . . . . . . .
12
3.1.4
Inicializace permutace typu char . . . . . . . . . . . . . . . . . . . . . .
12
3.1.5
Typ permutace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.1.6
Tisk permutace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.1.7
Tisk permutace na standardní výstup . . . . . . . . . . . . . . . . . . .
15
3.1.8
Tisk permutace do proudu . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.1.9
Generování následující permutace . . . . . . . . . . . . . . . . . . . . .
17
3.1.10 Získání permutace podle poˇradí . . . . . . . . . . . . . . . . . . . . . .
22
3.1.11 Kopírování permutace . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.1.12 Porovnání permutací . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.1.13 Skládání permutací . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.1.14 Cyklický posuv permutace . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.1.15 Znaménko permutace . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.1.16 Dealokace permutace . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.1.17 Bitové permutace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
Variace a kombinace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.2.1
Poˇcet všech variací, kombinací . . . . . . . . . . . . . . . . . . . . . . .
32
3.2.2
Alokace variace, kombinace . . . . . . . . . . . . . . . . . . . . . . . . .
33 vi
3.2.3
Parametry variace, kombinace . . . . . . . . . . . . . . . . . . . . . . .
34
3.2.4
Inicializace variace, kombinace typu int . . . . . . . . . . . . . . . . . .
35
3.2.5
Inicializace variace, kombinace typu char . . . . . . . . . . . . . . . . .
35
3.2.6
Tisk variace, kombinace na standardní výstup . . . . . . . . . . . . . .
36
3.2.7
Tisk variace, kombinace do proudu . . . . . . . . . . . . . . . . . . . .
37
3.2.8
Generování následující variace . . . . . . . . . . . . . . . . . . . . . . .
39
3.2.9
Generování následující kombinace . . . . . . . . . . . . . . . . . . . . .
43
3.2.10 Kopírování variace, kombinace . . . . . . . . . . . . . . . . . . . . . . .
47
3.2.11 Dealokace variace, kombinace . . . . . . . . . . . . . . . . . . . . . . .
47
4 Praktické ukázky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
4.1
Problém obchodního cestujícího . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
4.2
Výpoˇcet determinantu matice . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
4.3
Šifrování komunikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
5 Závˇer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
Literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
vii
Kapitola 1
Úvod Knihovny v programovacích jazycích jsou jejich velice duležitou ˚ souˇcástí, nebot’ obsahují velké množství funkcí [1], které jsou programátorovi k dispozici. Ten nemusí vymýšlet algoritmy a funkce, které pˇred ním již nˇekdo vymyslel a implementoval, ale staˇcí je vyhledat v knihovnˇe a nahrát do svého programu. Samotné nahrání je velice snadné, vystaˇcíme si jediným pˇríkazem a potˇrebné funkce jsou následnˇe volnˇe pˇrístupné k použití. Mezi standardní knihovny zatím nebyla zaˇrazena kombinatorická knihovna. Dávám si tedy za cíl vytvoˇrit knihovnu, která bude ulehˇcovat práci s permutacemi, variacemi, kombinacemi a bude obsahovat nˇekteré funkce potˇrebné k programování úloh kombinatorické povahy. Za pomoci známých algoritmu˚ implementuji funkce, které uživatel muže ˚ použít a u nichž bude mít zaruˇcenou jejich korektnost, nebot’ naprogramované funkce budou otestovány. Ve druhé kapitole se nachází popis již existujícího modelu standardní knihovny jazyka C, hlavnˇe konvence pro pojmenování funkcí. V novˇejších jazycích je povoleno pˇretˇežování funkcí (funkce dˇelající významovˇe totéž, ale s jinými typy parametru˚ mající stejný název). Uživatel použije jeden název pro funkci, již volá a pˇrekladaˇc rozhodne, který typ funkce se zavolá. Rozhodnutí je založeno v tomto pˇrípadˇe na typech parametru. ˚ V jazyce C je takováto shoda jmen nepˇrípustná [2]. Vyskytuje se tedy problém, jak utvoˇrit názvy významovˇe podobných funkcí. Název funkcí vznikne spojením zkratek z následujících vˇecí: funkcionality, vstupních parametru˚ a návratové hodnoty funkce. Zˇretˇezením tˇechto zkratek dává nˇekdy nejasný význam. Nejvˇetším problémem je však nejednotnost systému, napˇríklad jednou je typ vstupního parametru na zaˇcátku slova, kdežto jindy na konci. Proto zde analizuji starý systém pro kombinatorickou knihovnu a navrhuji nový, který je jednotný a zárovenˇ se pˇríliš neodlišuje od toho, na co už jsou uživatelé zvyklí. Tento kompromis je v ní použit. Tˇretí kapitola obsahuje výˇcet všech funkcí, které se nachází v naší kombinatorické knihovnˇe. U každé z funkcí je popsáno k cˇ emu slouží, jaké jsou parametry funkce a návratové hodnoty. Použití funkce je názornˇe ukázáno na krátkém programu využívající její funkcionalitu. Ve cˇ tvrté kapitole se vˇenuji ukázkám, jak lze funkce z naší knihovny využít na praktických pˇríkladech a závˇer obsahuje celkové hodnocení knihovny s jejím možným rozšíˇrením. 1
Kapitola 2
Konvence pro pojmenování funkcí v jazyce C 2.1
Popis problematiky
Funkce v programovacích jazycích mají jména, která oznaˇcují pamˇet’ová místa a pomocí nichž uživatel k daným funkcím pˇristupuje, aniž by musel používat jejich adresy. V mnohých moderních jazycích je možné definovat nˇekolik funkcí se stejným jménem, pokud mají rozdílnou množinu parametru˚ (alesponˇ co se jejich množství a typu˚ týˇce). Této vlastnosti se rˇ íká pˇretˇežování funkcí. Když je zavolána pˇretížená funkce, pˇrekladaˇc vybere správnou funkci podle poˇctu, typu˚ a poˇradí argumentu˚ volané funkce [3]. Pˇríklad pˇretížení funkcí: int fun(int a, int b) { return 1; } int fun(int a) { return 2; } int fun(double a) { return 3; } potom pˇri volání funkce fun tímto zpusobem: ˚ int x = fun(2, 3); se použije první definice fun kvuli ˚ volání funkce s dvˇema argumenty, obˇema typu int a pˇri volání int x = fun(4.3); se použije tˇretí definice funkce fun, protože argument pˇretížené funkce je typu double. V jazyce C je takovéto kolizní pojmenování funkcí nepˇrípustné a proto je nutné názvy funkcí od sebe odlišit pˇridáním nˇejakých znakových rˇ etˇezcu, ˚ aby bylo zajištˇeno jejich ruzné ˚ pojmenování. Pˇredchozí funkce by mohly vypadat v jazyce C tˇreba takto: int fun2i(int a, int b) { return 1; } int funi(int a) { return 2; } int fund(double a) { return 3; } kde i znaˇcí, že argument má být typu int, cˇ íslo 2 signalizuje požadavek dvou argumentu, ˚ zatímco d znaˇcí použití funkce s argumentem typu double. U takto vytvoˇrených názvu˚ funkcí je duležité, ˚ aby jejich používání bylo intuitivní a proto by mˇel v pojmenování funkcí být urˇcitý systém.
2
2.2. ANALÝZA STÁVAJÍCÍHO SYSTÉMU POJMENOVÁNÍ FUNKCÍ Pˇri vytváˇrení názvu˚ funkcí se budeme rˇ ídit tˇemito pravidly: •
vytvoˇrení názvu˚ podle funkcionality
•
urˇcení zkratky pro datové typy argumentu˚
•
umístˇení zkratek oznaˇcující datové typy argumentu˚
•
zvolení implicitního typu argumentu˚
2.2
Analýza stávajícího systému pojmenování funkcí
Cílem není vytvoˇrit úplnˇe nový a odlišný systém pojmenování, ale aby byl jednotný pro celou knihovnu a pˇresto se pˇríliš nelišil od stávajících modelu, ˚ na které jsou uživatelé používající jazyk C zvyklí. Toho docílíme studií názvu˚ existujících funkcí a odhalením jejich nedostatku˚ se zamˇerˇ ením hlavnˇe na matematickou knihovnu <math.h>. 2.2.1
Trigonometrické funkce
Ve standardní knihovnˇe jazyka C existují funkce sin, cos, tan, acos, asin, atan, atan2. Všechny jsou pouze ve verzích s datovým typem double. Jejich rozšíˇrení o práci s datovými typy float a long double jsou funkce z knihovny glibc. double sin (double x) •
Z názvu funkce je na první pohled zˇrejmé, že funkce poˇcítá sin úhlu x vyjádˇreného v radiánech.
•
Výchozí typ parametru a návratové hodnoty je double, pokud není specifikováno jinak. float sinf (float x)
•
Pˇridání f oznaˇcuje, že se jedná o funkci pracující s datovým typem float. Analogicky výskyt zkratky l znaˇcí práci s datovým typem long double.
•
Zkratka f je pˇridána na konec názvu funkce.
3
2.2. ANALÝZA STÁVAJÍCÍHO SYSTÉMU POJMENOVÁNÍ FUNKCÍ 2.2.2
Exponenciální a logaritmické funkce
double exp (double x) •
Zkratka exp je bˇežnˇe používána v matematické literatuˇre pro oznaˇcení exponenciální funkce.
•
Výchozí typ parametru a návratové hodnoty je double, takže zkratka doznaˇcující datový typ double se neuvádí. float expf (float x)
•
Zkratka f znaˇcí float a je umístˇen na konci názvu, nic se tedy neliší od pˇredchozí funkce sin. float logf (float x)
•
Funkce logaritmu, která pracuje s typem float, což je specifikováno taktéž na konci.
2.2.3
Aritmetické funkce
Ve standardní knihovnˇe nalezneme pro výpoˇcet absolutní hodnoty funkce: abs, labs a fabs pracující s typy int, long int a double, chybí pouze verze s float. int abs (int number) •
Funkce vrací absolutní hodnotu cˇ ísla zadaného jako parametr, proto zkratka abs (absolute).
•
Výchozím typem je int. long int labs (long int number)
•
Zkratka l znaˇcí long int právˇe kvuli ˚ výchozímu typu int, což je zmˇena oproti pˇredchozím funkcím, které mˇeli výchozí typ double a proto l znamenalo long double.
•
Výchozím typem je int. double fabs (double number)
•
Oproti ostatním funkcím, které oznaˇcují f jako float, zde f znaˇcí typ double. Tím nastává problém, jak oznaˇcit float, viz následující funkce.
•
ˇ Rešení: dabs nebo radˇeji absd. 4
˚ FUNKCÍ PRO KOMBINATORICKOU KNIHOVNU 2.3. TVORBA NÁZV U float fabsf (float number) •
Kvuli ˚ nevhodnému použití f pro double u funkce fabs je pˇridáno ještˇe jedno f na konec. Takovéto rˇ ešení není pˇríliš uživatelsky pˇríjemné, bylo by vhodnˇejší použít absf pro float a zárovenˇ absd pro double. Pˇríznak typu je lepší umístit za významové slovo abs, protože napˇríklad u funkce cabsf, s prototypem float cabsf (complex float z), má tento pˇríznak také na konci.
2.3
Tvorba názvu˚ funkcí pro kombinatorickou knihovnu
Po zanalyzovaní funkcí z matematické knihovny a vypozorování urˇcitých vzoru, ˚ mužeme ˚ nyní pojmenovat funkce naší kombinatorické knihovny, cˇ emuž se vˇenujeme v této podkapitole. 2.3.1
Tvoˇrení názvu˚ podle funkcionality
Z názvu funkce musí být na první pohled patrný její význam, skládá se proto ze zkratky významového slova. Neuvádí se celý název, aby programátor nebyl nucen vypisovat dlouhý název funkce, ale pouze zkratka vystihující danou funkcionalitu. Podle prefixu každé funkce poznáme, zda funkce pracuje s permutacemi, variacemi nebo kombinacemi. U variací je zvolena pˇredpona var (variation), která muže ˚ být chápána jako promˇenná (variable). Pˇredpona var však nikdy nebude samotná, takže k zámˇenˇe s variable nedojde. Permutace Variace Kombinace Faktoriál
perm var comb fact
Tabulka 2.1: Tabulka základních zkratek funkcí
2.3.2
Zkratky pro typy parametru˚ a návratové hodnoty
K jednoznaˇcnému oznaˇcení funkce se do názvu pˇridávají informace identifikující datový typ, s kterým daná funkce pracuje. Permutace, variace nebo kombinace mohou obsahovat hodnoty s typem int, short int, long int, char a k nim ještˇe bez znaménkovˇe chápané datové typy, jejichž hodnoty nenabývají záporných hodnot (unsigned int, unsigned short int, unsigned long int, 5
˚ FUNKCÍ PRO KOMBINATORICKOU KNIHOVNU 2.3. TVORBA NÁZV U Inicializace
init
Alokace pamˇeti
alloc
Dealokace pamˇeti
free
Kopírování
copy
Výpis
print
Zjištˇení velikosti
sizeof
Následující n-tice
next
Tabulka 2.2: Tabulka zkratek pro specifikace funkcí unsigned char). Reálné datové typy (float, double, long double) nebudeme v kombinatorické knihovnˇe vubec ˚ používat, vystaˇcíme s typy celoˇcíselnými. Jako intuitivní rˇ ešení se nabízí vzít poˇcáteˇcní písmena z datového typu. Napˇríklad pro char by byla zkratka c, pro unsigned int zkratka ui a pro unsigned long int zkratka uli. Pokud jsou operandy typu char nebo int uvedeny bez typového specifikátoru signed nebo unsigned, pˇredpokládá se použití typu signed char, resp. signed int. V pˇrípadˇe kompilátoru ANSI C je potˇreba ovˇerˇ it, zda implicitnˇe reprezentuje typ char jako signed char nebo unsigned char [4]. V naší kombinatorické knihovnˇe je vhodnˇejší použít všechny typy implicitnˇe jako unsigned, jelikož permutace, variace nebo kombinace jsou v této knihovnˇe inicializovány bud’ od nuly nebo od jedné a žádné záporné hodnoty tak nemohou obsahovat. Pro úplnost jsou implementovány i funkce se znaménkovými typy, které obsahují ve zkratce navíc písmeno s od klíˇcového slova signed. Z duvodu ˚ pˇrehlednosti se vynechává uvádˇení implicitního datového typu int. Stejnˇe jako se neuvádí u trigonometrické funkce sin zkratka pro double, nebo u aritmetické funkce pro výpoˇcet absolutní hodnoty zkratka pro int, tak i zde se vynechává písmeno i pro funkce pracující s datovým typem int. V kombinatorické knihovnˇe se pˇridávají do názvu funkce zkratky, které jsou znázornˇeny v tabulce 2.3. 2.3.3
Zpusob ˚ rˇazení zkratek za sebe
Otázkou je, jak seˇradit zkratky za sebe, aby takto vytvoˇrený název byl pˇrehledný a bylo na první pohled zˇrejmé o jaký druh funkce se jedná. Ke zvýraznˇení a oddˇelení zkratek je možné použít zpusob ˚ zápisu tzv. camelCase, který je používán jako konvence psaní ruzných ˚ identifikátoru˚ v jazyce Java, PHP nebo Ruby. V jazyce C ovšem není tento zpusob ˚ tvoˇrení názvu˚ používán, stejnˇe jako použití podtržítka. Výsledný název tedy vznikne zˇretˇezením významového slova (viz tabulka 2.1), bližší 6
˚ FUNKCÍ PRO KOMBINATORICKOU KNIHOVNU 2.3. TVORBA NÁZV U Datový typ
Zkratka
Poznámka
int
s
signed (int)
short int
sh
signed short (int)
unsigned short int
h
long int
sl
unsigned long int
l
char
sc
unsigned char
c
unsigned int
signed long (int) signed char
Tabulka 2.3: Tabulka datových typu˚ a jejich zkratek specifikace funkce (tabulka 2.2) a zkratky pro typ parametru funkce (tabulka 2.3). Napˇríklad inicializace permutace tvoˇrené bezznaménkovými znaky bude vypadat takto: perm + init + c.
7
Kapitola 3
Funkce kombinatorické knihovny V této kapitole jsou popsány všechny funkce kombinatorické knihovny, která má název comb.c. Funkce jsou dˇeleny do tˇrí sekcí: funkce pro permutace, variace a kombinace. Vˇetšina funkcí je naprogramována v 8 variantách, liší se datovým typem prvku˚ v permutaci, které mohou být typu unsigned int, int, unsigned char, char, unsigned short, short, unsigned long a nebo long. Pˇri použití každé z funkcí si mužeme ˚ vybrat mezi objektovˇe orientovanou variantou nebo její alternativou v podobˇe klasického pˇrístupu. Objektový pˇrístup má uschovanou velikost permutace pˇred samotnou permutací a pˇrístup k ní je rˇ ešen funkcí permsizeof, kdežto u klasického pˇrístupu je velikost permutace zadána jako další parametr funkce a do názvu funkce je pro odlišení pˇridáno písmeno n, které znaˇcí nutnost zadání délky permutace (napˇríklad permninit). Popis funkce se skládá z obecného popisu, kde je uvedeno k cˇ emu funkce slouží, pˇrípadnˇe obsahuje technické údaje k objasnˇení, jak je funkce implementována. Dále je uveden prototyp funkce, z nˇehož je patrný název, jsou popsány parametry a návratová hodnota funkce. K lepšímu pochopení je uvedena názorná ukázka v podobˇe krátkého programu s jeho výstupem. Pˇri práci s permutacemi, variacemi nebo kombinacemi v jejich objektové variantˇe je nutné nejprve pˇridˇelit pamˇet’ funkcemi permalloc, varalloc a comballoc, dále inicializovat vzniklý objekt pomocí funkcí perminit, varinit, pˇrípadnˇe combinit a teprve potom s nimi lze manipulovat.
3.1
Permutace
Permutací z n-prvkové množiny M nebo n-ˇclennou permutací nazýváme každou uspoˇrádanou n-tici navzájem ruzných ˚ prvku, ˚ vytvoˇrenou z množiny prvku˚ M. Poˇcet všech permutací z n prvku: ˚ P(n) = 1 . 2 . 3 . ... . n = n! [5].
8
3.1. PERMUTACE Nebo mužeme ˚ permutace obecnˇeji definovat tímto zpusobem: ˚ Permutací množiny M nazýváme každé prosté zobrazení množiny M na množinu M. Faktoriálem cˇ ísla n nazýváme funkci F na množinˇe všech nezáporných celých cˇ ísel, definovanou takto: F(0) = 1, F(n + 1) = (n + 1) F(n) (n ∈ N0 ) Místo F(n) píšeme n!. Pro n ≥ 1 je n! = 1 . 2 . . . (n - 1) n [5]. 3.1.1
Alokace permutace
Permutace je v pamˇeti reprezentována jako jednorozmˇerné pole, k jehož alokaci využíváme funkce ze standardní knihovny jazyka C – calloc. Alokovaný blok funkcí permalloc má velikost o jedna vˇetší než je požadovaná velikost permutace zadaná jediným vstupním parametrem. První prvek pole je vyhrazen pro uložení velikosti permutace a všechny ostatní pro samotnou permutaci. Vrácen je ukazatel na první prvek permutace, který ve skuteˇcnosti ukazuje až na druhý prvek alokovaného pole. Všechny bity alokovaného pole jsou inicializovány na nulu, jen první prvek pole obsahuje velikost permutace. U funkce permnalloc je pouze dynamicky alokováno pole s velikostí rovnou n. Velikost alokované permutace je omezena datovým typem prvku, ˚ které obsahuje, což znázornuje ˇ tabulka 3.1, která udává ke každé funkci maximální poˇcet prvku˚ permutace. U permutací typu unsigned int nebo unsigned long je ještˇe snížen rozsah na polovinu kvuli ˚ použití vstupního parametru typu int, resp long. Alokovat vˇetší permutace stejnˇe není zatím fyzicky možné, protože takovéto permutace by vyžadovaly až 17 GB operaˇcní pamˇeti. Pˇri požadavku o alokaci vˇetší permutace než je povoleno, nedochází k pˇridˇelení pamˇeti, ale dojde k nastavení externí promˇenné errno [6] na hodnotu ERANGE. Název funkce: unsigned int *permalloc(int n) unsigned int *permnalloc(int n) Parametry: Parametr n je celoˇcíselná hodnota, která urˇcí velikost alokované permutace.
9
3.1. PERMUTACE Návratová hodnota: Ukazatel na blok alokované pamˇeti, typ ukazatele záleží na použité funkci (napˇríklad permalloc vrací ukazatel na unsigned int, permallocsl zase ukazatel na long int). Není-li z nˇejakého duvodu ˚ možné pamˇet’ pˇridˇelit, funkce vrací nulový ukazatel. #include<stdio.h> #include "comb.h" int main() { unsigned int *permutace, n = 10, size = 0; permutace = permalloc(n); size = permsizeof(permutuce); printf("Velikost permutace je %d a zabira v pameti %d B.\n", size,1+size*sizeof(unsigned int)); permfree(permutace); return 0; }
Pˇríklad 3.1.1: Pˇríklad použití funkce permalloc
1.
Funkce
Prvky datového typu
Maximální poˇcet prvku˚ permutace
permalloc
unsigned int
32 767 nebo 2 147 483 647 1
permallocs
int
32 767 nebo 2 147 483 647 1
permallocc
unsigned char
256
permallocsc
char
128
permallocl
unsigned long
2 147 483 647
permallocsl
long int
2 147 483 647
permalloch
unsigned short
65 536
permallocsh
short int
32 768
permnalloc
unsigned int
32 767 nebo 2 147 483 647 1
permnallocs
int
32 767 nebo 2 147 483 647 1
permnallocc
unsigned char
256
permnallocsc
char
128
podle architektury 2B nebo 4B
10
3.1. PERMUTACE Funkce
Prvky datového typu
Maximální poˇcet prvku˚ permutace
permnallocl
unsigned long
2 147 483 647
permnallocsl
long int
2 147 483 647
permnalloch
unsigned short
65 536
permnallocsh
short int
32 768
Tabulka 3.1: Omezení velikosti permutace datovým typem 3.1.2
Délka permutace
Funkce permsizeof slouží k zjištˇení velikosti permutace. Velikost je uložena pˇred prvním prvkem permutace, takže je možné délku permutace zpˇrístupnit indexem -1. Tento pˇrístup se nedoporuˇcuje kvuli ˚ reprezentaci nejvˇetší možné velikosti permutace uložené na tomto místˇe. Všechny typy bez znaménka používají pˇrímou binární notaci, bez ohledu na to, zda typy bez znaménka používají dvojkovou doplnkovou ˇ notaci, jedniˇckovou doplnkovou ˇ notaci nebo pˇrímou notaci. Znaménkový bit se považuje za normální datový bit. To znamená, že slovo o n bitech muže ˚ reprezentovat celá cˇ ísla od 0 do 2n -1 [6]. Pro uložení velikosti permutace 2n tam, kde je povoleno zapsat slovo maximálnˇe o velikosti 2n -1 se využije hodnoty 0, která je funkcí permalloc nastavena pouze v pˇrípadˇe hodnoty 2n . Funkce permsizeof nulu automaticky reprezentuje jako cˇ íslo o jedna vˇetší než je horní hranice rozsahu daného typu. Napˇríklad pole datového typu char muže ˚ obsahovat pouze hodnoty v rozmezí 0 až 255. Pro velikost permutace 256, kterou není možné v promˇenné daného typu zobrazit, znaˇcí nula v poli na indexu -1 právˇe velikost permutace rovnou 256.
Název funkce: int permsizeof(unsigned int *perm)
Parametry: Parametr perm je ukazatel na první prvek permutace.
Návratová hodnota: Funkce permsizeof vrací poˇcet prvku˚ permutace, která byla vytvoˇrena funkcí permalloc. Pokud má permutace nulovou délku nebo vstupní parametr má hodnotu nulového ukazatele, je vrácena 0. 11
3.1. PERMUTACE 3.1.3
Inicializace permutace typu int
Alokované místo v pamˇeti funkcí permalloc obsahuje prvky pole rovné nule. K nastavení poˇcáteˇcních hodnot permutace slouží funkce perminit, která vytvoˇrí identickou permutaci. Pro matematické úˇcely je k dispozici funkce perminit1, ta nastaví identickou permutaci od jedné, kdežto u funkce perminit je poˇcáteˇcním prvkem permutace nula. Pro inicializaci permutace od nuly lze použít její modifikaci perminitex (jako exclusive), u které dojde k vytknutí vybraného prvku permutace a k celkovému zmenšení velikosti o jedna. Funkce má dva parametry, první je ukazatel na permutaci a druhý je vyjmutý prvek.
0 1 2 3 4 ··· n − 1 1 2 3 4 5 ··· n 0 1 2 3 4 ··· n − 1 1 2 3 4 5 ··· n Název funkce: void perminit(unsigned int *perm) void permninit(unsigned int *perm, int n) void perminit1(unsigned int *perm) void permninit1(unsigned int *perm, int n) void permninitex(unsigned int *perm, int t) void permninitex(unsigned int *perm, int t, int n) Parametry: Parametr perm je ukazatel na permutaci, která má být inicializována. Parametr t je prvek, který bude z permutace vytknut. Návratová hodnota: Žádná. 3.1.4
Inicializace permutace typu char
Permutace obsahující znaky lze nastavit pomocí libovolného znaku. Ten pak bude prvním prvkem permutace a na ostatních pozicích permutace budou znaky s ordinální hodnotou o jedna vˇetší než má jeho pˇredchudce. ˚ Název funkce: void perminitc(unsigned char *perm, char init) void permninitc(unsigned char *perm, char init, int n) 12
3.1. PERMUTACE Parametry: Parametr perm je ukazatel na permutaci, která má být inicializována. Znaková konstanta init je poˇcáteˇcním prvkem permutace. Návratová hodnota: Žádná. #include<stdio.h> #include "comb.h" int main() { unsigned char *permutace, n = 8; permutace = permallocc(n); printf("Znakova permutace zacinajici znakem ’a’: \n"); perminitc(permutace, ’a’); permprintc(permutace); printf("\nZnakova permutace zacinajici znakem ’H’: \n"); perminitc(permutace, ’H’); permprintc(permutace); permfreec(permutace); return 0; }
Pˇríklad 3.1.2: Pˇríklad použití funkce perminitc
Výstup ukázkového pˇríkladu: Znakova permutace zacinajici znakem ’a’: [a, b, c, d, e, f, g, h] Znakova permutace zacinajici znakem ’H’: [H, I, J, K, L, M, N, O]
3.1.5
Typ permutace
Tato pomocná funkce nám zjistí hodnotu nejmenšího prvku, který se v dané permutaci vyskytuje. Po alokovaní místa v pamˇeti pro uložení permutace a následném nastavení 13
3.1. PERMUTACE hodnot, muže ˚ permutace obsahovat prvky od jedné nebo od nuly. Typem permutace se zde rozumí právˇe toto nastavení. Název funkce: int permtype(unsigned int *perm) int permntype(unsigned int *perm, int n) Parametry: Parametr perm je ukazatel na první prvek permutace. Návratová hodnota: Funkce permtype vrací hodnotu 0, pokud je permutace inicializována od nuly, hodnotu 1 v pˇrípadˇe inicializace permutace od jedné. V ostatních pˇrípadech vrací funkce hodnotu -1. 3.1.6
Tisk permutace
Permutaci lze vypsat pˇrímo na standardní výstup nebo je možné ji zapsat do specifikovaného proudu. Formát výpisu cˇ íselné permutace je dán jednou ze tˇrí funkcí: permprint2line, permprint nebo permprintcycle. Pro výpis znakové permutace existuje pouze jedna varianta, která vypisuje permutaci jako sekvenci prvku˚ (funkce permprintc). Zápis permutace tabulkou: Funkce permprint2line zobrazuje permutaci koneˇcné množiny S jako tabulku se dvˇema rˇ ádky tak, jak se to obvykle v matematice píše. V prvním je seznam elementu˚ množiny S a na druhém se nachází obrazy každého z elementu. ˚
0 1 2 3 4 5 6 7 0 7 1 6 4 5 3 2 Permutace reprezentovaná polem: Alternativní zobrazení permutace je zjednodušením pˇredchozího výpisu, kde jsou vypsány pouze obrazy elementu˚ (druhý rˇ ádek tabulky). Tato reprezentace permutace znázornuje ˇ zpusob ˚ uložení elementu˚ permutace v poli. První rˇ ádek tabulky (vzory elementu˚ permutace) je skryt pod indexy prvku˚ pole. h
0 7 1 6 4 5 3 2
i
14
3.1. PERMUTACE Zápis permutace pomocí nezávislých cyklu: ˚ Další zpusob ˚ zápisu permutací je pomocí nezávislých cyklu. ˚ Cykly jsou uzavˇreny v kulatých závorkách a vzniknou následujícím zpusobem: ˚ zaˇcneme výbˇerem nˇekterého elementu x z S takového, že π(x) 6= x a zapisujeme sekvenci (x π(x) π(π(x))...) následných obrazu˚ π, dokud obraz nebude x. Množina zapsaných hodnot tvoˇrí orbit elementu x a uzávorkovaný výraz nám udává odpovídající cyklus. Dále pokraˇcujeme výbˇerem elementu y z S, který nebyl doposud zapsán v žádném z orbitu˚ a zárovenˇ π(y) 6= y, zapíšeme odpovídající cyklus, a tak dále dokud všechny elementy z množiny S nepatˇrí do nˇejakého cyklu, nebo nejsou pevnými body1 . Definice. Každou permutaci π ∈ Sn lze rozložit na souˇcin nezávislých cyklu˚ délky alesponˇ 2. Tento rozklad je až na poˇradí cˇ initelu˚ jednoznaˇcný. Zápis výše uvedené permutace pomocí nezávislých cyklu: ˚
1 7 2
3 6
Poznámka: v cyklu nejdˇríve vypisujeme jeho minimální prvek. 3.1.7
Tisk permutace na standardní výstup
Zapíše permutaci v daném formátu na standardní výstup (stdout). Název funkce: void permprint2line(unsigned int *perm) void permnprint2line(unsigned int *perm, int n) void permprint(unsigned int *perm) void permnprint(unsigned int *perm, int n) void permprintcycle(unsigned int *perm) void permnprintcycle(unsigned int *perm, int n) Parametry: Parametr perm je ukazatel na permutaci, která má být vytištˇena na standardní výstup. Návratová hodnota: Žádná.
1.
elementy permutace, které zustávají ˚ na místˇe (π(x) = x)
15
3.1. PERMUTACE #include<stdio.h> #include "comb.h" int main() { unsigned int *permutace, n = 8; permutace = permget(n,4433); // vytvoreni permutace: [0,7,1,6,4,5,3,2] printf("Vypis permutace tabulkou: \n"); permprint2line(permutace); printf("\nZjednoduseny vypis permutace: \n"); permprint(permutace); printf("\nPermutace vypsana pomoci nezavislych cyklu: \n"); permprintcycles(permutace); permfree(permutace); return 0; }
Pˇríklad 3.1.3: Pˇríklad použití funkce permprint Výstup ukázkového pˇríkladu: Vypis permutace tabulkou: (0 1 2 3 4 5 6 7) (0 7 1 6 4 5 3 2) Zjednoduseny vypis permutace: [0, 7, 1, 6, 4, 5, 3, 2] Permutace vypsana pomoci nezavislych cyklu: (1 7 2)(3 6)
3.1.8
Tisk permutace do proudu
Funkce umožnující ˇ uživateli zápis permutace do specifikovaného proudu. Mimo permutace lze do proudu zapsat i textový rˇ etˇezec, který bude umístˇen pˇred výpis permutace.
16
3.1. PERMUTACE Název funkce: int permfprint2line(FILE * stream, char * text, unsigned int *perm) int permfprint(FILE * stream, char * text, unsigned int *perm) int permfprintcycle(FILE * stream, char * text, unsigned int *perm) int permnfprint2line(FILE * stream, char * text, unsigned int *perm, int n) int permnfprint(FILE * stream, char * text, unsigned int *perm, int n) int permnfprintcycle(FILE * stream, char * text, unsigned int *perm, int n)
Parametry: První parametr stream je ukazatel na objekt FILE, který identifikuje proud pro výpis permutace. Druhý parametr text tvoˇrí uvozovací textový rˇ etˇezec pˇred výpisem permutace. Parametr perm je ukazatel na permutaci, která má být vytištˇena do urˇceného proudu. Návratová hodnota: Poˇcet znaku, ˚ které se posílají do výstupního proudu, pokud nenastane chyba. V pˇrípadˇe výskytu chyby je vrácena hodnota EOF, která má ve vˇetšinˇe tradiˇcních implementacích hodnotu -1. 3.1.9
Generování následující permutace
Funkce permnext zmˇení obsah permutace zadané jako jediný parametr tak, že výsledná permutace je lexikograficky vˇetší. Zárovenˇ neexistuje permutace, která by byla vˇetší než puvodní, ˚ ale menší než novˇe vytvoˇrená. Tato vlastnost nám umožní generovat všechny možné permutace v pˇrípadˇe volání funkce na jednotkovou permutaci. Permutace jsou vytváˇreny dokud funkce nevrátí hodnotu nula (neexistuje už žádná vˇetší permutace). ˇ Rešením, jak vytvoˇrit všech n! permutací se zabýval Trotter [7], který uspoˇrádal jednotlivé transpozice do sekvence tak, aby každé dva prvky, které mají být transponovány byly sousedící. Jiný pˇrístup zvolil Wells, jeho metoda spoˇcívá ve vytvoˇrení nové permutace z pˇredchozí. Stejného principu využívám i v této práci s tím rozdílem, že vytvoˇrené permutace jsou lexikograficky uspoˇrádané. K vytvoˇrení minimálního lexikografického následníka je potˇreba nalézt ˇ dva prvky, které zamˇeníme a seˇradit urˇcitou podmnožinu prvku˚ permutace. Casová složitost problému seˇrazení posloupnosti o n prvcích je Θ(n log n). Když ale využijeme skuteˇcnosti, že 17
3.1. PERMUTACE #include<stdio.h> #include "comb.h" int main() { unsigned int *permutace, n = 8; FILE * pFile = NULL; pFile = fopen("permfprint_example.txt","w"); permutace = permalloc(n); perminit(permutace); permfprint(pFile,"identicka permutace: ", permutace); permfprint(pFile,"", permutace); fclose(pFile); permfree(permutace); return 0; }
Pˇríklad 3.1.4: Pˇríklad použití funkce permfprint rˇazená posloupnost je již seˇrazena sestupnˇe, dosáhneme rychlejších výsledku. ˚ K obrácenému seˇrazení totiž staˇcí provést reverzi, což znamená prohodit první prvek s posledním, druhý s pˇredposledním atd. Tím se nám cˇ asová složitost sníží na n/2. ˇ Stále je však otázkou, jak nalézt prvky, které mají být prohozeny. Rešení tohoto problému je popsáno v sekci: Popis algoritmu. Název funkce: int permnext(unsigned int *perm) int permnnext(unsigned int *perm, int n)
18
3.1. PERMUTACE Parametry: Parametr perm je ukazatel na permutaci, ze které se bude vytváˇret následující permutace. Návratová hodnota: Pokud existuje lexikograficky vˇetší permutace, než která byla zadána jako vstupní parametr, je vrácena hodnota 1, v opaˇcném pˇrípadˇe hodnota 0. Zdrojový kód: int permnext(unsigned int *p) { int i, dm, hm, pos, ord = 1; if( p == NULL) return 0; for( pos = permsizeof(p) - 1; pos > 0; pos-- ) { for( i = pos - 1; i >= 0 && ord; i-- ) { if( p[i] < p[pos] ) { /* swap */ p[i] ^= p[pos]; p[pos] ^= p[i]; p[i] ^= p[pos]; /* reverse */ hm = permsizeof(p) - 1; for( dm = i + 1; dm < hm; dm++,hm-- ) { p[hm] ^= p[dm]; p[dm] ^= p[hm]; p[hm] ^= p[dm]; } return 1; }else { if( p[i] < p[i+1] ) ord = 0;} } ord = 1; } return 0; }
19
3.1. PERMUTACE Použité promˇenné: Promˇenná pos je index prvku pole, jenž má být prohozen s jiným prvkem tak, aby došlo k pˇrechodu na následující permutaci. Pod indexem i hledáme v poli menší prvek než je na pozici pos. Pˇri nalezení této dvojice jsou prvky s indexy i a pos vzájemnˇe prohozeny. Indexy dm a hm oznaˇcují poˇcáteˇcní a koncový úsek pole, který bude seˇrazen vzestupnˇe. Hodnota promˇenné ord udává, že posloupnost prvku˚ za pozicí s indexem i je sestupnˇe uspoˇrádaná a tudíž mužeme ˚ prvky na indexech i a pos prohodit, aniž by došlo k vzniku nesprávné permutace.
Popis algoritmu: K vzniku nové permutace hledáme dvojici prvku, ˚ které prohodíme. Aby vznikl lexikografický následník, zamˇeníme vˇetší prvek umístˇený v pozici blíže ke konci, s prvkem menším v pozici blíže zaˇcátku. Nalezení dvojice prohazovaných prvku˚ probíhá následujícím zpusobem: ˚ Zaˇcínáme porovnávat od posledního prvku s jeho pˇredchudci. ˚ Pˇri hledání menšího prvku si kontrolujeme, zda se za ním nachází sestupnˇe seˇrazená posloupnost. Pokud tomu tak není, prohození nelze provést, protože by došlo k pˇreskoˇcení nˇekolika možností a pˇri generování všech n! permutací by výsledkem byla jen urˇcitá podmnožina z celkového poˇctu. Tuto situaci názornˇe ilustruje následující obrázek, ve kterém nedochází k prohození prvku 4 s prvním menším prvkem 3 (5 < 6 > 4), nebot’ bychom pˇreskoˇcili menší permutace: [1, 2, 3, 6, 4, 5] a [1, 2, 3, 6, 5, 4].
Prvek 3 na této pozici mužeme ˚ zamˇenit s prvkem 4 až v okamžiku, kdy je splnˇena podmínka seˇrazené sekvence prvku˚ (6 > 5 > 4) viz obrázek.
20
3.1. PERMUTACE Pokud nemužeme ˚ provést prohození prvku˚ at’ už z duvodu ˚ neexistence menšího prvku nebo kvuli ˚ neseˇrazené posloupnosti prvku˚ za nalezeným menším prvkem, posuneme se o jednu pozici doleva a opakujeme porovnávání s pˇredchudci ˚ prvku na této nové pozici. Jakmile mužeme ˚ prvky bez problému prohodit, uˇciníme tak a uspoˇrádáme sekvenci následovanou za menším z nalezených dvou prvku˚ (prvek v pozici blíže zaˇcátku). Tato sekvence v pˇrípadˇe prohození bude vždy sestupnˇe uspoˇrádaná, jinak nelze prvky prohodit. K setˇrídˇení posloupnosti tedy staˇcí provést reverzi prvku˚ a výsledkem je minimální lexikografický následník zadané permutace. ˇ Casová složitost: Poˇcet porovnání je v nejhorším pˇrípadˇe roven
Pn−1 i=1
(n − i) kde n ≥ 1.
Nejvíce zámˇen prvku˚ nastane v pˇrípadˇe prohození prvku na první pozici s jakýmkoliv jiným prvkem, pak je seˇrazena celá posloupnost následovaná za prvním prvkem. Poˇcet prohození je tedy: 1 + (n − 1) / 2. #include<stdio.h> #include "comb.h" int main() { unsigned int *permutace, n = 4; permutace = permalloc(n); perminit1(permutace); do{ permprint(permutace); }while( permnext(permutace) ); return 0; }
Pˇríklad 3.1.5: Pˇríklad použití funkce permnext Výstup ukázkového pˇríkladu: [1, [1, [1, [1,
2, 2, 3, 3,
3, 4, 2, 4,
4] 3] 4] 2]
[2, [2, [2, [2,
1, 1, 3, 3,
3, 4, 1, 4,
4] 3] 4] 1]
[3, [3, [3, [3,
1, 1, 2, 2,
2, 4, 1, 4,
4] 2] 4] 1]
[4, [4, [4, [4,
1, 1, 2, 2,
2, 3, 1, 3,
3] 2] 3] 1]
21
3.1. PERMUTACE [1, 4, 2, 3] [1, 4, 3, 2]
[2, 4, 1, 3] [2, 4, 3, 1]
[3, 4, 1, 2] [3, 4, 2, 1]
[4, 3, 1, 2] [4, 3, 2, 1]
3.1.10 Získání permutace podle poˇradí K získání permutace, která je vytvoˇrena podle lexikografického uspoˇrádání v požadovaném poˇradí slouží funkce permget. K výpoˇctu je využita funkce permnext, která generuje permutace do té doby, než je vytvoˇrena správná permutace. Název funkce: unsigned int *permget(int n, int s) unsigned int *permnget(int n, int s) Parametry: Parametr n udává velikost požadované permutace. Podle parametru s se vygeneruje v poˇradí s-tá permutace. Návratová hodnota: Ukazatel na novˇe vytvoˇrenou permutaci. 3.1.11 Kopírování permutace V pˇrípadˇe potˇreby vytvoˇrit kopii permutace lze využít funkce permcopy. Pˇri jejím zavolání dojde k alokaci pamˇeti, zkopírování všech prvku˚ puvodní ˚ permutace do novˇe alokovaného bloku a následnˇe je vrácena adresa zkopírované permutace. Název funkce: unsigned int *permcopy(unsigned int *perm) unsigned int *permncopy(unsigned int *perm, int n) Parametry: Parametr perm je ukazatel na permutaci, z níž se bude vytváˇret kopie. Návratová hodnota: Ukazatel na novˇe vytvoˇrenou kopii puvodní ˚ permutace. 22
3.1. PERMUTACE #include<stdio.h> #include "comb.h" int main() { unsigned int *permutace, *kopie, n = 8; permutace = permalloc(n); perminit(permutace); kopie = permcopy(permutace); // zaloha permutace permnext(permutace); // vytvoreni nasledujici permutace printf("Nove vytvorena permutace (naslednik puvodni): \n"); permprint(permutace); printf("\nPredchudce nove vytvorene permutace: \n"); permprint(kopie); permfree(permutace); permfree(kopie); return 0; }
Pˇríklad 3.1.6: Pˇríklad použití funkce permcopy Výstup ukázkového pˇríkladu: Nove vytvorena permutace (naslednik puvodni): [0, 1, 2, 3, 4, 5, 7, 6] Predchudce nove vytvorene permutace: [0, 1, 2, 3, 4, 5, 6, 7]
3.1.12 Porovnání permutací Pro porovnání permutací zavedeme pojem lexikografického uspoˇrádání (slovníkové rˇ azení). Jde o matematický pojem z oboru teorie uspoˇrádání, který formalizuje vlastnosti uspoˇrádání "podle abecedy"[8]. Definice: Lexikografické uspoˇrádání na uspoˇrádáné n-tici Xn = { [a1 ,a2 ,...,an ] : ai ∈ X } je definováno vztahem [a1 ,a2 ,...,an ]≤Le [b1 ,b2 , ..., bn ] ⇔ (a1 ≤ b1 ) ∨ (a1 = b1 ∧ a2 ≤ b2 ) ∨ (a1 = b1 ∧ a2 = b2 ∧ a3 ≤ b3 ) ∨ ... ∨ (a1 = b1 ∧ a2 = b2 ∧ ... ∧ an-1 = bn-1 ∧ an ≤ bn )
23
3.1. PERMUTACE Název funkce: int permcmp(unsigned int *p, unsigned int *q) int permncmp(unsigned int *p, unsigned int *q, int n) Parametry: Parametr p a q jsou ukazatele na porovnávané permutace. Návratová hodnota: ˇ Císlo -1, 0, 1, je-li p lexikograficky menší, rovno, vˇetší než q. 3.1.13 Skládání permutací Násobení permutací není v obecném pˇrípadˇe komutativní operace, proto rozlišujeme mezi skládáním zleva, cˇ i zprava. Ke složení dvou permutací zleva slouží funkce permcompl, permutace lze složit i zprava funkcí permcompr. U komutativních permutací nezáleží, kterou z výše uvedených funkcí použijeme. Zjištˇení komutativity permutací provádí funkce permiscommutative. Název funkce: int *permcompl(unsigned int *l, unsigned int *r) int *permncompl(unsigned int *l, unsigned int *r, int n) int *permcompr(unsigned int *l, unsigned int *r) int *permncompr(unsigned int *l, unsigned int *r, int n) Parametry: Parametry l a r jsou ukazatele na skládané permutace. Návratová hodnota: Ukazatel na permutaci, která vznikla jako souˇcin dvou permutací. Pokud nelze složit zadané permutace, je vrácen nulový ukazatel.
24
3.1. PERMUTACE #include<stdio.h> #include "comb.h" int main() { unsigned int *P = NULL, *Q = NULL, n = 8; unsigned int *S_zleva = NULL, *S_zprava = NULL; P = permget(n,9157); Q = permget(n,32859); printf("\nP: \n"); permprint2line(P); printf("\nQ: \n"); permprint2line(Q); S_zleva = permcompl(P, Q); printf("\nS = P * Q : \n"); permprint2line(S_zleva); S_zprava = permcompr(P, Q); printf("\nS = Q * P : \n"); permprint2line(S_zprava); permfree(P); permfree(Q); permfree(S_zleva); permfree(S_zprava); return 0; }
Pˇríklad 3.1.7: Pˇríklad použití funkce permcompl a permcompr
Výstup ukázkového pˇríkladu:
P: (0 1 2 3 4 5 6 7) (1 6 5 2 4 0 7 3)
Q: (0 1 2 3 4 5 6 7) (6 3 4 7 0 2 5 1)
S = P * Q : (0 1 2 3 4 5 6 7) (3 5 2 4 0 6 1 7) S = Q * P : (0 1 2 3 4 5 6 7) (7 2 4 3 1 5 0 6)
25
3.1. PERMUTACE 3.1.14 Cyklický posuv permutace Zavoláním funkce permshiftl na permutaci dojde k cyklickému posunu prvku˚ o k pozic doleva. Pro cyklický posuv elementu˚ permutace doprava slouží funkce permshiftr. Obrázek níže ilustruje posouvání prvku˚ v permutaci naší funkcí. Jak už z názvu vyplývá, jde o cyklické posuny. Na obrázku cyklicky posouváme osmiprvkovou posloupnost o dvˇe místa doprava a pˇri tom potˇrebujeme vykonat dva nezávislé cyklické posuny. Pˇri každém z nich si do cyklu zakomponujeme pomocnou promˇennou, aby nedošlo ke ztrátˇe informace o jednom z prvku. ˚ Tento algoritmus je efektivnˇejší, než kdybychom si vytvoˇrili celou kopii permutace, a její prvky pak vkládali na ty správné pozice. Vyžadovalo by to dvojnásobnou pamˇet’, n pˇriˇrazení do kopírované permutace a následných n vložení zpátky. My zde potˇrebujeme pouze jednu pomocnou promˇennou, do které pˇriˇrazujeme prvky pouze tolikrát, kolik je potˇreba vykonat cyklu. ˚ U permutací délky 2, 3, 5, 7, 11, 13, atd. (velikosti jsou prvoˇcísla) tvoˇrí posun o libovolný poˇcet vždy jen jeden cyklus a tedy jedno pˇriˇrazení navíc, celkový poˇcet pˇriˇrazení je v tomto pˇrípadˇe rovno n + 1.
Název funkce: void permshiftl(unsigned int *perm, int k) void permnshiftl(unsigned int *perm, int k, int n) void permshiftr(unsigned int *perm, int k) void permnshiftr(unsigned int *perm, int k, int n)
Parametry: Parametr perm je ukazatel na permutaci, kterou cyklicky posuneme o urˇcitý poˇcet míst doleva, cˇ i doprava. Parametr k specifikuje poˇcet míst, o kolik se posune každý prvek permutace.
Návratová hodnota: Žádná. 26
3.1. PERMUTACE
#include<stdio.h> #include "comb.h" int main() { unsigned int *permutace = NULL, n = 8, k = 1; permutace = permalloc(n); perminit1(permutace); printf("Posun o %d misto doprava: \n",k); permprint(permutace); permshiftr(permutace, k); permprint(permutace); perminit1(permutace); printf("\nPosun o %d misto doleva: \n",k); permprint(permutace); permshiftl(permutace, k); permprint(permutace); permfree(permutace); return 0; }
Pˇríklad 3.1.8: Pˇríklad použití funkce permshiftl a permshiftr
27
3.1. PERMUTACE Výstup ukázkového pˇríkladu: Posun o 1 misto doprava: [1, 2, 3, 4, 5, 6, 7, 8] [8, 1, 2, 3, 4, 5, 6, 7] Posun o 1 misto doleva: [1, 2, 3, 4, 5, 6, 7, 8] [2, 3, 4, 5, 6, 7, 8, 1]
3.1.15 Znaménko permutace ˇ Ríkáme, že permutace množiny Un = {1, 2, ..., n} má inverzi, právˇe když existují takové indexy i, j (i < j), že ki > kj (i, j ∈ Un ). Oznaˇcíme-li v(P) poˇcet všech inverzí v permutaci P, pak permutaci P nazýváme sudou, resp. lichou, právˇe když v(P) je sudé, resp. liché cˇ íslo. Znaménko [ signum ] permutace P je cˇ íslo z(P) = (−1)v(P) [5]. Pˇríklad: Inverze permutace [3, 1, 2, 5, 4] jsou vyznaˇceny oblouˇckem.
Název funkce: int permsgn(unsigned int *perm) int permnsgn(unsigned int *perm, int n) Parametry: Parametr perm je ukazatel na permutaci, u které zkoumáme její znaménko. Návratová hodnota: Je-li permutace sudá, je vrácena hodnota 1, v pˇrípadˇe lichosti permutace je vrácena hodnota -1. Výstup ukázkového pˇríkladu: Znamenko permutace: [1, 2, 3, 4, 5] je +1. Znamenko permutace: [1, 2, 3, 5, 4] je -1.
28
3.1. PERMUTACE #include<stdio.h> #include "comb.h" int main() { unsigned int *permutace = NULL, n = 5; permutace = permalloc(n); perminit1(permutace); printf("Znamenko permutace: [1, 2, 3, 4, 5] je %+d.\n", permsgn(permutace)); permnext(permutace); printf("Znamenko permutace: [1, 2, 3, 5, 4] je %+d.\n", permsgn(permutace)); return 0; }
Pˇríklad 3.1.9: Pˇríklad použití funkce permsgn 3.1.16 Dealokace permutace Funkce permfree uvolní pamˇet’, která byla pˇridˇelena funkcí permalloc. Pˇri volání obycˇ ejné funkce free na alokovanou permutaci se neuvolní kus pamˇeti (obsahující údaj o velikosti permutace), který je umístˇen pˇred polem. Název funkce: void permfree(unsigned int *perm) Parametry: Parametr perm je ukazatel na permutaci, která má být z pamˇeti uvolnˇena. Návratová hodnota: Žádná. 3.1.17 Bitové permutace Mezi permutace mužeme ˚ zaˇradit i ty bitové, kde dochází k permutaci jednotlivých bitu, ˚ kdežto u obyˇcejných permutací jsou permutovány celé prvky pole. K tomuto úˇcelu slouží funkce bitperm, která bere jako první vstupní parametr prvek, jehož bity budou následnˇe permutovány permutací zadanou jako druhý parametr. Funkce bitpermb nám vrátí permutovaný prvek funkcí bitperm do puvodní ˚ podoby. 29
3.1. PERMUTACE Pro permutování bitu˚ se využívá dvou bitových operátoru, ˚ bitového souˇcinu (AND) a bitové nonekvivalence (XOR). Pomocí bitového souˇcinu se namapujeme postupnˇe na každý bit vstupních dat a ten pak bitovou nonekvivalencí zmˇeníme, pokud je to možné (nemuže ˚ nám vzniknou bitový vzorek s jiným poˇctem jedniˇcek a nul, než jaký byl u puvodního ˚ vzorku). Bity, které budou zmˇenˇeny, udává rozdíl každé dvojice sousedících prvku˚ ze zadané permutace a pozice jedniˇcek a nul v puvodním ˚ vzorku. Název funkce: int bitperm(int b, int *perm) int bitpermn(int b, int *perm, int n) int bitpermb(int b, int *perm) int bitpermbn(int b, int *perm, int n) Parametry: Parametr b je prvek, jehož bity chceme permutovat. Parametr perm je ukazatel na permutaci, podle které jsou bity prvku b permutovány. Pokud chceme permutovat všechny bity vstupního údaje, musí mít permutace stejné množství prvku˚ jako je poˇcet bitu˚ prvku b. Pˇrístupné velikosti permutace datového typu int jsou: 8, 16, 24 a 32. Podle tˇechto velikostí dojde k permutaci spodních 8, 16, 24 nebo všech 32 bitu˚ vstupního prvku. Pˇri jiných velikostech nedochází k žádné permutaci bitu. ˚ Návratová hodnota: Prvek b po permutaci jeho bitu. ˚ Výstup ukázkového pˇríkladu: Permutace p1 = [3, 7, 2, 6, 1, 5, 0, 4] Permutaci bitu cisla 164 (10100100) pomoci p1 vzniklo cislo 52 (00110100). Permutace p2 = [7, 5, 3, 1, 6, 4, 2, 0] Permutaci bitu cisla 164 (10100100) pomoci p2 vzniklo cislo 25 (00011001).
30
3.2. VARIACE A KOMBINACE #include<stdio.h> #include "comb.h" int main() { int p1[]={3,7,2,6,1,5,0,4}; int p2[]={7,5,3,1,6,4,2,0}; unsigned int b, n =8; printf("Permutace p1 = "); permnprints(p1,n); b = 164; printf("Permutaci bitu b, bitpermn(b, printf("\nPermutace p2 permnprints(p2,n); printf("Permutaci bitu b, bitpermn(b, return 0;
cisla %d (10100100) pomoci p1 vzniklo cislo %d (00110100).\n", p1, n)); = "); cisla %d (10100100) pomoci p2 vzniklo cislo %d (00011001).\n", p2, n));
}
Pˇríklad 3.1.10: Pˇríklad použití funkce bitpermn
3.2
Variace a kombinace
Variace i kombinace jsou k-tice vybírané z n prvku. ˚ Jejich struktura v pamˇeti se liší jen nepatrnˇe, u kombinací jde o jednorozmˇerné pole obsahující k prvku, ˚ kdežto u variací je do pole zaˇrazeno i zbylých n-k nevybraných prvku, ˚ umístˇených v poli až za vybranou k-ticí. Základní operace s nimi mají stejnou implementaci, ale používají rozdílná jména funkcí (prefix var pro práci s variacemi, prefix comb jde-li o kombinace). Dvojí pojmenování je zvoleno kvuli ˚ tomu, aby bylo na první pohled zˇrejmé o jakou formu k-tice jde (zda-li v ní záleží na poˇradí, cˇ i nikoliv). Variací k-té tˇrídy z n-prvkové množiny nebo variací k-té tˇrídy z n-prvku˚ nazýváme každou uspoˇrádanou k-tici navzájem ruzných ˚ prvku, ˚ vytvoˇrenou z n-prvkové množiny, tj. každý prvek z daných n prvku˚ se v jedné variaci muže ˚ vyskytnout právˇe jednou. Poˇcet všech variací k-té tˇrídy z n-prvkové množiny: V(k, n) = n(n − 1) (n − 2)...(n − k + 1) = n! / (n − k)!. Kombinací k-té tˇrídy z n-prvkové množiny nebo kombinací k-té tˇrídy z n prvku˚ nazýváme každou k-prvkovou podmnožinu z n-prvkové množiny, tj. u kombinace nepˇrihlížíme k uspoˇrádání prvku˚ a každý prvek z daných n prvku˚ se v jedné kombinaci muže ˚ vyskytnout nejvýše jednou. 31
3.2. VARIACE A KOMBINACE Poˇcet všech kombinací k-té tˇrídy z n prvku: ˚ C(k, n) = n! / k!(n − k)! [5].
3.2.1
Poˇcet všech variací, kombinací
Funkce varcount poˇcítá podle definice celkový poˇcet všech variací. Funkce combcount poˇcítá podle definice celkový poˇcet všech variací. Výpoˇcet však neprobíhá pˇres výpoˇcet faktoriálu˚ tak, že prvnˇe se spoˇcítá n! a poté dojde k dˇelení jmenovatelem, ale prubˇ ˚ ežnˇe se krátí zlomek nejvˇetším spoleˇcným dˇelitelem. Kdyby se neprovádˇelo krácení ihned, už pˇri velikosti n = 13 by došlo k pˇreteˇcení datového typu long int a výsledky by byly správné jen pro malé vstupní hodnoty n. I tak jsme ale schopni vrátit jen poˇcet možností menší než 2 147 483 648, což je omezení dané návratovým typem long int.
Název funkce: long varcount(int k, int n) long combcount(int k, int n)
Parametry: Parametr k je celoˇcíselná hodnota, která urˇcuje velikost k-tice. Hodnota n znaˇcí velikost množiny, ze které lze vybírat prvky.
Návratová hodnota: Celkový poˇcet variací (kombinací) rˇ ádu k z n prvku. ˚
Výstup ukázkového pˇríkladu: Celkovy pocet vsech kombinaci radu 3 ze 6 prvku je 20. Celkovy pocet vsech variaci radu 3 ze 6 prvku je 120. Celkovy pocet vsech kombinaci radu 5 ze 10 prvku je 252. Celkovy pocet vsech variaci radu 5 ze 10 prvku je 30240. Max. pocet variaci, ktery lze vypocitat: V(10, 13) = 1037836800. Max. pocet kombinaci, ktery lze vypocitat: K(15, 34) = 1855967520.
32
3.2. VARIACE A KOMBINACE #include<stdio.h> #include "comb.h" int main() { int k, n; k = 3; n = 6; printf("Celkovy pocet vsech kombinaci radu %d ze %d prvku je %ld.\n", k, n, combcount(k,n)); printf("Celkovy pocet vsech variaci radu %d ze %d prvku je %ld.\n\n", k, n, varcount(k,n)); k = 5; n = 10; printf("Celkovy pocet vsech kombinaci radu %d ze %d prvku je %ld.\n", k, n, combcount(k,n)); printf("Celkovy pocet vsech variaci radu %d ze %d prvku je %ld.\n\n", k, n, varcount(k,n)); k = 10; n = 13; printf("Max. pocet variaci, ktery lze vypocitat: V(%d, %d) = %ld.\n", k, n, varcount(k,n)); k = 15; n = 34; printf("Max. pocet kombinaci, ktery lze vypocitat: K(%d, %d) = %ld.\n", k, n, combcount(k,n)); return 0; }
Pˇríklad 3.2.1: Pˇríklad použití funkce varcount a combcount 3.2.2
Alokace variace, kombinace
Variace k-té tˇrídy z n prvku˚ je v pamˇeti uložena jako pole o velikosti n + 2. U kombinací je velikost alokovaného pole pouze k + 2. Pˇred každou k-ticí jsou umístˇeny charakteristické informace (poˇcet vybíraných prvku˚ a celková velikost vybírané množiny) a u variací jsou ještˇe navíc za k-ticí umístˇeny zbylé prvky, které nebyly zahrnuty do variace. K údajum ˚ o velikostech lze pˇristoupit pomocí funkcí sizeofn a sizeofk s urˇcitým prefixem, které vrací velikost n, resp. velikost k.
Název funkce: unsigned int *varalloc(int k, int n) unsigned int *varknalloc(int k, int n) 33
3.2. VARIACE A KOMBINACE unsigned int *comballoc(int k, int n) unsigned int *combknalloc(int k, int n) Parametry: Parametr k je celoˇcíselná hodnota, která urˇcuje velikost k-tice. Hodnota n znaˇcí velikost množiny, ze které lze vybírat prvky. Návratová hodnota: Ukazatel na blok alokované pamˇeti. Typ ukazatele záleží na použité funkci (napˇríklad varalloc vrací ukazatel na unsigned int, varallocsl zase ukazatel na long int). Není-li z nˇejakého duvodu ˚ možné pamˇet’ pˇridˇelit, funkce vrací nulový ukazatel. 3.2.3
Parametry variace, kombinace
Parametry variace se rozumí tˇrída variace (k) a velikost množiny prvku˚ (n), ze které vybíráme její podmnožinu. K zisku velikosti k a n slouží funkce varsizeofk (combsizeofk) resp. varsizeofn (combsizeofn). Parametry k-tic jsou nastaveny pˇri alokaci pamˇeti funkcemi varalloc a comballoc, takže v pˇrípadˇe volání funkcí na jinak vytvoˇrené pole budou vráceny nesmyslné výsledky. Název funkce: int varsizeofk(unsigned int *var) int varsizeofn(unsigned int *var) int combsizeofk(unsigned int *comb) int combsizeofn(unsigned int *comb) Parametry: Parametr var (comb) je ukazatel na první prvek k-tice. Návratová hodnota: Funkce varsizeofk a combsizeofk vrací velikost k-tice, neboli poˇcet vybíraných prvku˚ z celkového množství n. Funkce varsizeofn a combsizeofn vrací velikost poˇcáteˇcní množiny n, ze které jsou k-tice vybírány. Pokud má k-tice nulovou délku nebo vstupní parametr má hodnotu nulového ukazatele, je vrácena 0. 34
3.2. VARIACE A KOMBINACE 3.2.4
Inicializace variace, kombinace typu int
Kombinace i variace jsou nastaveny tak, že obsahují nejmenších k-prvku, ˚ kde výchozí nejmenší prvek je roven nule, pˇri inicializaci od jedné je možné použít funkci varinit1 nebo combinit1. U variací je kromˇe k-tice inicializováno i nevybraných n-k prvku. ˚
Název funkce: void varinit(unsigned int *var) void varkninit(unsigned int *var, int k, int n) void combinit(unsigned int *comb) void combkninit(unsigned int *comb, int k, int n) Parametry: Parametr var (comb) je ukazatel na variaci (kombinaci), která má být inicializována. Návratová hodnota: Žádná. 3.2.5
Inicializace variace, kombinace typu char
Variace (kombinace) obsahující znaky lze nastavit pomocí libovolného znaku. Ten pak bude prvním prvkem k-tice a na ostatních pozicích budou znaky s ordinální hodnotou o jedna vˇetší než má jeho pˇredchudce. ˚ Název funkce: void varinitc(unsigned char *var, char init) void varkninitc(unsigned char *var, char init, int k, int n) void combinitc(unsigned char *comb, char init) void combkninitc(unsigned char *comb, char init, int k, int n) Parametry: Parametr var (comb) je ukazatel na variaci (kombinaci), která má být inicializována. Znaková konstanta init je poˇcáteˇcním prvkem variace (kombinace). 35
3.2. VARIACE A KOMBINACE Návratová hodnota: Žádná. #include<stdio.h> #include "comb.h" int main() { unsigned char *variace, n = 8, k = 5; variace = varallocc(k,n); printf("Znakova variace zacinajici znakem ’a’: \n"); varinitc(variace, ’a’); varprintc(variace); printf("\nZnakova variace zacinajici znakem ’H’: \n"); varinitc(variace, ’H’); varprintc(variace); varfreec(variace); return 0; }
Pˇríklad 3.2.2: Pˇríklad použití funkce varinitc
Výstup ukázkového pˇríkladu: Znakova variace zacinajici znakem ’a’: [a, b, c, d, e] Znakova variace zacinajici znakem ’H’: [H, I, J, K, L]
3.2.6
Tisk variace, kombinace na standardní výstup
Zapíše k-tici na standardní výstup (stdout). Variace jsou vypsány v hranatých závorkách, kdežto prvky kombinace jsou uzavˇreny ve složených množinových závorkách, aby se zdu˚ raznilo, že nezáleží na poˇradí prvku. ˚ Název funkce: void varprint(unsigned int *var) void varknprint(unsigned int *var, int k, int n) void combprint(unsigned int *comb) void combknprint(unsigned int *comb, int k, int n) 36
3.2. VARIACE A KOMBINACE Parametry: Parametr var (comb) je ukazatel na k-tici, která má být vytištˇena na standardní výstup.
Návratová hodnota: Žádná. #include<stdio.h> #include "comb.h" int main() { unsigned int *variace, *kombinace, k = 5, n = 8; variace = varalloc(k,n); varinit(variace); printf("\nVypis variace, kde zalezi na poradi prvku: \n"); varprint(variace); kombinace = comballoc(k,n); combinit(kombinace); printf("\nVypis kombinace, kde nezalezi na poradi prvku: \n"); combprint(kombinace); varfree(variace); combfree(kombinace); return 0; }
Pˇríklad 3.2.3: Pˇríklad použití funkce varprint a combprint
Výstup ukázkového pˇríkladu: Vypis variace, kde zalezi na poradi prvku: [0, 1, 2, 3, 4] Vypis kombinace, kde nezalezi na poradi prvku: {0, 1, 2, 3, 4}
3.2.7
Tisk variace, kombinace do proudu
Funkce umožnující ˇ uživateli zápis k-tice do specifikovaného proudu. Mimo k-tice lze do proudu zapsat i textový rˇ etˇezec, který bude umístˇen pˇred ní. 37
3.2. VARIACE A KOMBINACE Název funkce: int varfprint(FILE * stream, char * text, unsigned int *var) int combfprint(FILE * stream, char * text, unsigned int *comb) int varknfprint(FILE * stream, char * text, unsigned int *var, int k, int n) int combknfprint(FILE * stream, char * text, unsigned int *comb, int k, int n) Parametry: První parametr stream je ukazatel na objekt FILE, který urˇcuje proud pro výpis k-tice. Druhý parametr text tvoˇrí uvozovací textový rˇ etˇezec pˇred výpisem k-tice. Parametr var (comb) je ukazatel na k-tici, která má být vytištˇena do urˇceného proudu. Návratová hodnota: Poˇcet znaku, ˚ které se posílají do výstupního proudu, pokud nenastane chyba. V pˇrípadˇe výskytu chyby je vrácena hodnota EOF, která má ve vˇetšinˇe tradiˇcních implementacích hodnotu -1. #include<stdio.h> #include "comb.h" int main() { unsigned int *variace, k = 5, n = 8; FILE * pFile = NULL; pFile = fopen("varfprint_example.txt","w"); variace =varalloc(k,n); varinit(variace); permfprint(pFile,"nejmensi variace: ", variace); permfprint(pFile,"", variace); fclose(pFile); varfree(variace); return 0; }
Pˇríklad 3.2.4: Pˇríklad použití funkce varfprint
38
3.2. VARIACE A KOMBINACE Obsah souboru varfprint_example.txt: nejmensi variace: [0, 1, 2, 3, 4] [0, 1, 2, 3, 4]
3.2.8
Generování následující variace
Funkce varnext vytvoˇrí na adrese, která byla zadaná jako jediný vstupní parametr, minimálního lexikografického následníka k dané variaci. Opakovanou aplikací funkce lze generovat všechny lexikograficky uspoˇrádané variace. Další variace vznikne transpozicí dvou prvku. ˚ Bud’ jsou oba prohazované prvky souˇcástí k-tice a nacházejí se ve variaci, nebo se jeden z nich vyskytuje v k-tici (menší prvek) a druhý se tam nevyskytuje (vˇetší prvek). Pak je menší prvek z variace odstranˇen a naopak vˇetší prvek zaˇrazen mezi vybranou k-tici. Prvky, které nebyly zahrnuty do variace se nachází na indexech k až n − 1 (dále jen za variací), kdežto vybrané prvky tvoˇrící k-tici jsou v poli na indexech 0 až k − 1 (dále jen ve variaci). Samotnou transpozicí vznikne lexikograficky vˇetší variace, minimálního zvˇetšení dosáhneme pomocí vzestupného seˇrazení prvku˚ od pozice nalezeného menšího prvku až do konce. Podrobnˇejší popis seˇrazení i nalezení transpozice se nachází v sekci popis algoritmu. Název funkce: int varnext(unsigned int *var) int varknnext(unsigned int *var, int k, int n) Parametry: Parametr var je ukazatel na variaci, ze které se bude vytváˇret její následník. Návratová hodnota: Pokud existuje lexikograficky vˇetší variace, než která byla zadána jako vstupní parametr, je vrácena hodnota 1, v opaˇcném pˇrípadˇe je vrácena hodnota 0.
39
3.2. VARIACE A KOMBINACE Zdrojový kód: int varnext(unsigned int *p) { int i, pos, k = varsizeofk(p); for( i = k-1; i >= 0 ; i--) { /*zvetseni variace o prvek, ktery je za variaci*/ for( pos = k; pos < varsizeofn(p); pos++) { if( (p[i] < p[pos]) ) { swap_and_sort(p, i, pos); return 1; } } /* nepodarilo se zvetsit variaci prvkem za variaci */ /* zkousime ji tedy zvetsit prvkem ve variaci */ for( pos = k-1; pos > i; pos--) { if( (p[i] < p[pos]) ) { swap_and_sort(p, i, pos); return 1; } } } /* zadna dalsi variace neexistuje, je vracena 0 */ return 0; } void swap_and_sort(unsigned int *p, int i, int pos) { int dm, hm; /* swap */ p[i] ^= p[pos]; p[pos] ^= p[i]; p[i] ^= p[pos]; /* reverse prvku za variaci*/
40
3.2. VARIACE A KOMBINACE hm = varsizeofn(p)-1; for( dm = varsizeofk(p); dm < hm; dm++,hm--) { p[hm] ^= p[dm]; p[dm] ^= p[hm]; p[hm] ^= p[dm]; } /* reverse vsech prvku od pozice mensiho prvku az do konce */ hm = varsizeofn(p)-1; for( dm = i+1; dm < hm; dm++,hm--) { p[hm] ^= p[dm]; p[dm] ^= p[hm]; p[hm] ^= p[dm]; } }
Použité promˇenné: Promˇenná pos je index prvku pole, jenž má být prohozen s jiným prvkem tak, aby došlo ke zvˇetšení variace. Pod indexem i hledáme v poli menší prvek než je na pozici pos. Pˇri nalezení této dvojice jsou prvky s indexy i a pos vzájemnˇe prohozeny. V poli pod indexem k je umístˇen první prvek, který nebyl vybrán a tedy se ve variaci nevyskytuje. Indexy dm a hm oznaˇcují poˇcáteˇcní a koncový úsek pole, který bude seˇrazen.
Popis algoritmu: Nejprve se snažíme zvˇetšit pozici posledního prvku ve variaci zámˇenou s vetším prvkem za variací. Prvky za variací jsou uspoˇrádány vzestupnˇe, takže porovnávání probíhá postupnˇe od indexu k do n-1. Pokud nelze provést žádnou zámˇenu, posuneme se o jednu pozici doleva na pˇredposlední prvek ve variaci a ten opˇet porovnáváme s prvky za variací. Zde už pˇri neexistenci vˇetšího prvku za variací zkoušíme provést zámˇenu i s prvky nacházející se ve variaci za ním (v tomto pˇrípadˇe pouze s posledním prvkem) viz následující obrázek. Tento postup opakujeme dokud nenalezneme dva prvky, které lze prohodit. U maximální variace se už žádné takové dva prvky nenacházejí a proto nedojde ke zmˇenˇe a algoritmus konˇcí. 41
3.2. VARIACE A KOMBINACE
Jakmile nalezneme správnou dvojici prvku, ˚ prohodíme je a seˇradíme sekvenci za menším z nalezených prvku˚ (prvek na indexu i). K tomu slouží pomocná funkce swap_and_sort, ˇ jejíž druhý a tˇretí parametr obsahuje indexy prohazovaných prvku. ˚ Razení probíhá nadvakrát, nejprve seˇradíme prvky za variací tak, aby byla sekvence sestupná místo vzestupná. A poté následuje vzestupné rˇ azení všech prvku˚ od indexu˚ i+1 až n-1. Seˇrazením jsem dosáhli vytvoˇrení nejmenšího lexikografického následníka puvodní ˚ variace.
ˇ Casová složitost v nejhorším pˇrípadˇe: ˇ Casová složitost pomocné funkce swap_and_sort je 1 + (n−k)/2 + (n−1)/2. Poˇcet porovnání je
P
(n − k + i) kde 0 ≤ i ≤ k−1.
42
3.2. VARIACE A KOMBINACE #include<stdio.h> #include "comb.h" int main() { unsigned int *variace, k = 3, n = 4, count = 0; variace = varalloc(k,n); varinit1(variace); printf("Vypis vsech variaci radu %d ze %d prvku: \n",k,n); do{ varprint(variace); count++; } while( varnext(variace) ); varfree(variace); printf("Celkovy pocet variaci radu %d ze %d prvku je %d.\n", k,n,count); return 0; }
Pˇríklad 3.2.5: Pˇríklad použití funkce varnext Výstup ukázkového pˇríkladu (výpis po sloupcích): Vypis vsech variaci radu 3 ze 4 prvku: [1, [1, [1, [1, [1, [1,
2, 2, 3, 3, 4, 4,
3] 4] 2] 4] 2] 3]
[2, [2, [2, [2, [2, [2,
1, 1, 3, 3, 4, 4,
3] 4] 1] 4] 1] 3]
[3, [3, [3, [3, [3, [3,
1, 1, 2, 2, 4, 4,
2] 4] 1] 4] 1] 2]
[4, [4, [4, [4, [4, [4,
1, 1, 2, 2, 3, 3,
2] 3] 1] 3] 1] 2]
Celkovy pocet variaci radu 3 ze 4 prvku je 24.
3.2.9
Generování následující kombinace
Funkce combnext vytvoˇrí na adrese, která byla zadaná jako jediný vstupní parametr, minimálního lexikografického následníka k dané kombinaci. Opakovanou aplikací funkce na urˇcitou kombinaci lze generovat všechny její následníky v lexikograficky uspoˇrádaném poˇradí. U kombinací nezáleží na poˇradí prvku˚ a proto jsou kombinace {1, 2, 3} a {3, 2, 1} stejné. Aby bylo možné kombinace porovnat, nejprve se prvky kombinace vzestupnˇe seˇradí a poté 43
3.2. VARIACE A KOMBINACE probíhá lexikografické rˇazení podle definice uvedené v kapitole 3. 1. 11 Porovnání permutací. Takže napˇríklad kombinace {1, 2, 4} je vˇetší než kombinace {3, 1, 2}, protože 4 je vˇetší než 3. Pˇri generování funkcí combnext se nám automaticky vytváˇrí kombinace, jejíž prvky jsou uspoˇrádané, aby se pˇri porovnání kombinací nemusely rˇ adit. Algoritmus generování následující kombinace je naprosto odlišný od generování variací, kde byly prvky ve variaci porovnávány a pˇrípadnˇe prohazovány mezi sebou, nebo s prvky, jenž nebyly zahrnuty v k-tici. U variací nám zámˇena urˇcité podmnožiny prvku˚ zaruˇcila, že se žádný z nich nebude ve variaci opakovat a proto jsme nemuseli komplikovanˇe kontrolovat existenci prvku, který jsme chtˇeli do variace zaˇradit. U kombinací je situace jiná, pˇri generování všech lexikografických kombinací zjistíme, že každá z nich je v neklesajícím poˇradí. Tohoto faktu využijeme pˇri hledání prvku, ˚ které mají být vybrány do nové kombinace. Ke zvˇetšení kombinace nalezneme pozici co nejvíce vzadu, kam umístíme prvek o jedniˇcku vˇetší, což nám zaruˇcí, že na žádné pˇredchozí pozici se tento prvek nevyskytuje a dojde ke zvˇetšení kombinace. Nalezení ostatních prvku˚ za pozicí novˇe umístˇeného prvku je triviální. Aby nebylo porušeno vzestupné uspoˇrádání a navíc byly vybrané prvky minimální, je každý novˇe vybraný prvek o jedna vˇetší. Tím, že umíst’ujeme do kombinace pokaždé vˇetší prvek, nemuže ˚ dojít k vložení prvku vícekrát než jednou. Navíc nemusíme rˇ adit prvky (jako tomu bylo u variací), abychom vkládali ty nejmenší, ale staˇcí pˇriˇcítat jedniˇcku, což výpoˇcet velice urychlí. Název funkce: int combnext(unsigned int *comb) int combknnext(unsigned int *comb, int k, int n) Parametry: Parametr comb je ukazatel na kombinaci, ze které se bude vytváˇret následující kombinace. Návratová hodnota: Pokud existuje lexikograficky vˇetší kombinace, než která byla zadána jako vstupní parametr, je vrácena hodnota 1, v opaˇcném pˇrípadˇe je vrácena hodnota 0. Zdrojový kód: int combnext(int *p) { int i, j, k = varsizeofks(p), n = varsizeofns(p);
44
3.2. VARIACE A KOMBINACE
for( i = k-1; i >= 0 ; i-- ) { /* hledani prvku na pozici i, ktery zvedneme o jedna */ if( p[i] < n && ( p[i] + 1 ) + ( k - 1 - i ) <= n ) { p[i] = p[i] + 1; /* zvetseni prvku za nalezenym */ for( j = i + 1; j < k; j++ ) { p[j] = p[j-1] + 1; } return 1; } } /* zadna dalsi kombinace neexistuje, je vracena 0 */ return 0; }
Použité promˇenné: V poli hledáme prvek s indexem i , zvˇetšením prvku na nalezené pozici vytvoˇríme vˇetší kombinaci než puvodnˇ ˚ e byla. Promˇenné k a n jsou parametry kombinace. Na indexu k − 1 se nachází poslední prvek kombinace. Popis algoritmu: Od konce kombinace (posledního prvku) hledáme pozici i, na kterou když umístíme prvek o jedna vˇetší, bude stále menší nebo roven nejvˇetšímu možnému prvku kombinace. Pokud na tuto pozici lze vložit vˇetší prvek, musíme ještˇe zkontrolovat, zda budeme schopni vložit i zbylých k − i − 1 vˇetších prvku˚ tak, aby žádný z nich nebyl vˇetší než nejvˇetší možný prvek kombinace. Naplnˇení zbytku kombinace od pozice i + 1 je rˇ ešen vkládáním prvku vždy o jedna vˇetší než je jeho pˇredchudce. ˚ ˇ Casová složitost v nejhorším pˇrípadˇe: Poˇcet porovnání bude v nejhorším pˇrípadˇe roven k. Tato situace nastane, když budeme zvˇetšovat prvek na první pozici. 45
3.2. VARIACE A KOMBINACE Poˇcet pˇrístupu do pamˇeti urˇcuje pozice prvního zvˇetšovaného prvku, protože pak následnˇe budeme zvˇetšovat i prvky na všech pozicích za ním. Nejhorší pˇrípad opˇet nastává pokud je nalezený prvek s indexem i na první pozici v k-tici. Poˇcet pˇrístupu do pamˇeti je pak taktéž roven k. Pamˇet’ová nároˇcnost: K vygenerování všech kombinací slouží pouze blok pamˇeti obsahující k + 2 položek daného datového typu. Generováním další kombinace nedochází k nové alokaci pamˇeti, ale jenom ke zmˇenˇe položek na již jednou alokovaném bloku. #include<stdio.h> #include "comb.h" int main() { unsigned int *kombinace, k = 3, n = 6, count = 0; kombinace = varalloc(k,n); varinit1(kombinace); printf("Vypis vsech kombinaci radu %d ze %d prvku: \n",k,n); do{ varprint(kombinace); count++; }while( combnext(kombinace) ); combfree(kombinace); printf("Celkovy pocet vsech kombinaci radu %d ze %d prvku je %d.\n", k,n,count); return 0; }
Pˇríklad 3.2.6: Pˇríklad použití funkce combnext
Výstup ukázkového pˇríkladu (výpis po sloupcích): Vypis vsech kombinaci radu 3 ze 6 prvku: [1, [1, [1, [1, [1,
2, 2, 2, 2, 3,
3] 4] 5] 6] 4]
[1, [1, [1, [1, [1,
3, 3, 4, 4, 5,
5] 6] 5] 6] 6]
[2, [2, [2, [2, [2,
3, 3, 3, 4, 4,
4] 5] 6] 5] 6]
[2, [3, [3, [3, [4,
5, 4, 4, 5, 5,
6] 5] 6] 6] 6]
Celkovy pocet vsech kombinaci radu 3 ze 6 prvku je 20.
46
3.2. VARIACE A KOMBINACE 3.2.10 Kopírování variace, kombinace V pˇrípadˇe potˇreby vytvoˇrit kopii variace (kombinace) lze využít funkce varcopy (combcopy). Pˇri jejím zavolání dojde k alokaci pamˇeti, zkopírování všech prvku˚ puvodní ˚ k-tice do novˇe alokovaného bloku a následnˇe je vrácena adresa zkopírované k-tice. Název funkce: unsigned int *varcopy(unsigned int *var) unsigned int *varkncopy(unsigned int *var, int k, int n) unsigned int *combcopy(unsigned int *comb) unsigned int *combkncopy(unsigned int *comb, int k, int n) Parametry: Parametr var (comb) je ukazatel na k-tici, z níž se bude vytváˇret kopie. Návratová hodnota: Ukazatel na novˇe vytvoˇrenou kopii puvodní ˚ k-tice. 3.2.11 Dealokace variace, kombinace Funkce varfree a combfree uvolní pamˇet’ alokovanou funkcemi varalloc a comballoc. Název funkce: void varfree(unsigned int *var) void combfree(unsigned int *comb) Parametry: Parametr var (comb) je ukazatel na variaci (kombinaci), která má být z pamˇeti uvolnˇena. Návratová hodnota: Žádná.
47
Kapitola 4
Praktické ukázky V této kapitole si ukážeme, jak se funkce z naší kombinatorické knihovny dají použít na praktických pˇríkladech. Jako možné využití funkce permnext se nabízí pˇri rˇešení problému obchodního cestujícího, kde je potˇreba projít všechny cesty v grafu. Tato funkce je použitelná i pro výpoˇcet determinantu matice podle její definice. A na závˇer si ukážeme, jak se dají šifrovat zprávy pomocí cyklického posunu permutace. Ukázky mají pouze ilustrativní charakter, pro efektivní rˇ ešení nˇekterých z tˇechto problému˚ existují vhodnˇejší zpusoby ˚ rˇ ešení. My si ukazujeme, jak lze dojít k výsledkum ˚ jinou cestou, s použitím funkcí z naší kombinatorické knihovny.
4.1
Problém obchodního cestujícího
Známý problém obchodního cestujícího je formulován takto: Je dána množina M a pro každé dva její prvky x, y je dáno cˇ íslo d(x,y), které budeme nazývat vzdáleností x a y. Pro jednoduchost budeme pˇredpokládat, že d je metrika, tj. d(x, y) ≥ 0 pro každé x, y a rovnost platí pouze je-li x = y, d(x, y) = d(y, x) pro každé x, y, d(x, y) + d(y, z) ≥ d(x, z) pro každé x, y, z (trojúhelníková nerovnost). Cílem je urˇcit, v jakém poˇradí má obchodní cestující projet prvky množiny M („mˇesta“) tak, aby prošel každým právˇe jednou a pak se vrátil do místa, kde cestu zaˇcal, a urazil pˇri tom vzdálenost co možná nejmenší. [9]. Tato úloha patˇrí mezi NP-úplné úlohy, tzn. v obecném pˇrípadˇe není známo ani jak nalézt pˇresné rˇ ešení v rozumném cˇ ase a dokonce ani zda vubec ˚ muže ˚ existovat algoritmus, který takové rˇ ešení najde v cˇ ase úmˇerném nˇejaké mocninˇe poˇctu uzlu˚ [10]. Na rozdíl od praxe, kde se takovéto problémy rˇ eší pouze pˇribližnˇe z duvod ˚ u˚ snížení výpoˇcetního cˇ asu, využijeme funkce permnext k nalezení pˇresného rˇ ešení hrubou silou. Nejprve vybereme bod, z kterého budeme graf procházet a do nˇehož se máme opˇet vrátit. Vybraný bod bude vždy prvním prvkem permutace a proto ho není tˇreba permutovat. 48
4.1. PROBLÉM OBCHODNÍHO CESTUJÍCÍHO Tento bod vytkneme z permutace funkcí perminitex a permutovat budeme jen zbylých n − 1 bodu. ˚ Nejkratší cestu si prubˇ ˚ ežnˇe ukládáme do pomocné permutace a tu pak nakonec vypíšeme na standardní výstup. Složitost nalezení nejkratší cesty je rovna (n − 1)!.
#include<stdio.h> #include "comb.h" int main() { int j, n = 5, min_d = INT_MAX, cesta_d = 0; int d[n][n]; unsigned int *cesta = NULL, *min_cesta = NULL, start; d[0][0] d[1][0] d[2][0] d[3][0] d[4][0]
= = = = =
1; 1; 1; 1; 2;
d[0][1] d[1][1] d[2][1] d[3][1] d[4][1]
= = = = =
1; 0; 2; 2; 2;
d[0][2] d[1][2] d[2][2] d[3][2] d[4][2]
= = = = =
1; 2; 0; 1; 3;
d[0][3] d[1][3] d[2][3] d[3][3] d[4][3]
= = = = =
1; 2; 1; 0; 2;
d[0][4] d[1][4] d[2][4] d[3][4] d[4][4]
= = = = =
2; 2; 3; 2; 0;
cesta = permalloc(n); printf("Zadejte pocatecni bod: "); scanf("%u",&start); perminitex(cesta, start);
49
4.1. PROBLÉM OBCHODNÍHO CESTUJÍCÍHO do { cesta_d += d[start][cesta[0]]; for( j = 0; j < n-2; ) { cesta_d += d[cesta[j]][cesta[j+1]]; j++; } cesta_d += d[cesta[j]][start]; if( cesta_d <= min_d ) { if(min_cesta != NULL) { permfree(min_cesta); } min_cesta = permcopy(cesta); min_d = cesta_d; } cesta_d = 0; } while( permnext(cesta) ); printf("Nejkratsi cesta o vzdalenosti %d vede po trase:\n%d ->",min_d,start); for( j = 0; j < permsizeof(min_cesta); j++ ) { printf(" %d ->", min_cesta[j]); } printf(" %d\n", start); permfree(cesta); permfree(min_cesta); return 0; }
Pˇríklad 4.1.1: Pˇríklad hledání nejkratší cesty z vybraného bodu:
Výstup programu: Zadejte pocatecni bod: 3 Nejkratsi cesta o vzdalenosti 7 vede po trase: 3 -> 4 -> 1 -> 0 -> 2 -> 3
50
ˇ 4.2. VÝPO CET DETERMINANTU MATICE
4.2
Výpoˇcet determinantu matice
Determinantem matice A n-tého rˇ ádu nazýváme cˇ íslo P
z(P) a1k1 a2k2 ... ankn ,
kde P =
1 2 3 ··· n k1 k2 k3 · · · kn je permutace množiny Un = {1, 2, ..., n }, z(P) je znaménko pˇríslušné permutace a kde sˇcítáme pˇres všech n! souˇcinu, ˚ pˇriˇcemž n! je poˇcet všech permutací množiny Un [5]. Pro výpoˇcet determinantu podle definice si nejprve vytvoˇríme permutaci funkcí permalloc, dále ji inicializujeme funkcí perminit. Nyní již použijeme funkce permnext k vygenerování všech permutací. Ke každé permutaci si spoˇcítáme její znaménko funkcí permsgn a ˇ vypoˇcítáme cˇ len determinantu z dvourozmˇerného pole reprezentující matici. Clen determinantu je souˇcinem znaménka permutace a prvku˚ matice, jejíž indexy sloupcu˚ nám udávají prvky permutace. Provedeme souˇcet všech cˇ lenu˚ determinantu pˇres všechny permutace a výsledkem je determinant matice. Determinant matice muže ˚ být spoˇcítán více zpusoby, ˚ než podle definice se složitostí n!. Nˇekteré z nich mají složitost n3 , proto berme tento zpusob ˚ výpoˇctu spíše jako ukázku, jak relativnˇe jednoduše vypoˇcítat determinant matice, než jako efektivní zpusob ˚ výpoˇctu. #include<stdio.h> #include "comb.h" int main() { unsigned int *permutace, n = 4, sum = 0, znamenko, i, clen_det; int A[n][n]; /* matice A[0][0] = A[1][0] = A[2][0] = A[3][0] =
pro vypocet determinantu */ 1; A[0][1] = 2; A[0][2] = 3; 2; A[1][1] = 4; A[1][2] = 1; 4; A[2][1] = 2; A[2][2] = 1; 3; A[3][1] = 1; A[3][2] = 2;
A[0][3] A[1][3] A[2][3] A[3][3]
= = = =
3; 4; 2; 1;
51
4.3. ŠIFROVÁNÍ KOMUNIKACE permutace = permalloc(n); perminit(permutace); /* vypocet determinatnu matice pres vsechny permutace */ do{ /* urceni znamenka permutace */ znamenko = permsgn(permutace); /* vypocet clenu determinantu pres permutaci */ clen_det = 1; for( i = 0; i < n; i++ ) { clen_det *= A[i][permutace[i]]; } /* soucet vsech clenu determinantu */ sum += znamenko*clen_det; }while( permnext(permutace) ); permfree(permutace); printf("det(A) = %d.\n",sum); return 0; }
Pˇríklad 4.2.1: Pˇríklad výpoˇctu determinantu matice :
Výstup programu: det(A) = 16.
4.3
Šifrování komunikace
Mˇejme následující situaci: Alice (dále jen A) a Bob (dále jen B) chtˇejí spolu komunikovat pomocí zpráv a není žádoucí, aby se jakákoli tˇretí osoba dozvˇedˇela obsah jejich korespondence. Komunikace bude probíhat pomocí známe metody DHM (podle svých objevitelu˚ Diffie, Hellman, Merkle), která je ilustrována na obrázku níže. Posílaná zpráva je uložena do truhly chránˇené dvˇema visacími zámky. První zámek na truhlu povˇesí odesílatel A, jehož klíˇc má pouze on. Následnˇe je uzamˇcená truhla poslána pˇríjemci B, který na truhlu zavˇesí svuj ˚ zámek a truhlu se zprávou pošle odesílateli A nazpˇet (na truhle jsou nyní dva zámky). Ten odemkne svuj ˚ zámek a znovu pošle truhlu k pˇríjemci B. Pˇríjemce B obdrží truhlu, na které je pouze jeho zámek, takže ji odemkne a pˇreˇcte si v ní uloženou zprávu. 52
4.3. ŠIFROVÁNÍ KOMUNIKACE
Ke zprávˇe se nemohl dostat nikdo jiný, protože na truhle byl vždy alesponˇ jeden zámek a obsah byl tedy dobˇre chránˇen. Ovšem na doruˇcení jedné zprávy musela být zpráva mezi odesílatelem a pˇríjemcem poslána tˇrikrát, dvakrát zašifrována a dvakrát dešifrována. Celková nároˇcnost tedy není optimální, ale s využitím dnešních poˇcítaˇcu˚ to není nepˇrekonatelný problém. Tato metoda se spíše používá pro pˇredání klíˇce, než-li pro bˇežnou komunikaci. Otázkou je, jak nalézt šifry, u kterých nezáleží na poˇradí šifrování a dešifrování jako tomu je pˇri zamykání a odemykání visacích zámku. ˚ Hledáme tedy podmnožinu permutací, pro kterou platí: A-1 (A(t)) = t, B-1 (B(t)) = t, B-1 (A-1 (B(A(t)))) = t, kde t je puvodní ˚ zpráva, A je zašifrování odesílatelkou A, B zašifrování pˇríjemcem B a A-1 odšifrování odesílatelkou A, B-1 odšifrování pˇríjemcem B. Nejjednodušší podmnožinou permutací splnující ˇ výše uvedenou podmínku je cyklický posun o k (0 ≤ k < n) míst doprava a k nˇemu inversní je cyklický posun o stejné k doleva a tedy n − k doprava. Jak odesílatel, tak pˇríjemce vlastní svuj ˚ ad hoc privátní klíˇc, pomocí nˇehož cyklicky posune zprávu o urˇcitý poˇcet míst doprava. Tyto privátní klíˇce by se mˇenily pˇri každém poslání nové zprávy. Pˇri šifrování zprávy délky m by existovalo pouze m možností, jak zprávu zašifrovat (zprávu cyklicky posunout o 0 až m − 1 míst). V tomto pˇrípadˇe by dešifrování zprávy pˇri znalosti algoritmu bylo velice snadné. Ke zvýšení bezpeˇcnosti je potˇreba rozdˇelit zprávu na více úseku˚ a ty následnˇe posunout, každý zvlášt’ o ruzný ˚ poˇcet míst. Nejvˇetší poˇcet možností, jak muže ˚ být zpráva zašifrována nastává pˇri úsecích délky 3, což je vidˇet na následujícím pˇríkladˇe, kde m znaˇcí velikost zprávy a n velikost úseku. m = 12, n = 12: 12 posunu˚ = 12 možností, m = 12, n = 3: 3 posuny * 3 posuny * 3 posuny * 3 posuny = 81 možností, m = 12, n = 4: 4 posuny * 4 posuny * 4 posuny = 64 možností, 53
4.3. ŠIFROVÁNÍ KOMUNIKACE m = 12, n = 2: 2 posuny * 2 posuny * 2 posuny * 2 posuny * 2 posuny * 2 posuny = 64 možností. Formálnˇeji vypoˇcítáme délku úseku pomocí derivace, kterou položíme rovnu nule, aby pocˇ et možností byl maximální. Výpoˇcet vypadá takto: y = nm/n y = eln n
(m/n)
y = em/n ln n 2 * ln n + m/n * 1/n)
y’ = em/n ln n * (−m/n
y’ = nm/n * (1 − ln n) * (m/n2 ) y’ = 0 ⇔ 1 − ln n = 0 ⇔ n = e a potom nejbližší celé cˇ íslo k e je 3. Tím se nám tedy zvýšil poˇcet možností, jak muže ˚ být zpráva zašifrována. Když navíc útoˇcník nebude znát, jaké trojice položek zprávy mají být spoleˇcnˇe cyklicky posunuty, dešifrování zprávy bude mít ještˇe obtížnˇejší. Urˇcení trojic posouvaných prvku˚ zprávy je urˇceno sdíleným klíˇcem, který má komunikující dvojice spoleˇcný. S využitím sdíleného klíˇce navíc zabráníme tzv. útoku muže uprostˇred. Pokud by se totiž útoˇcník dostal k zašifrované zprávˇe, zašifroval by zprávu jakýmkoliv klíˇcem a odesílatel by nemˇel šanci zjistil, zda byla zpráva zašifrována správným pˇríjemcem. Když ale útoˇcník nebude znát sdílený klíˇc, nebude schopen zašifrovat ty správné trojice a tedy se nemá možnost dozvˇedˇet správné znˇení zprávy. Pro útoˇcníka je nutné znát algoritmus šifrování a hlavnˇe sdílený klíˇc, který se pro zvýšení bezpeˇcnosti také cˇ as od cˇ asu zmˇení. Jeho délka musí být shodná s délkou zprávy. V praxi by se posílaly zprávy jednotné délky 256 bajtu, ˚ kratší zprávy by byly doplnˇeny do této velikosti bud’ tzv. solí (nadbyteˇcnou informací), jejíž hranice od pˇrenášené informace by musela být oddˇelena speciálním ukonˇcovacím znakem. A nebo by za zprávu byly doplnˇeny samé nuly. My si pro jednoduchost ukážeme šifrování krátké zprávy délky 9 se spoleˇcným klíˇcem stejné délky. Nyní si ukážeme, jak probíhá samotné šifrování zprávy. Nejprve nalezneme trojice, které budeme spoleˇcnˇe cyklicky posouvat. Jejich pozice ve zprávˇe zjistíme ze sdíleného klíˇce tak, že každá trojice cˇ ísel zleva nám udává indexy posouvaných trojic ve zprávˇe. Jakmile známe správné trojice, posuneme je o urˇcité poˇcty míst doleva, cˇ i doprava podle privátního klíˇce uživatele (jeho permutace). Namapované trojice jsou pˇri šifrování cyklicky posunuty funkcí permshiftr o k míst doprava a dešifrovány stejnou funkcí o n − k míst také doprava, což je ekvivalentní cyklickému posunu o k míst doleva.
54
4.3. ŠIFROVÁNÍ KOMUNIKACE
#include<stdio.h> #include "comb.h" void sifrovani(unsigned int *zprava, unsigned int *priv, unsigned int *sdil, int sifr) { int i, j, posun; unsigned int *map_pole; map_pole = permalloc(3); for( j = 0, i = 0; i < 9; i+= 3,j++) { /* namapovani trojice ve zprave */ map_pole[0] = zprava[sdil[i]]; ++i; map_pole[1] = zprava[sdil[i]]; ++i; map_pole[2] = zprava[sdil[i]]; /* (de)sifrovani pomoci posunu o urcitou polozku privatniho klice */ posun = (sifr == 1) ? priv[j] : 3 - priv[j]; permshiftr(map_pole, posun); zprava[sdil[i]] = map_pole[2]; --i; zprava[sdil[i]] = map_pole[1]; --i; zprava[sdil[i]] = map_pole[0]; } permfree(map_pole); }
55
4.3. ŠIFROVÁNÍ KOMUNIKACE int main() { unsigned unsigned unsigned unsigned int j;
int int int int
zprava[] = {1,2,3,4,5,6,7,8,9}; sdileny_klic[] = {0,2,5, 1,3,4, 6,7,8}; privatni_klic1[] = {1,2,1}; privatni_klic2[] = {1,2,2};
printf("Puvodni zprava (t): "); for( j = 0; j < 9; j++ ) { printf("%d ", zprava[j]); } /* zasifrovani odesilatele A jejim privatnim klicem */ sifrovani(zprava, privatni_klic1, sdileny_klic, 1); printf("\nZasifrovano (dA(t)): "); for( j = 0; j < 9; j++ ) { printf("%d ", zprava[j]); } /* zasifrovani prijemce B jeho privatnim klicem */ sifrovani(zprava, privatni_klic2, sdileny_klic, 1); printf("\nZasifrovano (dB(dA(t))): "); for( j = 0; j < 9; j++ ) { printf("%d ", zprava[j]); } /* odsifrovani odesilatele A jejim privatnim klicem */ sifrovani(zprava, privatni_klic1, sdileny_klic, 0); printf("\nOdsifrovano (dB(t)): "); for( j = 0; j < 9; j++ ) { printf("%d ", zprava[j]); } /* zasifrovani prijemce B jeho privatnim klicem */ sifrovani(zprava, privatni_klic2, sdileny_klic, 0); printf("\nOdsifrovano (t): "); for( j = 0; j < 9; j++ ) { printf("%d ", zprava[j]); } printf("\n"); return 0; }
Pˇríklad 4.3.1: Pˇríklad šifrované komunikace : Výstup programu: Puvodni zprava (t): Zasifrovano (dA(t)): Zasifrovano (dB(dA(t))): Odsifrovano (dB(t)): Odsifrovano (t):
1 6 3 6 1
2 4 5 4 2
3 1 6 1 3
4 5 2 5 4
5 2 4 2 5
6 3 1 3 6
7 9 7 8 7
8 7 8 9 8
9 8 9 7 9
56
Kapitola 5
Závˇer Kombinatorická knihovna, kterou jsem vytvoˇril, muže ˚ být nyní používána pˇri programování v jazyce C. Funkce jsou otestovány testovacími soubory perm_test.c, var_test.c a comb_test.c, což nám zaruˇcuje jejich bezchybnost. K lepšímu porozumˇení a seznámení se s funkcemi naší kombinatorické knihovny byla vytvoˇrena manuálová webová stránka v cˇ eském jazyce. Jako rozšíˇrení bakaláˇrské práce se nabízí pˇreložení dokumentace i do anglického jazyka pro ostatní uživatele.
57
Literatura [1] C Standard Library [online]. 30. 11. 2006, [cit. 15. 11. 2009]. Dostupné na:
. [2] Kernighan, B., Ritchie, D. Programovací jazyk C. New Jersey: Prentice Hall, 1988. ISBN 80-251-0897-X. [3] Deitel, H., Deitel, P. C How To Program, Third Edition. New Jersey: Prentice Hall, 2001. ISBN 0-13-089572-5. ˇ [4] Herout, P. Uˇcebnice jazyka C - 2. díl. Ceské Budˇejovice: KOPP, 1998. ISBN 80-85828-502. [5] Bartsch, H. Matematické vzorce. Praha: Academia, 2006. ISBN 80-200-1448-9. [6] Harbison, S., Steele, G. Referenˇcní pˇríruˇcka jazyka C. New Jersey: Prentice Hall, 1996. ISBN 80-901475-50. [7] Wilf, H., Nijenhuis, A. Computer science and applied mathematics. Combinatorial algorithms for computers and calculators (Second Edition). 1931-. London: ACADEMIC PRESS. ISBN 0-12-51-9260-6. [8] Wikipedie, Otevˇrená encyklopie: Lexikografické uspoˇrádání [online]. 26. 12. 2009, [cit. 28. 4. 2010]. Dostupné na: . [9] Kuˇcera, L. Kombinatorické algoritmy. Praha: SNTL – Nakladatelství technické literatury, 1983. ISBN 04-009-83. [10] Wikipedie, Otevˇrená encyklopie: Problém obchodního cestujícího [online]. 27. 3. 2009, [cit. 3. 5. 2010]. Dostupné na: .
58
