Wie heißt diese Datenstruktur

Wie heißt diese Datenstruktur (19 Beiträge, 697 Mal gelesen)

Du bist nicht angemeldet. [ Login/Registrieren ]

Ein Array, eine list oder was auch immer die folgendes kann/macht:

Es gibt maximal x Integer Elemente, die Struktur wird gefüttert mit Integerwerten zwischen 0 und x-1. Größere und kleinere Werte kommen nicht vor.
Die neueste Zahl kommt immer "oben" drauf.
Falls die hinzuzufügende Zahl y schon vorkommt:
Die Zahl y kommt wie immer ganz oben auf die Struktur, auf der alten Position wird y entfernt, aber alle Zahlen unter/hinter/nach y sollen aufrücken.

Beispiel:
Die Zahlen, 5, 20, 2, 21, 22 werden nacheinander, beginnend mit 5 an die Struktur geschickt:
Die Reihenfolge wie folgt:
5, 20, 2, 21, 22.
Jetzt geben wir nochmal 21 dazu, die Reihenfolge ist dann wie folgt:
21, 5, 20, 2, 22

Auf gut Deutsch: Eine Liste von Zahlen, in der jede Zahl nur einmal existieren darf, wobei bereits vorhandene Zahlen an den Anfang der Liste gestellt werden, die alte Position dieser Zahl gelöscht wird und der Rest aufrückt.

Ich könnte mir das wahrscheinlich selber basteln würde es aber wahrscheinlich nur äußerst unperformant hinbekommen.
Jede Zahl in eine Instanz der Speicherklasse ala Binärbaum?
Dann könnte ich am leichtesten aufrücken.

Das Ziel ist, dass ich herausfinden möchte ob man bei möglichst perfekten Zufallszahlen zwischen 0 und x durch das Erwarten der am längsten nicht aufgetretenen Zahlen die Wahrscheinlichkeit des Auftretens jeder einzelnen Zahl zwischen 0 und x berechnen kann.

Man könnte ja sagen:
"Jeder Griff in den Random Topf holt eine komplett zufällige Zahl hervor!"
oder
"Dass 100 mal hintereinander dieselbe Zahl y auftritt bei einer Auswahl aus 10^1000 Zahlen muss genauso wahrscheinlich sein wie jede andere definierte Folge derselben Größe aus demselben Arsenal!"
aber ich bin trotzdem misstrauisch.

Re: Wie heißt diese Datenstruktur (hariw am 22.08.2012, 13:38:09)

Re: Wie heißt diese Datenstruktur (hellbringer am 22.08.2012, 13:38:10)

Re(2): Wie heißt diese Datenstruktur (Diabolo2000 am 22.08.2012, 13:51:44)

Re: Wie heißt diese Datenstruktur

(tha_haze am 22.08.2012, 18:28:35)

Re: Wie heißt diese Datenstruktur (ZombyKillah am 22.08.2012, 22:58:22)

Re(2): Wie heißt diese Datenstruktur (Diabolo2000 am 22.08.2012, 23:33:07)

Re(3): Wie heißt diese Datenstruktur (ZombyKillah am 23.08.2012, 23:00:34)

Re: Wie heißt diese Datenstruktur (Robert Craven am 22.08.2012, 23:19:32)

Re: Wie heißt diese Datenstruktur (User71571 am 23.08.2012, 07:16:50)

Re: Wie heißt diese Datenstruktur (thE am 23.08.2012, 13:04:02)

Re: Wie heißt diese Datenstruktur (m3t4tr0n am 24.08.2012, 00:52:21)

Re: Wie heißt diese Datenstruktur (TomCat am 24.08.2012, 21:28:30)

Re: Wie heißt diese Datenstruktur (spoilerhead am 25.08.2012, 11:48:30)

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung