Springen naar inhoud

Algoritme unieke set getallen uit n verzamelingen


  • Log in om te kunnen reageren

#1

Box

    Box


  • >25 berichten
  • 100 berichten
  • Ervaren gebruiker

Geplaatst op 23 mei 2011 - 20:24

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
Das ist nicht einmal falsch. - Wolfgang Pauli

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 23 mei 2011 - 20:44

Is er hiervoor een goed en snel algoritme?

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.
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-

#3

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 24 mei 2011 - 08:43

Ik heb N sets met getallen in een bepaalde volgorde.

Wat is een bepaalde volgorde? Bedoel je een willekeurige volgorde?

Is er hiervoor een goed en snel algoritme?

Dat hangt er van af. Wat vind je goed en wat vind je snel?

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.

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.

#4

Box

    Box


  • >25 berichten
  • 100 berichten
  • Ervaren gebruiker

Geplaatst op 24 mei 2011 - 16:16

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.
Das ist nicht einmal falsch. - Wolfgang Pauli

#5

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 24 mei 2011 - 17:00

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.

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.

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 LaTeX . 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-

#6

Box

    Box


  • >25 berichten
  • 100 berichten
  • Ervaren gebruiker

Geplaatst op 24 mei 2011 - 20:52

Bedankt !
Das ist nicht einmal falsch. - Wolfgang Pauli





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures