Diskrétní matematika

Antonín Slavík
Matematicko-fyzikální fakulta UK

Permutace, variace, kombinace

Permutace

Permutace bez opakování:

Permutations[{a,b,c,d}]

Permutace s opakováním:

Permutations[{a,a,b,c,c}]

Jejich počet:

?Multinomial

Multinomial[2,1,2]

Variace

Variace bez opakování:

Permutations[{a,b,c,d,e},{3}]

Jejich počet:

FactorialPower[n,k] vrací n(n-1)⋯(n-k+1).

FactorialPower[5,3]

Obecněji, pro x∈ℝ a k∈ℕ zavedeme označení (x^(UnderBar[k]))=x(x-1)⋯(x-k+1), a dále dodefinujeme (x^(UnderBar[0]))=1. Těmto číslům se říká sestupné mocniny.

Variace s opakováním:

Tuples[{a,b,c,d},3]

Kartézský součin:

Tuples[{{a,b,c},{1,2,3}}]

Kombinace

Kombinace bez opakování:

Subsets[{a,b,c,d,e},{3}]

Jejich počet:

Binomial[5,3]

Pascalův trojúhelník:

TableForm[Table[Binomial[n,k],{n,0,10},{k,0,n}]]

Všechny podmnožiny:

Subsets[{a,b,c,d}]

Kombinace s opakováním (najdeme variace s opakováním, odstraníme duplikáty):

Union[Map[Sort,Tuples[{a,b,c,d,e},3]]]

Jiné řešení: IntegerPartitions[m,{k},seznam] najde všechny rozklady přirozeného čísla m na k sčítanců, přičemž hodnoty sčítanců jsou ze zadaného seznamu a nezáleží na jejich pořadí. 
Neuspořádané k-tice sestavené z prvků množiny {1,...,n} lze chápat jako rozklady přirozených čísel počínaje k a konče k·n na k přirozených sčítanců s hodnotami ze seznamu {1,...,n}.

kombinaceSOpakovanim[n_,k_]:=Join@@Table[IntegerPartitions[m,{k},Range[n]],{m,k,n k}]

kombinaceSOpakovanim[5,3]

Chceme-li kombinace vybírat z jiné množiny než {1,...,n}, použijeme substituci:

%/.Thread[{1,2,3,4,5}->{a,b,c,d,e}]

Stirlingova čísla

Stirlingova čísla druhého druhu

Kolika způsoby lze rozdělit množinu {1,…,n} na k neprázdných podmnožin?

Needs["Combinatorica`"]

KSetPartitions[Range[3],2]

KSetPartitions[Range[5],3]

Grid[%]

Length[%%]

StirlingS2[5,3]

Stirlingův trojúhelník druhého druhu:

TableForm[Table[StirlingS2[n,k],{n,1,10},{k,1,n}]]

Quit[]

Stirlingova čísla prvního druhu

Každou permutaci lze rozložit na cykly. Např. permutace {2,4,3,1,6,8,5,7} vypadá takto:

GraphPlot[{1->2,2->4,3->3,4->1,5->6,6->8,7->5,8->7},DirectedEdges->True,BaseStyle->14,VertexLabeling->True,ImageSize->Small,PlotStyle->Arrowheads[{{Medium,0.6}}]]

Tento rozklad zapíšeme ve tvaru {{1,2,4},{3},{5,6,8,7}}.

Úloha. Najděte všechny permutace množiny {1, …, n} tvořené právě k cykly.

Prvky 1,…,n-1 jsou rozděleny do k-1 cyklů, k-tý cyklus obsahuje pouze n.

Prvky 1,…,n-1 jsou rozděleny do k cyklů, prvek n je přidán do některého z nich.

(* Vloží x postupně na všechny možné pozice v cyklu c *)
vlozDoCyklu[c_,x_]:=Table[Insert[c,x,i],{i,1,Length[c]}]

vlozDoCyklu[{1,2},x]

(* Vloží x postupně do všech cyklů v permutaci p *)
vlozDoPermutace[p_,x_]:=Join@@Table[Map[ReplacePart[p,i->#]&,vlozDoCyklu[p[[i]],x]],{i,1,Length[p]}]

vlozDoPermutace[{{1,2},{3}},x]

permutace[n_,0]:={}
permutace[n_,k_]:={}/;k>n
permutace[1,1]:={{{1}}}
permutace[n_,k_]:=Join[Map[Append[#,{n}]&,permutace[n-1,k-1]],
Join@@Map[vlozDoPermutace[#,n]&,permutace[n-1,k]]]

permutace[3,2]//Grid

permutace[5,3]

Grid[%]

Length[%%]

StirlingS1[n,k] vrací (((-1))^(n-k)) krát počet permutací n-prvkové množiny s k cykly.

StirlingS1[5,3]

Poznámka: Definice Stirlingových čísel prvního druhu jsou nejednotné, faktor (((-1))^(n-k)) se někdy vynechává.

Stirlingův trojúhelník prvního druhu:

TableForm[Table[Abs[StirlingS1[n,k]],{n,1,10},{k,1,n}]]

Další použití Stirlingových čísel

(x^0), (x^1), …, (x^n) tvoří bázi prostoru všech polynomů stupně nejvýše n.

(x^(UnderBar[0])), (x^(UnderBar[1])), …, (x^(UnderBar[n])) je rovněž bází tohoto prostoru.

Matice přechodu mezi těmito bázemi jsou tvořeny Stirlingovými čísly:

({{({{(x^(UnderBar[k]))=(∑_(m=0)^k)StirlingS1[k,m](x^m)}}),}})

({{({{(x^k)=(∑_(m=0)^k)StirlingS2[k,m](x^(UnderBar[m]))}}).}})

Příklad:

FunctionExpand[FactorialPower[x,7]]

Expand[%]

Table[StirlingS1[7,m],{m,0,7}]

Další kombinatorické posloupnosti čísel

Fibonacciova čísla (Fibonacci), Catalanova čísla (CatalanNumber), Eulerova čísla (EulerE), Bernoulliova čísla (BernoulliB), Bellova čísla (BellB), …

Posloupnosti, diskrétní kalkulus

Posloupnosti

Řešení rekurentních rovnic:

RSolve[a[n]==2a[n-1]+1,a[n],n]

RSolve[{a[n]==2a[n-1]+1,a[1]==1},a[n],n]

RSolve[{a[n]==a[n-1]+a[n-2],a[1]==1,a[2]==1},a[n],n]

FunctionExpand[Fibonacci[n]]

Uhodnutí vzorce na základě počátečních členů:

FindSequenceFunction[{1,4,9,16,25},n]

FindSequenceFunction[{2,4,7,11,16},n]

FindSequenceFunction[{1,1,2,3,5,8},n]

Další pokusy:

FindSequenceFunction[{1,2,3,5,6,7},n]

FindSequenceFunction[{1,2,3,5,6,7,9,10,11},n]

Diskrétní kalkulus

Diskrétní kalkulus je analogií diferenciálního a integrálního počtu, místo funkcí pracuje s posloupnostmi. Základní dvě operace jsou diference a antidiference (neurčitá suma).

Diference: Δ(Subscript[a, n])=(Subscript[a, n+1])-(Subscript[a, n])

DifferenceDelta[a[n],n]

Ekvivalentní zápis (EscdiffdEsc):

(Subscript[∆, n])a[n]

Diference vyšších řádů:

Map[Reverse,Table[DifferenceDelta[a[n],{n,k}],{k,1,8}]]//TableForm

DifferenceDelta[n,n]

DifferenceDelta[n^2,n]

DifferenceDelta[n^3,n]

Analogií klasického vzorce (d/(dx))((x^a))=a·(x^(a-1)) je ∆(n^(UnderBar[a]))=a·(n^(UnderBar[a-1])).

DifferenceDelta[FactorialPower[n,a],n]

Antidiference posloupnosti (Subscript[a, n]) je posloupnost (Subscript[b, n]) taková, že ∆(Subscript[b, n])=(Subscript[a, n]). 
Označení: (Subscript[b, n])=(∑_n)(Subscript[a, n]) (neurčitá suma)
(Subscript[b, n]) není určena jednoznačně (lze přičíst konstantní posloupnost).

DifferenceDelta[n^2,n]

Sum[%,n]

Analogií klasického vzorce ∫(x^a)dx=((x^(a+1))/(a+1)) je (∑_n)(n^(UnderBar[a]))=((n^(UnderBar[a+1]))/(a+1)).

Sum[FactorialPower[n,a],n]

Protože (n^a) lze vyjádřit jako lineární kombinaci (n^(UnderBar[k])), k∈{0,…,a} (koeficienty jsou Stirlingova čísla druhého druhu), dá se snadno najít antidiference k libovolnému polynomu v proměnné n.

Roli exponenciální funkce přebírá (2^n):

DifferenceDelta[2^n,n]

Sum[2^n,n]

Analogie Newtonova-Leibnizova vzorce: Je-li (Subscript[b, n]) antidiference (Subscript[a, n]), pak (∑_(n=min)^max)(Subscript[a, n])=(Subscript[b, max+1])-(Subscript[b, min])

Sum[n^2+3n+2,{n,1,10^20}]

b[n_]=Sum[n^2+3n+2,n]

b[10^20+1]-b[1]

Kreslení grafů

Objekty typu Graph

Neorientované grafy:

Graph[{1<->2,2<->3,3<->4,4<->2}]

InputForm[%]

Popisky u vrcholů:

Graph[{1<->2,2<->3,3<->4,4<->2},VertexLabels->"Name"]

Symbol pro neorientovanou hranu: <-> (EscueEsc)

Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]4,4\[UndirectedEdge]2}]

Orientované grafy:

Graph[{1->2,2->3,3->4,4->2}]

InputForm[%]

Symbol pro orientovanou hranu: -> (EscdeEsc)

Graph[{1\[DirectedEdge]2,2\[DirectedEdge]3,3\[DirectedEdge]4,4\[DirectedEdge]2}]

Graf s izolovanými vrcholy:

Graph[{1,2,3,4,5},{1->2,2->3,3->4,4->2}]

Zadání pomocí matice sousednosti:

AdjacencyGraph[(({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {0, 1, 0, 0}}))]

AdjacencyGraph[(({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {0, 1, 0, 0}})),DirectedEdges->False]

Konstrukce speciálních grafů:

Table[CompleteGraph[i],{i,3,7}]

CompleteGraph[{3,4}]

Table[CycleGraph[i],{i,3,7}]

Table[StarGraph[i],{i,3,7}]

CompleteKaryTree[3,4,DirectedEdges->True]

GridGraph[{3,6}]

Databáze GraphData

Všechny grafy v databázi:

GraphData[]

Třídy grafů:

GraphData["Classes"]

Grafy v dané třídě:

GraphData["Windmill"]

Konkrétní graf:

GraphData[{"Windmill",{4,4}}]

Vlastnosti grafů:

GraphData["Properties"]

GraphData[{"Windmill",{4,4}},"Connected"]

GraphData[{"Windmill",{4,4}},"Planar"]

GraphData[{"Windmill",{4,4}},"Acyclic"]

Umísťování vrcholů

Automatické rozmístění vrcholů v rovině, algoritmus lze zvolit pomocí GraphLayout:

Manipulate[Graph[graph,GraphLayout->layout],{graph,{CompleteGraph[6],StarGraph[6],CompleteGraph[{3,4}],CompleteKaryTree[5,3]}},{layout,{"CircularEmbedding","GridEmbedding","LayeredEmbedding","BipartiteEmbedding","LinearEmbedding","StarEmbedding","RandomEmbedding","SpringEmbedding","SpringElectricalEmbedding","GravityEmbedding"}}]

Explicitní zadání souřadnic vrcholů:

Graph[Range[6],{1->4,1->5,1->6,2->4,2->5,2->6,3->4,3->5,3->6},VertexCoordinates->{{0,(1/2)},{0,1},{0,(3/2)},{1,(1/2)},{1,1},{1,(3/2)}},VertexLabels->"Name"]

Vzhled vrcholů a hran

Volba GraphStyle:

GraphElementData["GraphStyle"]

Map[CompleteGraph[5,GraphStyle->#,PlotLabel->#]&,%]

Graph[{1->2,2->3,3->4,4->2},GraphStyle->"VintageDiagram"]

Volba PlotTheme:

Manipulate[Graph[{1->2,2->3,3->4,4->2},PlotTheme->theme,ImagePadding->10],{theme,{Automatic,"Detailed","Monochrome","Business","Scientific","Marketing","Minimal","Web","Classic"}}]

Explicitní nastavení vzhledu vrcholů a hran:

Graph[{1->2,2->3,3->4,4->2},VertexSize->0.15,VertexStyle->Green,EdgeStyle->Directive[Black,Thick]]

Pomocí VertexShapeFunction->f lze zadat libovolnou funkci, která bude obstarávat kreslení vrcholů. Pro každý vrchol se vyhodnotí f[(Subscript[r, k]),(Subscript[v, k])], kde (Subscript[r, k]) jsou souřadnice vrcholu v rovině a (Subscript[v, k]) jeho název.

Graph[{1->2,2->3,3->4,4->2},VertexShapeFunction->({LightBlue,EdgeForm[Black],Disk[#1,0.1],Black,Text[Style[#2,FontFamily->"Arial",FontSize->14],#1]}&)]

EdgeShapeFunction->g je specifikace funkce, která bude obstarávat kreslení hran. Pro každou hranu se vyhodnotí g[{(Subscript[r, i]),(Subscript[r, j])},{(Subscript[v, i]),(Subscript[v, j])},(Subscript[lbl, ij])], kde (Subscript[r, i]), (Subscript[r, j]) jsou souřadnice vrcholů hrany, (Subscript[v, i]) a (Subscript[v, j]) jsou názvy vrcholů, které hrana spojuje, a (Subscript[lbl, ij]) je případný název hrany.

Graph[{1->2,2->3,3->4,4->2},VertexStyle->Red,EdgeShapeFunction->({Blue,Arrow[#1],Arrow[Reverse[#1]]}&)]

Zvýraznění částí grafu

g=Graph[{1->2,2->3,3->4,4->2}]

HighlightGraph[g,{2->3,4}]

HighlightGraph[g,{2->3,4},GraphHighlightStyle->"Thick"]

Grafové algoritmy

Eulerovské tahy

?FindEulerianCycle

FindEulerianCycle[CompleteGraph[5]]

g1=CompleteGraph[7];cycle=First@FindEulerianCycle[g1];Manipulate[HighlightGraph[g1,cycle[[1;;d]],GraphHighlightStyle->"Thick"],{d,0,Length[cycle],1}]

Hamiltonovské kružnice

?FindHamiltonianCycle

Příklad (úloha šachového jezdce):

g2=GraphData[{"Knight",{8,8}}]

cycle=First[FindHamiltonianCycle[g2]]

Manipulate[HighlightGraph[g2,cycle[[1;;d]],GraphHighlightStyle->"Thick"],{d,0,Length[cycle],1}]

Šachovnice nestandardních rozměrů:

knightGraphs=Cases[GraphData[{"Knight"}],{"Knight",_}]

Grid[Map[{#,GraphData[#],GraphData[#,"Hamiltonian"]}&,knightGraphs],Dividers->All]

Věta (A. J. Schwenk, 1991): Úloha šachového jezdce na šachovnici m×n, kde m≤n, je řešitelná s výjimkou následujících případů:

a) m, n jsou obě lichá,

b) m∈{1,2,4},

c) m=3 a n∈{4,6,8}.

Maximální párování

FindIndependentEdgeSet hledá maximální párování, tj. co nejvíce hran takových, že žádné dvě nemají společný vrchol.

Příklad z dokumentace: Given a set of women, each of whom has a preference for some subset of men, find a maximal matching where only matches that agree with preferences are allowed:

g3=Graph[{(Subscript[W, 1])\[UndirectedEdge](Subscript[M, 2]),(Subscript[W, 1])\[UndirectedEdge](Subscript[M, 4]),(Subscript[W, 2])\[UndirectedEdge](Subscript[M, 1]),(Subscript[W, 3])\[UndirectedEdge](Subscript[M, 1]),(Subscript[W, 4])\[UndirectedEdge](Subscript[M, 1]),(Subscript[W, 4])\[UndirectedEdge](Subscript[M, 3])},VertexShapeFunction->"Name",VertexCoordinates->Join[Table[(Subscript[W, i])->{0,i-1},{i,4}],Table[(Subscript[M, j])->{2,j-1},{j,4}]],ImageSize->Small]

matchings=FindIndependentEdgeSet[g3]

HighlightGraph[g3,matchings,GraphHighlightStyle->"Thick"]

Nejkratší cesty v grafu

Graf bez ohodnocených hran:

g=GridGraph[{2,3},VertexLabels->"Name"]

FindShortestPath[g,1,6]

HighlightGraph[g,PathGraph@%]

Graf s ohodnocenými hranami:

edges={1<->2,2<->3,3<->4,4<->2,3<->5,4<->5};
weights={5,2,2,6,4,1};
g=Graph[MapThread[Labeled[#1,Framed[#2,RoundingRadius->25,Background->White]]&,{edges,weights}],VertexStyle->Red,EdgeWeight->weights,VertexLabels->"Name"]

HighlightGraph[g,PathGraph@FindShortestPath[g,1,5]]

Obarvení mapy čtyřmi barvami

countries=CountryData["SouthAmerica"]

edges=Flatten[Map[Thread[#\[UndirectedEdge]CountryData[#,"BorderingCountries"]]&,countries]]

Odstraníme všechny hrany, které vedou do vrcholů mimo countries (zde (Entity["Colombia", Entity["Country","Colombia"], "Entity[\"Country\", \"Colombia\"]", "country"])<->(Entity["Panama", Entity["Country","Panama"], "Entity[\"Country\", \"Panama\"]", "country"])).

edges=Cases[edges,(x_\[UndirectedEdge]y_)/;MemberQ[countries,y]]

Z každé dvojice x<->y, y<->x ponecháme jen jednu hranu (abecední řazení):

edges=Select[edges,OrderedQ]

graph=Graph[countries,edges,GraphLayout->"CircularEmbedding",VertexLabels->"Name"]

Funkce FindVertexColoring (novinka ve verzi 13) hledá obarvení grafu nejmenším možným počtem barev, tak aby sousední vrcholy měly různé barvy. (Obdobná, ale pomalejší funkce MinimumVertexColoring byla již dříve dostupná v balíčku Combinatorica.)

coloring=FindVertexColoring[graph]

capitalLocations=Reverse/@First/@Map[CountryData[#,"CapitalLocation"]&,countries]

polygons=Map[CountryData[#,"Polygon"]&,countries]

nicecolors={Red,Green,Yellow,RGBColor[0.68,0.85,0.9]};

Show[Graphics[{Table[{nicecolors[[coloring[[i]]]],polygons[[i]]},{i,1,Length[countries]}]}],Graph[countries,edges,VertexCoordinates->capitalLocations,PlotTheme->"Detailed"]]

countries=CountryData["Europe"]

edges=Flatten[Map[Thread[#\[UndirectedEdge]CountryData[#,"BorderingCountries"]]&,countries]];
edges=Cases[edges,(x_\[UndirectedEdge]y_)/;MemberQ[countries,y]&&OrderedQ[x\[UndirectedEdge]y]];
graph2=Graph[countries,edges,VertexLabels->"Name"];
coloring=FindVertexColoring[graph2];
capitalLocations=Reverse/@First/@Map[CountryData[#,"CapitalLocation"]&,countries];
polygons=Map[CountryData[#,"Polygon"]&,countries];
Show[Graphics[{Table[{nicecolors[[coloring[[i]]]],polygons[[i]]},{i,1,Length[countries]}]}],Graph[countries,edges,VertexCoordinates->capitalLocations,PlotTheme->"Detailed"],ImageSize->Full]

Diskrétní matematika a zpracování obrazu

Průchod bludištěm

Použité zdroje (Wolfram Blog):

Jon McLoone: aMAZEing Image Processing in Mathematica

Jon McLoone: The Battle of the Marlborough Maze at Blenheim Palace Continues

mazeImage=;

bwImage=Binarize[mazeImage]

cleanMaze=DeleteSmallComponents[bwImage,40000]

thinMaze=Thinning[cleanMaze]

prunedMaze=Pruning[thinMaze,∞]

croppedMaze=ImageTake[prunedMaze,350]

pathCoordinates=Position[ImageData[croppedMaze],1]

{start,end}=Cases[pathCoordinates,{350,_}]

pointNeighbors[{x_,y_}]:=Intersection[pathCoordinates,{{x+1,y},{x-1,y},{x,y+1},{x,y-1},{x+1,y+1},{x-1,y-1},{x+1,y-1},{x-1,y+1}}]

graphEdges[{x_,y_}]:=Map[({x,y}\[UndirectedEdge]#)&,pointNeighbors[{x,y}]]

graphEdges[start]

mazeGraph=Graph[pathCoordinates,Union[Map[Sort,Flatten[Map[graphEdges,pathCoordinates]]]],VertexCoordinates->pathCoordinates]

VertexCount[mazeGraph]

mazeSolution=FindShortestPath[mazeGraph,start,end];

{w,h}=ImageDimensions[mazeImage];
transform[{x_,y_}]:={y,h-x}
shortImage=Graphics[{Red,Point[Map[transform,mazeSolution]]}]

Show[mazeImage,shortImage]

TSP umění

Použitý zdroj (Wolfram Blog):

Vitaliy Kaurov: Find Waldo Faster

Here is a portrait computed by FindShortestTour spanning a single line through more than 30,000 points to redraw the Mona Lisa. The idea is quite simple: an image is reduced to only two colors with ColorQuantize, and then FindShortestTour draws a single line through the coordinates of only dark pixels.

monalisa = ;

adjustedML=ImageAdjust[
ColorQuantize[ColorConvert[monalisa,"Grayscale"],2]]

pts=PixelValuePositions[adjustedML,0];
Graphics[Line[pts[[FindShortestTour[pts][[2]]]]]]

So why isn’t it simply a chaos of lines rather than a recognizable image? Because in a shortest tour, connecting closer neighbors is often less costly. Thus, in the Mona Lisa one-liner, there are no segments spanning across large white spaces.

Cvičení

Uvažujme rovinný obrazec složený z konečného počtu jednotkových čtverečků, jejichž středy mají celočíselné souřadnice. Máme k dispozici dlaždice ve tvaru obdélníků o rozměrech 1 × 2, které lze pokládat ve vodorovném nebo svislém směru. Zajímá nás, jakým způsobem lze na políčka obrazce položit maximální počet dlaždic tak, aby se nepřekrývaly. Implementujte následující řešení této úlohy:

Předpokládejte, že obrazec je zadán seznamem souřadnic středů jednotkových čtverečků, tj. dvojicemi celých čísel. Napište funkci, která dostane tento seznam a vykreslí všechny čtverečky obrazce.

Zkonstruujte graf, jehož vrcholy odpovídají středům čtverečků, přičemž dva vrcholy budou spojeny hranou, právě když se jedná o sousední čtverečky. Postupujte podobně jako při řešení úlohy o průchodu bludištěm.

Najděte maximální párování v tomto grafu, zobrazte příslušné hrany a doplňte je do dříve získaného obrázku.

Následující obrázek ilustruje celý postup: Vstupem je obdélník o rozměrech 4 × 3 zadaný ve formě seznamu {{1,1},{1,2},{1,3},{2,1},{2,2},{2,3},{3,1},{3,2},{3,3},{4,1},{4,2},{4,3}}. Další části obrázku ukazují příslušný graf, nalezené maximální párování a výsledné rozmístění dlaždic (pokud existuje více možností, jak dlaždice poskládat, stačí vybrat libovolnou z nich):

Použijte svůj program k vyřešení úlohy pro následující obrazec:

Standardní balíček hracích karet je tvořen 52 kartami rozdělenými do čtyř barev, s třinácti hodnotami 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A. Balíček promícháme a karty následně vyskládáme do 4 řádků a 13 sloupců. Naším úkolem je vybrat z každého sloupce jednu kartu tak, abychom na konci měli od každé hodnoty po jedné kartě (libovolné barvy). Dá se dokázat, že úloha je vždy řešitelná.
Situaci ilustruje následující obrázek, kdy lze úkol splnit např. tak, že z jednotlivých sloupců postupně volíme karty s hodnotami 5, 4, A, J, Q, 2, 6, 10, 3, 7, 8, 9, K.

Implementujte následující postup:

Vytvořte seznam obsahující všech 52 karet; prvky seznamu budou dvojice {hodnota, barva}, přičemž barvy reprezentujte jejich názvy. Pomocí RandomSample vygenerujte náhodnou permutaci karet, pomocí Partition ji rozdělte do 4 řádků po 13 kartách. Zobrazte výslednou tabulku pomocí Grid.

Zkonstruujte orientovaný graf tvořený dvěma skupinami vrcholů: V první skupině budou čísla sloupců, tj. 1 až 13, a ve druhé skupině hodnoty karet, tj. 2 až A (uložte je jako řetězce, aby nekolidovaly s názvy vrcholů v první skupině). Vrchol i z první skupiny bude spojen orientovanou hranou s vrcholem j z druhé skupiny právě tehdy, když ve sloupci i leží karta s hodnotou j.

Najděte maximální párování v tomto grafu.

Pokud se v párování objeví hrana i->j, znamená to, že ze sloupce i vezmeme kartu s hodnotou j (je-li takových karet více, vybereme libovolnou z nich). Zkonstruujte seznam, kde na i-té pozici bude hodnota karty vybrané z i-tého sloupce, tj. např. {5,4,A,J,Q,2,6,10,3,7,8,9,K}.