RSS Feed
abonnieren.
Suche
Wunschzettel
Weblogeinträge
ReferenzenProgrammier-Quiz finde nächste freie Zahl | 19. September 2007 um 19:29 Uhr
Ich habe gerade ein Interessantes Problem was ich auch mit euch mal zum Überlegen teilen möchte. Ich habe ein Array mit ganzen positiven sortierten Zahlen die bei 1 beginnen, z.B. [1,2,3,5,6,7] und möchte die erste "freie" Zahl finden. In diesem Fall ist das die 4. Im Array können auch mehrere Zahlen fehlen wie bei: [1,3,5,6,7], dann möchte ich die erste "freie" Zahl, die 2 finden, sonst nichts. Es kann auch sein dass es gar keine Lücke gibt, dann möchte ich einfach die Nächste "freie" Zahl haben. Falls schon die 1 fehlen sollte dann möchte ich diese haben.
Konkret geht es darum dass das Spieltage einer Liga sind. Es kann vorkommen dass ein Spieltag verlegt wird und erst später gespielt wird. Ich möchte dem Administrator, der ein Neues Spiel eingeben muss einen Vorschlag für den möglichen nächsten Spieltag geben. Die Spieltage bekomme ich aus der Datenbank und sie stehen mir als Array zur Verfügung.
Es ist egal in welcher Sprache ihr das löst, ich hätte aber gerne verschiedene Ansätze in verschiedenen Sprachen gesehen.
Meine Lösung bisher ist eine ziemlich einfache aber wohl nicht so performante, da jedes mal im ganzen Array gesucht werden muss (in Ruby):
def next_matchday(matchdays)
matchday = 0
while (matchday += 1)
return matchday unless matchdays.include? matchday
end
end
puts next_matchday([1,2,3,5,6,7])
=> 4
puts next_matchday([2,3,5,6,7])
=> 1
clynx schrieb am 19.09.2007
PHP:
$x = 0; do { $x++; $y = array_shift( $matchdays); } while( $x == $y );Henryk Plötz schrieb am 19.09.2007
PHP(kurz): (ggbf. plus eine Überprüfung auf leere Liste)
do { $x++; } while( $matchdays[$x-1] == $x );PHP(vielleicht schneller):
Javascript/Pseudocode:
Python (eher umständlich):
Daniel Thoma schrieb am 19.09.2007
Bisher wurden ja nur verschiedene Implementierungen in linearer Zeit genannt.
Wir kennen aber folgende Eigenschaft: wenn eine Teilliste mit einer Zahl a beginnt und mit einer Zahl b endet, dann muss sie b - a + 1 Elemente enthalten. (Dies gilt natürlich nur, wenn man doppelte Elemente ausschließen kann)
Wir können also prüfen, ob ein Element im Array fehlt. Wenn das der Fall ist, machen wir das rekursiv für die erste und zweite Hälfte.
Wir wenden also einfach das bekannte Devide and Conquer-Prinzip auf unsere Eigenschaft dieser Listen an. Und schon lösen wir das Problem in logarithmischer Zeit.
Die Ausformulierung als Programm überlasse ich hier mal als Übungsaufgabe ;)
Es ist übrigens unwahrscheinlich, dass das Verfahren bei einer Hand voll (< 10 oder so) Elemente schon etwas bringt.
Jeena Paradies aus Varberg schrieb am 19.09.2007
Interessant, auch wenn ich so etwas (noch) nicht hinbekommen würde.
Doppelte Elemente gibt es in der Liste nicht und je nach dem wie weit man schon in der Saison fortgeschritten ist können es 0 bis etwa 40 Spieltage sein, die im Array stecken.
Martin schrieb am 19.09.2007
Man könnte das ganze auch in O(log n) statt O(n) Schritten lösen, indem man Intervallhalbierungen vornimmt und mittels Vergleich vom letzten abzüglich des ersten Wertes +1 (beide Werte aus der gleichen Hälfte) mit der Länge (des halbierten Arrays) nachsieht, ob es eine Lücke geben muss. Aber wenn es nicht sehr viele Spieltage sind, lohnt sich der Aufwand wohl nicht, zumal menschliche Arbeitszeit (zum Implementieren) teurer ist als Rechenzeit.
Beispiel:
[1, 2, 3, 4, 5, 7, 8, 9]
(Hier vielleicht erstmal prüfen, ob der erste Wert > 1 ist, denn dann ist 1 eine Lücke, aber das ändert an der Komplexität des beschriebenen Algorithmus nichts)
9-1+1 = 9 > [1, 2, 3, 4, 5, 7, 8, 9].len ? Lücke vorhanden
Erste Hälfte [1, 2, 3, 4] analysieren:
4-1+1 = 4 = [1, 2, 3, 4].len ? keine Lücke ? Lücke muss in der 2. Hälfte sein
[5, 7, 8, 9] halbieren:
[5, 7] analysieren:
7-5+1 = 3 > [5, 7].len ? Lücke ist in diesem Teilbereich
[5, 7].len enthält nur noch zwei Elemente, ist aber lückenhaft, also muss bei <erster Wert> + 1 (= 5 +1) eine Lücke sein.
Allerdings muss man da noch Sonderbehandlungen einbauen für den Fall, dass ein Bereich mit ungerader Elementanzahl halbiert werden soll (hatte erst 6 Elemente und dann beim Aufschreiben der Einfachheit halber es auf 8 Elemente vergrößert). Wie gesagt, wird sich wohl nur bei sehr großer Anzahl an Spieltagen lohnen.
Martin schrieb am 19.09.2007
Hm, in der Vorschau gingen die Folgepfeile (U+21D2) noch, jetzt sind dort Fragezeichen.
Jeena Paradies aus Varberg schrieb am 19.09.2007
Wenn ich das richtig verstehe, Martin, dann würde man aber die erste "freie" Zahl in [1,4,6,9,10,12,15,44], also die 2 gar nicht finden so, oder?
Daniel Thoma schrieb am 19.09.2007
Martin beschreibt doch genau das gleiche Verfahren wie ich. Die 2 würde man in drei Rekursionsschritten finden.
Eine Implementierung sähe etwa so aus:
int[] array; // eingabe int a = 0; int b = array.length - 1; while (a + 1 < b) { int pos = (b + a) / 2; if (array[pos] - array[a] + 1 < pos - a) { b = pos; } else { a = pos; } } if (array[a] < array[b] - 1) { return array[a] + 1; } else { return array.length + 1; }Das Ergebnis ist das nächste Element, wenn es keine Lücke gibt. Vermutlich ist irgendwo ein kleiner Fehler drin ;)
dedlfix schrieb am 19.09.2007
Hier noch eine einzeilige Lösung in Python, die nicht iterativ arbeitet.
Voraussetzung ist, dass matchdays sortiert vorliegt.
next = sorted(set(range(1, matchdays[-1])) - set(matchdays) | set([matchdays[-1] + 1]))[0]zeek schrieb am 20.09.2007
Die Funktion, die du suchst, heißt array_diff. Jedenfalls in php ;)
$alle_spieltage = array(); for( $i = 1; $i <= 40; ++$i ) { $alle_spieltage[] = $i; } $spieltage = array( 1, 2, 3, 5, 6, 7 ); $result = array_diff( $alle_spieltage, $spieltage ); reset($result); echo current($result)."\n";Ausgabe: 4
Zuerst wird ein Array mit allen Spieltagen erzeugt. Dies wird mit dem Array verglichen (mit array_diff), das die aktuellen Spieltage hält.
Das Ergebnis ist ein Array mit allen freien Spieltagen.
Mit reset() setzen wir nun den Zeiger auf das erste Element in diesem Array und geben es mit current() aus. Mit next() kann man weiter durch das Array laufen.
Falls es keine Lücke gibt, wird der nächste freie Spieltag ausgegeben...
Ich hoffe, dass dir das was bringt ;)
Tim schrieb am 20.09.2007
Hier endlich und nach diversen Umwegen eine Funktion für Python, die auch bei ewig lang laufenden Iteratoren funktioniert:
Henryk Plötz schrieb am 20.09.2007
Noch eine kleine Verbesserung für Tims tollen Vorschlag (und um die Schmach wettzumachen dass ich in meiner ersten Python-Lösung einen Fehler habe):
Tim schrieb am 20.09.2007
Für Daniel dagegen entspricht dies hier mehr seiner Intuition:
def pairwise(iterable): a, b = it.tee(iterable) try: b.next() except StopIteration: pass return it.izip(a, b) def daniel2(iterable): gaps = ((a + 1) for a, b in pairwise(it.chain([0], iterable, [sys.maxint])) if b - 1 > a) return gaps.next()Martin schrieb am 20.09.2007
Huch, der Kommentar von Daniel war noch nicht da, als ich meinen verfasst hab :) Und funktionieren sollte das eigentlich auch mit [1,4,6,9,10,12,15,44], wieso denn nicht? Das wählt dann halt 2x die linke Hälfte aus und gibt dann 1+1 (= 2) zurück.
[1,4,6,9,10,12,15,44]: 44-1+1 = 44 > 8, also Lücke vorhanden.
[1,4,6,9]: 9-1+1 = 8 > 4, also Lücke vorhanden.
[1,4]: 4-1+1 = 4 > 2, also Lücke vorhanden. Da es nur noch zwei Elemente sind, muss es bei 1+1 (= 2) sein.
Jeena Paradies aus Varberg schrieb am 20.09.2007
Danke, Martin, Daniel hat mir das jetzt hinter den Kulissen gaanz ausführlich erklärt und jetzt habe ich es kappiert :-)
Zeek, deinen Ansatz hatte ich im IRC-Chanel #ruby-lang heute Mittag auch bekommen: ([*1..40] - [1,2,3,5,6,7]).first, der Nachteil ist dass es ziemlich viel Rechenaufwand ist und man die Zahl 40 fest drinn haben muss, also fällt die Lösung als allgemeinlösung weg.
[update:] Ok ich verstehe jetzt dass man auch einfach die länge des Arrays anstatt der 40 nehmen kann, da man ja nicht alle Lücken sondern nur die erste braucht.
zeek schrieb am 20.09.2007
Die Länge welchen Arrays? Die Länge des kleineren kann man nicht nehmen, denn [1,2,3,5,6,7] würde Länge 6 zurückgeben. Wodurch die 7 nicht geprüft wird und man auch nicht den nächsten freien Tag bekäme, der frei wäre, wenn keine Lücke existiert.
Allerdings könnte man den letzten Eintrag aus dem Array nehmen und diesen Wert um einen erhöhen und ihn dann als Limit in der for Schleife anstatt der 40 benutzen.
Und wieso steht denn die Maximale Anzahl der Spieltage nicht fest? Das müsste man doch vorher wissen...
Man kann doch jeden anderen Wert nehmen, je nachdem wie lang die Saison ist. Das Ding müsste doch eh je nach Saison angepasst werden, oder?
Und das mit dem Rechenaufwand ist auch eh nebensächlich, oder?
Jeena Paradies aus Varberg schrieb am 20.09.2007
zeek, man kann die länge des kleineren nehmen, das ist ja gerade der Witz dabei. Genau aus dem gleichen Grund wie bei der Lösung von Daniel und Martin. Die 7 muss nie geprüft werden wenn es eine Lücke gibt, denn das wäre ja nicht der nächste freie dat, die 4 ist ja schon der nächste freie Tag. Und prüfen ob es überhaupt eine Lücke gibt ist ja einfach und geht sau schnell: array[array.length - 1] == array.length
Die maximale Anzahl der Spieltage ist nicht fest, weil die variieren kann. Tut sie ja jetzt schon von Land zu Land, von Liga zu Liga, von Sportart zu Sportart. Wenn der DFB beschließt mehr Mannschaften in die erste Liga zu legen müsste man das Programm anpassen, das ist mehr als suboptimal, vor allem wenn man alles neu kompilieren und die neue Version dann an verschiedene Stellen legen muss.
Das mit dem Rechenaufwand ist nicht wirklich nebensächlich, ok vielleicht wenn man für Microsoft arbeitet ^^, es ging ja auch darum das ganze von der theoretischen Seite zu durchleuchten und mögliche Lösungsansätze aufgezeigt zu bekommen. Auf Daniels und Martins Lösung wäre ich zum Beispiel nie gekommen.
Martin schrieb am 20.09.2007
Das Beispiel von zeek ([1,2,3,5,6,7]) ist gut, denn es zeigt, wie leicht man bei der nichtlinearen Lösung Fehler einbaut :) Oben hatte ich vom Fehlen der Lücke in der ersten Hälfte darauf geschlossen, dass die Lücke in der zweiten Hälfte sein muss. Aber nein, hier ist sie genau zwischen den Teilen.
Ach und Jeena, dein Vergleich des letzten Elements mit der Länge klappt so eigentlich auch nur am Anfang, später muss man den Wert des ersten Elements berücksichtigen (beispielsweise bei [1, 2, 3, 4] hat man dann ja im zweiten Schritt nur noch [3, 4] mit der Länge 2, was aber lückenlos ist).
Mickey schrieb am 21.09.2007
Hi, na leider kann ich dir da nicht weiterhelfen.
Aber da du ja schon soooo viele Kommentare bekommenhast
ist das ja sicherlich nicht weiter schlimm :-(
Dennoch denke ich das bei dieser Vielzahl doch einige gute Ansätze dabei sind.
Beste Grüße
Mickey
Wolfgang aus Germany schrieb am 19.06.2008
Hi,
da der Beitrag wohl schon ein bisschen älter ist, ist es wohl nicht mehr so richtig relevant, aber wenn du es, meiner Meinung nach, am performantesten haben möchtest solltest du es direkt in der DB machen.
SELECT id+1 FROM test WHERE (id+1) NOT IN (SELECT id FROM test) order by id LIMIT 1