Die nächstkleinste freie Zahl in einer Liste finden

[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

[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

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

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

[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)

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

[DrShrek]

Nimm doch einfach eine Map + etwas Logik beim generieren des Keys: JJJJMMDDHHMMSSmmm => das sollte fast schon sicher sein.

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

[Chimorin]

Derrens Idee finde ich super

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