Algorytmy kombinatoryczne - pseudokod algorytmów omawianych na ćwiczeniach

Pseudokody wszystkich poznanych dotychczas algorytmów jako PDF: pobierz

 Reprezentacja zbiorów

• SetInsert
• SetDelete
• MemberOfSet
• SetUnion
• SetIntersection
• Zliczanie jedynek w ciągu bitów
• Zliczanie jedynek w słowie maszyny
• Zliczanie jedynek z tablicą lookup
• Zliczanie jedynek - logarytmiczny algorytm rekurencyjny
  

 Generowanie ciągów długości k z liczb {1,...,n}

• Algorytm rekurencyjny (podany na wykładzie)

 Generowanie podzbiorów zbioru {1,...,n}

• SubsetLexSuccessor
• SubsetLexRank
• SubsetLexUnrank
• GrayCodeRank
• GrayCodeUnrank

 Generowanie k-elementowych podzbiorów zbioru {1,...,n}

Porządek co-lex:

• kSubsetCoLexSuccessor
• kSubsetCoLexRank
• kSubsetCoLexUnrank

Porządek minimalnych zmian (revolving door):

• kSubsetRevDoorSuccessor
• kSubsetRevDoorRank
• kSubsetRevDoorUnrank

 Generowanie permutacji zbioru {1,...,n} w porządku minimalnych zmian

• TrotterJohnsonRank
• TrotterJohnsonUnrank
• PermParity
• TrotterJohnsonSuccessor

 Podziały liczb

• EnumPartitions
• PartitionLexRank
• PartitionLexUnrank
• PartitionLexSuccessor

 Podziały zbiorów

• SetPartToRGF
• RGFToSetPart
• GenerateRGF
• GeneralizedRGF
• RankRGF
• UnrankRGF

 Kod Prüfera

• Prüfer
• InvPrüfer
• PrüferToRank
• RankToPrüfer

 Trwałe skojarzenia

• StableMatchingFundamental