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
Laatste berichten
-
23:25
2013 – Augustus Vraag 3
-
23:07
Rood laserlicht 2
-
23:04
Bruine vlekken op treinaanwijzerbord 5
-
15:28
Vraag 2009 Juli Vraag 5 5
-
12:51
positie 2
-
10:44
Schroefdraad berekening 8
-
24 apr
[scheikunde] Kan chloorgas de geleiding van elektriciteit belemmeren? 9
-
23 apr
Weerfrustratie 9
-
23 apr
geen minkowski-ruimte toch? Doe ik dit nou fout? 15
-
23 apr
do-re-mi-fa-so vliegtuigen 7
-
23 apr
Kunnen quantum Zonnecellen 190% quantum efficiënt zijn 3
-
23 apr
De Euro Nederlandse 100 qubit computer komt eraan
-
23 apr
projectiel 8
-
23 apr
Verschil tussen deze 2 vragen 5
-
23 apr
[scheikunde] berekeningen labo vitamine c bepaling 1
-
22 apr
[wiskunde] rode en witte ballen verdelen 8
-
22 apr
Rotatie van het heelal 41
-
22 apr
Muntje opgooien 14
-
21 apr
Reactiviteit silyl enol ethers 1
-
21 apr
Criterium voor vochtretentie
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
Algoritme unieke set getallen uit n verzamelingen
-
- Berichten: 100
Algoritme unieke set getallen uit n verzamelingen
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
