streamalism.org

1. Overzicht

In deze tutorial leren we hoe we enkele veelvoorkomende combinatorische problemen kunnen oplossen. Ze zijn hoogstwaarschijnlijk niet erg nuttig in een alledaagse job; ze zijn echter interessant vanuit algoritmisch perspectief. We kunnen ze handig vinden voor testdoeleinden.

Houd er rekening mee dat er veel verschillende benaderingen zijn om deze problemen op te lossen. We hebben geprobeerd de gepresenteerde oplossingen begrijpelijk te maken.

2. Permutaties genereren

Laten we eerst beginnen met permutaties. Een permutatie is een handeling waarbij een reeks zodanig wordt herschikt dat deze een andere volgorde heeft.

Zoals we weten uit wiskunde, voor een reeks van n elementen zijn er n! verschillende permutaties. n! staat bekend als een faculteit operatie:

n! = 1 * 2 *… * n

Dus bijvoorbeeld voor een reeks [1, 2, 3] er zijn zes permutaties:

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Factorial groeit erg snel - voor een reeks van 10 elementen hebben we 3.628.800 verschillende permutaties! In dit geval, we hebben het over permuterende reeksen, waarbij elk element anders is.

2.1. Algoritme

Het is een goed idee om na te denken over het genereren van permutaties op een recursieve manier. Laten we het idee van de staat introduceren. Het zal uit twee dingen bestaan: de huidige permutatie en de index van het momenteel verwerkte element.

Het enige werk dat je in een dergelijke toestand kunt doen, is het element verwisselen met elk overgebleven element en een overgang uitvoeren naar een toestand met de gewijzigde volgorde en de index verhoogd met één.

Laten we illustreren met een voorbeeld.

We willen alle permutaties genereren voor een reeks van vier elementen - [1, 2, 3, 4]. Er zullen dus 24 permutaties zijn. De onderstaande afbeelding toont de deelstappen van het algoritme:

Elk knooppunt van de boom kan worden opgevat als een staat. De rode cijfers bovenaan geven de index van het momenteel verwerkte element aan. De groene cijfers in de knooppunten illustreren swaps.

Dus we beginnen in de staat [1, 2, 3, 4] met een index gelijk aan nul. We ruilen het eerste element met elk element - inclusief het eerste, dat niets ruilt - en gaan verder naar de volgende toestand.

Nu bevinden onze gewenste permutaties zich in de laatste kolom aan de rechterkant.

2.2. Java-implementatie

Het algoritme geschreven in Java is kort:

private statische ongeldige permutaties Intern (lijstvolgorde, lijst results, int index) {if (index == sequence.size () - 1) {permutations.add (new ArrayList (sequence)); } for (int i = index; i <sequence.size (); i ++) {swap (sequentie, i, index); permutationsInternal (sequentie, permutaties, index + 1); swap (sequentie, i, index); }}

Onze functie heeft drie parameters: de momenteel verwerkte volgorde, resultaten (permutaties) en de index van het element dat momenteel wordt verwerkt.

Het eerste dat u moet doen, is controleren of we het laatste element hebben bereikt. Dan voegen we de reeks toe aan de resultatenlijst.

Vervolgens voeren we in de for-lus een swap uit, doen een recursieve aanroep van de methode en ruilen we het element vervolgens terug.

Het laatste deel is een kleine prestatietruc - we kunnen op dezelfde manier werken volgorde object de hele tijd zonder dat u voor elke recursieve aanroep een nieuwe reeks hoeft te maken.

Het kan ook een goed idee zijn om de eerste recursieve aanroep onder een gevelmethode te verbergen:

openbare statische lijst GenereerPermutations (lijstopeenvolging) {List permutaties = nieuwe ArrayList (); permutationsInternal (sequentie, permutaties, 0); permutaties teruggeven; } 

Houd er rekening mee dat het weergegeven algoritme alleen werkt voor reeksen unieke elementen! Het toepassen van hetzelfde algoritme voor reeksen met terugkerende elementen geeft ons herhalingen.

3. Genereren van de Powerset van een set

Een ander populair probleem is het genereren van de powerset van een set. Laten we beginnen met de definitie:

powerset (of power set) van set S is de verzameling van alle subsets van S inclusief de lege set en S zelf

Dus bijvoorbeeld een set [a, b, c], de powerset bevat acht subsets:

[] [a] [b] [c] [a, b] [a, c] [b, c] [a, b, c]

We weten uit wiskunde dat, voor een set met n elementen, de powerset moet bevatten 2 ^ n subsets. Dit aantal groeit ook snel, maar niet zo snel als faculteit.

3.1. Algoritme

Deze keer denken we ook recursief. Nu zal onze toestand uit twee dingen bestaan: de index van het element dat momenteel wordt verwerkt in een set en een accumulator.

We moeten een beslissing nemen met twee keuzes in elke staat: het al dan niet plaatsen van het huidige element in de accumulator. Wanneer onze index het einde van de set bereikt, hebben we een mogelijke subset. Zo kunnen we elke mogelijke subset genereren.

3.2. Java-implementatie

Ons algoritme geschreven in Java is redelijk leesbaar:

