Seite 1 von 3
Die nächstkleinste freie Zahl in einer Liste finden
Verfasst: 11.06.2014 08:49
von Bisonte
Hallo.
Ich habe eine Liste : Nummer.i()
In dieser Liste sind zufällige Zahlen, wobei keine der Zahlen doppelt sein darf.
wie kann ich ermitteln welche nächste kleinstmögliche Zahl ich der Liste hinzufügen kann ?
Bsp: Wie bekomme ich die 2 heraus ?
Code: Alles auswählen
NewList Nummer.i()
AddElement(Nummer()) : Nummer() = 4
AddElement(Nummer()) : Nummer() = 3
AddElement(Nummer()) : Nummer() = 1
AddElement(Nummer()) : Nummer() = 7
AddElement(Nummer()) : Nummer() = 5
SortList(Nummer(), #PB_Sort_Ascending)
ForEach Nummer()
Debug Nummer()
Next
Ich seh den Wald bestimmt vor lauter Bäumen nicht
Re: Die nächstkleinste freie Zahl in einer Liste finden
Verfasst: 11.06.2014 10:09
von matbal
Überprüfe einfach, ob nächstes Element um 1 größer ist
Code: Alles auswählen
Procedure GetNumber(List Nummer())
Protected n
ForEach Nummer()
n + 1
If Nummer() <> n
ProcedureReturn n
EndIf
Next
ProcedureReturn n + 1
EndProcedure
Re: Die nächstkleinste freie Zahl in einer Liste finden
Verfasst: 11.06.2014 13:21
von Chimorin
Das geht ja nicht, weil die Zahlen zufällig sind.
Mir fällt da nur ein:
Liste sortieren und DANN nachschauen, wo eine Zahl fehlt. Vom unteren Rand aus.
Re: Die nächstkleinste freie Zahl in einer Liste finden
Verfasst: 11.06.2014 13:32
von NicTheQuick
Wie viele Zahlen werden es denn später so ungefähr sein? Und wie läuft das ganze überhaupt ab? Sind am Anfang alle Zahlen da, dann werden welche heraus genommen und dann willst du erst wissen, welche die kleinste ist, die fehlt? Oder bekommst du von Anfang an diese unsortierte Liste und willst dann die kleinste fehlende Zahl finden? Und gibt es nach oben Grenzen oder nicht? Wenn es nach oben nämlich keine Grenzen gibt und außerdem alle Zahlen Ganzzahlen sind, dann würde sich ein Radixsort anbieten. Und für den ersten Fall könnte man auch einen Heap nutzen.
Re: Die nächstkleinste freie Zahl in einer Liste finden
Verfasst: 11.06.2014 13:43
von Bisonte
Sinn und Zweck der Übung ist es eine Art Objektverwaltung wie PB zu realisieren. Also wenn ein Objekt mit
#PB_Any erstellt wird, eine freie Nummer zu bekommen. Es wird also laufend etwas hinzugefügt und entfernt. deswegen auch am besten
immer die kleinste Nummer.... Heisst natürlich aber auch, das da keine doppelten Nummern existieren dürfen.
(Wollte ich dann mit einer Map() realisieren)
Re: Die nächstkleinste freie Zahl in einer Liste finden
Verfasst: 11.06.2014 14:20
von NicTheQuick
Achso, okay.
Ich hatte da auch mal sowas gemacht. Schon Ewigkeiten her. Ich hab das mal eben umgebaut auf Module:
Code: Alles auswählen
DeclareModule ID
Structure IDList
count.i
List freeIDs.i()
EndStructure
Global NewMap IDs.IDList()
Declare.i newID(type.s)
Declare.i freeID(type.s, id.i)
EndDeclareModule
Module ID
Procedure.i newID(type.s)
Protected *idList.IDList = FindMapElement(IDs(), type)
Protected tmp.i
If (*idList)
If (FirstElement(*idList\freeIDs()))
tmp = *idList\freeIDs()
DeleteElement(*idList\freeIDs())
ProcedureReturn tmp
Else
*idList\count + 1
ProcedureReturn *idList\count - 1
EndIf
Else
*idList = AddMapElement(IDs(), type, #PB_Map_NoElementCheck)
If (Not *idList)
ProcedureReturn -1
EndIf
*idList\count + 1
ProcedureReturn 0
EndIf
EndProcedure
Procedure.i freeID(type.s, id.i)
Protected *idList.IDList = FindMapElement(IDs(), type)
If (Not *idList)
ProcedureReturn #False
EndIf
With *idList
If (id = \count - 1)
\count - 1
Else
If AddElement(\freeIDs())
\freeIDs() = id
SortList(\freeIDs(), #PB_Sort_Ascending)
;Räume die Liste auf
While LastElement(\freeIDs())
If (\freeIDs() = \count - 1)
DeleteElement(\freeIDs())
\count - 1
Else
Break
EndIf
Wend
EndIf
EndIf
EndWith
ProcedureReturn #True
EndProcedure
EndModule
Debug ID::newID("window")
Debug ID::newID("gadget")
Debug ID::newID("gadget")
Debug ID::newID("gadget")
Debug ID::newID("gadget")
ID::freeID("gadget", 2)
ID::freeID("gadget", 1)
Debug ID::newID("gadget")
Debug ID::newID("gadget")
Ich speichere eigentlich einfach nur die wieder frei gegebenen freien IDs und nimm die wieder aus der Liste heraus, wenn man eine neue braucht. Das 'SortList()' kann man mit einem Heap etwas effizienter machen, aber ob sich das lohnt, kommt auf das Einsatzgebiet an.
///Edit:
Hab noch eine kleine Aufräumroutine eingebaut, die sicher stellt, dass die interne 'freeIDs()'-Liste immer so klein wie möglich ist.
Re: Die nächstkleinste freie Zahl in einer Liste finden
Verfasst: 11.06.2014 16:08
von DrShrek
Nimm doch einfach eine Map + etwas Logik beim generieren des Keys: JJJJMMDDHHMMSSmmm => das sollte fast schon sicher sein.
Re: Die nächstkleinste freie Zahl in einer Liste finden
Verfasst: 11.06.2014 16:20
von Derren
Ich würde das mit 2 Listen machen. Eine kleine Zahl wird ja nur frei wenn du etwas löscht. Ansonsten stapelst du ja immer oben drauf, musst also nur die zuletzt hinzugefügte Zahl speichern.
Wenn du jetzt was löscht, speicherst du die Zahl in einer zweiten Liste, welche sortiert ist (diese Liste sollte ja jederzeit ziemlich klein sein, weshalb das sortieren relativ schnell geht).
Re: Die nächstkleinste freie Zahl in einer Liste finden
Verfasst: 11.06.2014 17:48
von Chimorin
Derrens Idee finde ich super
Re: Die nächstkleinste freie Zahl in einer Liste finden
Verfasst: 11.06.2014 17:51
von Derren
Hab mir den Code nicht genau angeschaut, aber ich glaube Nic's Code macht genau das, dem Kommentar unter dem Code nach zu urteilen.