Algoritme unieke set getallen uit n verzamelingen
- Berichten: 100
Algoritme unieke set getallen uit n verzamelingen
Ik heb N sets met getallen in een bepaalde volgorde. Ik wil uit elke verzameling één getal nemen en toevoegen aan een rij. Ik wil dat de rij allemaal unieke getallen bevat.
Is er hiervoor een goed en snel algoritme?
mvg, Box
Is er hiervoor een goed en snel algoritme?
mvg, Box
Das ist nicht einmal falsch. - Wolfgang Pauli
- Berichten: 5.609
Re: Algoritme unieke set getallen uit n verzamelingen
Ja, je neemt een getal uit de eerste verzameling, voegt die toe aan de lijst, maar ook aan een hashSet. Dan kun je iedere keer als je een nieuw getal wil toevoegen, in constante tijd kijken of je die al genomen hebt door te kijken of die in je hashSet zit.Is er hiervoor een goed en snel algoritme?
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
-
- Berichten: 7.068
Re: Algoritme unieke set getallen uit n verzamelingen
Wat is een bepaalde volgorde? Bedoel je een willekeurige volgorde?Ik heb N sets met getallen in een bepaalde volgorde.
Dat hangt er van af. Wat vind je goed en wat vind je snel?Is er hiervoor een goed en snel algoritme?
Het in (bijna) constante tijd controleren of je een getal al gehad hebt, lijkt me niet het grootste probleem. Een veel groter probleem lijkt het me dat je bij de laatste set getallen komt en dan blijkt dat er geen getal in zit dat je niet al hebt toegevoegd aan je rij.Ja, je neemt een getal uit de eerste verzameling, voegt die toe aan de lijst, maar ook aan een hashSet. Dan kun je iedere keer als je een nieuw getal wil toevoegen, in constante tijd kijken of je die al genomen hebt door te kijken of die in je hashSet zit.
- Berichten: 100
Re: Algoritme unieke set getallen uit n verzamelingen
Excuseer voor de onvolledigheid, ik preciseer:
Ik heb n eindige gelabelde sets: set 1, ..., set n.
Ik wil nu een n-tupel samenstellen waarbij de i-de component een getal uit set i is. Ik wil dat alle componenten van het n-tupel van elkaar verschillen.
Ik bedoelde een algoritme dat zo'n n-tupel construeert of mij (al snel) zegt of zo'n n-tupel niet bestaat.
Ik heb zelf hiervoor een (zeer naief) algoritme geschreven (voor een programma) en vroeg me af of er een gekend en efficiënt algoritme bestond voor dit probleem.
Ik heb n eindige gelabelde sets: set 1, ..., set n.
Ik wil nu een n-tupel samenstellen waarbij de i-de component een getal uit set i is. Ik wil dat alle componenten van het n-tupel van elkaar verschillen.
Ik bedoelde een algoritme dat zo'n n-tupel construeert of mij (al snel) zegt of zo'n n-tupel niet bestaat.
Ik heb zelf hiervoor een (zeer naief) algoritme geschreven (voor een programma) en vroeg me af of er een gekend en efficiënt algoritme bestond voor dit probleem.
Das ist nicht einmal falsch. - Wolfgang Pauli
- Berichten: 5.609
Re: Algoritme unieke set getallen uit n verzamelingen
Ah, vrij simpel eigenlijk. Als je een willekeurig aantal willekeurige verzamelingen neemt, moeten hierin steeds meer verschillende getallen staan dan er verzamelingen zijn. Dit is een nodige en voldoende voorwaarde voor een oplossing. Dit is Hall's trouwprobleem.Box schreef:Ik bedoelde een algoritme dat zo'n n-tupel construeert of mij (al snel) zegt of zo'n n-tupel niet bestaat.
Ik heb zelf hiervoor een (zeer naief) algoritme geschreven (voor een programma) en vroeg me af of er een gekend en efficiënt algoritme bestond voor dit probleem.
Het probleem om zo'n set te construeren is een bipartite graaf maximum matching probleem. Het beste algoritme daarvoor is het Hopcroft–Karp algoritme dat draait in
\(O(\sqrt{V}E)\)
. Hierin is V het aantal getallen en E de som van het aantal keren de getallen voorkomen.What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
- Berichten: 100
Re: Algoritme unieke set getallen uit n verzamelingen
Bedankt !
Das ist nicht einmal falsch. - Wolfgang Pauli