private static void powersetInternal (List set, List powerset, List accumulator, int index) {if (index == set.size ()) {results.add (nieuwe ArrayList (accumulator)); } else {accumulator.add (set.get (index)); powerSetInternal (set, powerset, accumulator, index + 1); accumulator.remove (accumulator.size () - 1); powerSetInternal (set, powerset, accumulator, index + 1); }}

Onze functie heeft vier parameters nodig: een set waarvoor we subsets willen genereren, de resulterende powerset, de accumulator en de index van het momenteel verwerkte element.

Voor de eenvoud, we houden onze sets in lijsten. We willen snelle toegang hebben tot elementen gespecificeerd door index, waarmee we het kunnen bereiken Lijst, maar niet met Set.

Bovendien wordt een enkel element weergegeven door een enkele letter (Karakter klasse in Java).

We kijken eerst of de index groter is dan de ingestelde grootte. Als dit het geval is, plaatsen we de accumulator in de resultatenset, anders:

• plaats het momenteel beschouwde element in de accumulator
• maak een recursieve oproep met verhoogde index en uitgebreide accumulator
• verwijder het laatste element uit de accumulator, dat we eerder hebben toegevoegd
• doe opnieuw een oproep met ongewijzigde accumulator en de verhoogde index

Nogmaals, we verbergen de implementatie met een gevelmethode:

openbare statische lijst genererenPowerset (lijstreeks) {List powerset = nieuwe ArrayList (); powerSetInternal (sequentie, powerset, nieuwe ArrayList (), 0); terugkeer powerset; }

4. Combinaties genereren

Nu is het tijd om combinaties aan te pakken. We definiëren het als volgt:

k-combinatie van een set S is een subset van k verschillende elementen van S, waar een volgorde van items er niet toe doet

Het aantal k-combinaties worden beschreven door de binominale coëfficiënt:

Dus bijvoorbeeld voor de set [a, b, c] we hebben er drie 2-combinaties:

[a, b] [a, c] [b, c]

Combinaties hebben veel combinatorische toepassingen en verklaringen. Laten we als voorbeeld zeggen dat we een voetbalcompetitie hebben die uit 16 teams bestaat. Hoeveel verschillende overeenkomsten kunnen we zien?

Het antwoord is , wat neerkomt op 120.

4.1. Algoritme

Conceptueel zullen we iets doen dat lijkt op het vorige algoritme voor powersets. We hebben een recursieve functie, waarbij de status bestaat uit de index van het momenteel verwerkte element en een accumulator.

Nogmaals, we hebben dezelfde beslissing voor elke staat: voegen we het element toe aan de accumulator?Deze keer hebben we echter een extra beperking: onze accu kan niet meer hebben dan k elementen.

Het is vermeldenswaard dat de binominale coëfficiënt niet noodzakelijk een enorm getal hoeft te zijn. Bijvoorbeeld:

is gelijk aan 4.950, terwijl

heeft 30 cijfers!

4.2. Java-implementatie

Voor de eenvoud nemen we aan dat elementen in onze set gehele getallen zijn.

Laten we eens kijken naar de Java-implementatie van het algoritme:

private statische ongeldige combinaties Intern (List inputSet, int k, List resultaten, ArrayList-accumulator, int index) {int needToAccumulate = k - accumulator.size (); int canAcculumate = inputSet.size () - index; if (accumulator.size () == k) {results.add (nieuwe ArrayList (accumulator)); } else if (needToAccumulate <= canAcculumate) {CombinationsInternal (inputSet, k, results, accumulator, index + 1); accumulator.add (inputSet.get (index)); combinatiesInternal (inputSet, k, resultaten, accumulator, index + 1); accumulator.remove (accumulator.size () - 1); }}

Deze keer heeft onze functie vijf parameters: een invoerset, k parameter, een resultatenlijst, een accumulator en de index van het huidig ​​verwerkte element.

We beginnen met het definiëren van hulpvariabelen:

• needToAccumulate - geeft aan hoeveel extra elementen we aan onze accumulator moeten toevoegen om een ​​goede combinatie te krijgen
• canAcculumate - geeft aan hoeveel extra elementen we aan onze accumulator kunnen toevoegen

Nu controleren we of onze accumulatormaat gelijk is aan k. Als dat het geval is, kunnen we de gekopieerde array in de resultatenlijst plaatsen.

In een ander geval als we nog genoeg elementen in het resterende deel van de set hebben, doen we twee afzonderlijke recursieve aanroepen: met en zonder dat het momenteel verwerkte element in de accumulator wordt geplaatst. Dit deel is analoog aan hoe we de powerset eerder hebben gegenereerd.

Deze methode had natuurlijk kunnen worden geschreven om iets sneller te werken. We zouden bijvoorbeeld kunnen aangeven needToAccumulate en canAcculumate variabelen later. We zijn echter gefocust op leesbaarheid.

Nogmaals, een gevelmethode verbergt de implementatie:

openbare statische lijst combinaties (List inputSet, int k) {List results = nieuwe ArrayList (); combinatiesInternal (inputSet, k, results, new ArrayList (), 0); resultaten retourneren; }

5. Samenvatting

In dit artikel hebben we verschillende combinatorische problemen besproken. Bovendien hebben we eenvoudige algoritmen laten zien om ze op te lossen met implementaties in Java. In sommige gevallen kunnen deze algoritmen helpen bij ongebruikelijke testbehoeften.

Zoals gewoonlijk is de volledige broncode, met tests, beschikbaar op GitHub.