gegebene aufgabe:
ein string von nullen und einsen der länge n soll in k Segmente unterteilt werden (z.b. 3 segmente: 0010111#0110000010#11101) und zwar so, dass die gesamtsumme der 'exceptions' minimal ist, wobei die zahl der exceptions auf einem segment die minderheit der zeichen darstellt.
in obigem beispiel hätten wir im ersten segment 4 einsen und 3 nullen, also 3 exceptions, im zweiten segment sind es auch 3 exceptions (die einsen) und im letzten segment ist nur mehr eine null störend. gesamt: 7 exceptions.
so, jetzt: man programmiere ein programm (in pseudo-code), welches in LAUFZEIT O(k*n) die optimale lösung ausspuckt, d.h. die position der delimiter "#". dabei sei k natürlich kleiner als n
das ganze war ein wettbewerb, dessen deadline abgelaufen ist. ich werde nachdem counts lösung vollständig entschlüsselt wurde, den korrekten algo in pseudo code angeben, der in der tat nur O(kn) braucht, was vermutlich nicht zu toppen ist. der algo braucht aber leider auch O(kn) memory, was vielleicht besser geht, da bin ich mir derzeit net sicher.
anbei ein proof of correctness und für alle DP-freaks noch die backtracing-info.
selbst wenn niemand das preisgeld verdient haben sollte, werd ich garantiert trostpreise o.ä. verteilen ^^
@prinegon:
dein algo liefert leider nur local optimale lösungen. das einfügen von delimitern in segmente ist generell schlecht, weil die segmente abwechselnd einsen und nullen als mehrheit haben. wenn du da jetzt irgendein segment teilst, und das ist weder am ende noch am anfang, dann erschaffst du definitiv zwei nebeneinanderliegende segmente, welche gleiche mehrheit haben -> da könnte man den delimiter auch gleich weglassen ^^
@count: dein algo ist im grundprinzip korrekt, aber so wie ich das derzeit entschlüssle, kopierst du arrays der größe O(k)/O(n) in deiner inneren schleife, was leider deine laufzeit aufblähen würde.
@damh: dein algo ist ganz schön kompliziert - aber interessant ^^ und wie du selbst schon gemerkt hast, ist er net in O(kn).
jemand ahnung von dynamischer programmierung?
jemand ahnung von dynamischer programmierung?
Zuletzt geändert von kane am 28. Sep 2006, 21:06, insgesamt 1-mal geändert.
Mich würde zumindest die Lösungsstrategie interessieren. Wäre cool, falls du eine Lösung hast, dass du die hier reinstellst.
Im Moment tippe ich auf das 0/1-Rucksackproblem, aber sicher bin ich mir nicht so recht.
Ich nehm mal an, der Aufbau der Tabelle für die Darstellung der Teilprobleme zählt noch nicht mit in deiner Komplexitätsangabe, oder?
Im Moment tippe ich auf das 0/1-Rucksackproblem, aber sicher bin ich mir nicht so recht.
Ich nehm mal an, der Aufbau der Tabelle für die Darstellung der Teilprobleme zählt noch nicht mit in deiner Komplexitätsangabe, oder?
Okay, Grundidee:
für die k-te Unterteilung eines Segments wähle das (mehrelementige) Teilsegment mit den meisten Exceptions (bei mehreren Segmenten mit gleich vielen Exceptions wähle irgendeines der Segmente aus. Wichtig: k<n, so daß es mind. 1 mehrelementiges Segment gibt).
Sei A= 010011101100 und bereits unterteilt worden in 0100111 und 01100
Das Teilelement mit den meisten Exceptions ist 0100111.
Nun wandern wir für die k-te Unterteilung mit 2 Zeigern durch die Elemente (ich gehe der Einfachheit von einem n-elementigen Array aus, könnte aber auch ne Liste sein), mit den Indexen p von vorne und q von hinten. Des weiteren brauche ich noch je eine Variable die oBdA die Anzahl der Nullen speichert, die ich bislang abgezählt habe (nenne sie p_null und q_null). Abbruchbedingung: p=(n-q) {z.B. durch repeat--- until p==(n-q-1)(das ist die letzte Schleife, die durchlaufen werden muß)}
Ausgangssituation: p=0, q=n+1 (n Anzahl der Elemente im Teilsegment).
Somit pAq = p0100111q. p_null, q_null == 0 und und p_ex = min{p_null, p-p_null}, q_ex = min{q_null, ((q-q_null} == 0
Nun wandere ich mit p solange weiter, bis die Anzahl der Exceptions höher ist, als k_ex (== 0).
p=1, also 0p100111q p_null == 1, p_ex == 0.
p=2, also 01p00111q p_null == 1, p_ex == min{1,(2-1)} == 1
Nun wandere ich mit q solange weiter, bis die Anzahl der Exceptions höher ist, als p_ex.
q=1, also 01p0011q1, q_null == 0, q_ex == min{0,(1-0)} = 0
q=2, also 01p001q11, q_null == 0, q_ex == min{0,(2-0)} = 0
q=3, also 01p00q111, q_null == 0, q_ex == min{0,(3-0)} = 0
q=4, also 01p0q0111, q_null == 1, q_ex == min{1,(4-1)} = 1
q=5, also 01pq00111, q_null == 2, q_ex == min{2,(5-2)} = 2
break;
Somit zum Ende: p==2, p_null == 1, p_ex == 1, q==5, q_null==2, q_ex == 2), und die Unterteilung:
01, 00111.
Zum Schluß muß noch eine Ausnahme geregelt werden:
falls A(p) == A(q):
Wählten wir unser Beispiel etwas anders, z.B. 01000111, so wären alle Schritte wie bisher durchgeführt worden, nur daß als letzte Operation hinzugekommen wäre:
p=2, also 010pq00111 p_null == 2, p_ex == min{2,(3-2)} == 1
A(p) == 0, A(q) == 0;
Nun wäre es sinnvoll, die überzähligen Nullen von q p zuzuordnen, da es die Anzahl der exceptions von q erniedrigt, die von p unbeeinflußt läßt (in einem solchen Fall, daß A(p) == A(q) kann IMMER eine Exceptionzahl erniedrigt werden, wobei die andere unbeeinflußt bleibt).
Also muß nun auf 4 Fälle überprüft werden:
case:
A(p) (== A(q)) == 1, p_null<=(p-p_null)
somit sind die Anzahl der Nullen bestimmend für die Exceptions des P-Teilsegments.
-> while (A(q) == 1) { p++, q--} die überflüssigen Einsen von q nach p verschieben.
A(p) (== A(q)) == 1, p_null>(p-p_null)
somit sind die Anzahl der Einsen bestimmend für die Exceptions des P-Teilsegments.
-> while (A(p) == 1) { p--, q++} die überflüssigen Einsen von p nach q verschieben.
A(p) (== A(q)) == 0, p_null<=(p-p_null)
somit sind die Anzahl der Nullen bestimmend für die Exceptions des P-Teilsegments.
-> while (A(q) == 0) { p--, q++} die überflüssigen Nullen von p nach q verschieben.
A(p) (== A(q)) == 0, p_null>(p-p_null)
somit sind die Anzahl der Einsen bestimmend für die Exceptions des P-Teilsegments.
-> while (A(p) == 0) { p++, q--} die überflüssigen Nullen von q nach p verschieben.
Zum Schluß muß noch sichergestellt werden, daß beide Teilsegmente mindestens einelementig sind. Also
if (q == n) {q=n, p--} (diese Überprüfung fällt weg, wenn man gleich mit q=n startet und q_null berechnet, habe ich für die Erklärung nicht gemacht, um dich nicht zu verwirren, ist im Code aber kein Problem).
Beweis von O(k*n):
Beweise: für eine Unterteilung ist der Aufwand O(n).
oBdA gehe davon aus, daß ich mit p A einmal durchwandere (ob ich nun mit p A durchwandere, oder mit p einen Teil und mit q den anderen, ist aufwandsmäßig gleich). Alle Operationen, die ich bei der Überprüfung von P ausführe, sind O(0) und nicht von n abhängig (das Berechnen von p_null ist eine if-Abfrage und ein Increment, das Berechnen von p_ex ist eine Substraktion, zwei Abfragen und eine Minimumsbestimmung.
Insofern ist der Aufwand zum Überprüfen eines Elements O(0). Das muß für n Elemente je ein Mal geschehen, also O(0) * n -> O(n)
Nun zur Ausnahmeregelung. Hier muß ich maximal für n Elemente überprüfen, ob die Elemente gleich sind. Also auch maximal O(n). Somit der Gesamtaufwand O(n) + O(n) = o(n).
Schließlich müssen k Unterteilungen von Teilarrays vorgenommen werden, wobei jedes Teilarray <= n Elemente besitzt. Also 0(n)*k -> O(k*n) qed.
Den Pseudocode dazu mußt du dann schon selbst machen, will dir ja nicht alles abnehmen, aber der sollte nun wirklich kein Problem mehr sein.
für die k-te Unterteilung eines Segments wähle das (mehrelementige) Teilsegment mit den meisten Exceptions (bei mehreren Segmenten mit gleich vielen Exceptions wähle irgendeines der Segmente aus. Wichtig: k<n, so daß es mind. 1 mehrelementiges Segment gibt).
Sei A= 010011101100 und bereits unterteilt worden in 0100111 und 01100
Das Teilelement mit den meisten Exceptions ist 0100111.
Nun wandern wir für die k-te Unterteilung mit 2 Zeigern durch die Elemente (ich gehe der Einfachheit von einem n-elementigen Array aus, könnte aber auch ne Liste sein), mit den Indexen p von vorne und q von hinten. Des weiteren brauche ich noch je eine Variable die oBdA die Anzahl der Nullen speichert, die ich bislang abgezählt habe (nenne sie p_null und q_null). Abbruchbedingung: p=(n-q) {z.B. durch repeat--- until p==(n-q-1)(das ist die letzte Schleife, die durchlaufen werden muß)}
Ausgangssituation: p=0, q=n+1 (n Anzahl der Elemente im Teilsegment).
Somit pAq = p0100111q. p_null, q_null == 0 und und p_ex = min{p_null, p-p_null}, q_ex = min{q_null, ((q-q_null} == 0
Nun wandere ich mit p solange weiter, bis die Anzahl der Exceptions höher ist, als k_ex (== 0).
p=1, also 0p100111q p_null == 1, p_ex == 0.
p=2, also 01p00111q p_null == 1, p_ex == min{1,(2-1)} == 1
Nun wandere ich mit q solange weiter, bis die Anzahl der Exceptions höher ist, als p_ex.
q=1, also 01p0011q1, q_null == 0, q_ex == min{0,(1-0)} = 0
q=2, also 01p001q11, q_null == 0, q_ex == min{0,(2-0)} = 0
q=3, also 01p00q111, q_null == 0, q_ex == min{0,(3-0)} = 0
q=4, also 01p0q0111, q_null == 1, q_ex == min{1,(4-1)} = 1
q=5, also 01pq00111, q_null == 2, q_ex == min{2,(5-2)} = 2
break;
Somit zum Ende: p==2, p_null == 1, p_ex == 1, q==5, q_null==2, q_ex == 2), und die Unterteilung:
01, 00111.
Zum Schluß muß noch eine Ausnahme geregelt werden:
falls A(p) == A(q):
Wählten wir unser Beispiel etwas anders, z.B. 01000111, so wären alle Schritte wie bisher durchgeführt worden, nur daß als letzte Operation hinzugekommen wäre:
p=2, also 010pq00111 p_null == 2, p_ex == min{2,(3-2)} == 1
A(p) == 0, A(q) == 0;
Nun wäre es sinnvoll, die überzähligen Nullen von q p zuzuordnen, da es die Anzahl der exceptions von q erniedrigt, die von p unbeeinflußt läßt (in einem solchen Fall, daß A(p) == A(q) kann IMMER eine Exceptionzahl erniedrigt werden, wobei die andere unbeeinflußt bleibt).
Also muß nun auf 4 Fälle überprüft werden:
case:
A(p) (== A(q)) == 1, p_null<=(p-p_null)
somit sind die Anzahl der Nullen bestimmend für die Exceptions des P-Teilsegments.
-> while (A(q) == 1) { p++, q--} die überflüssigen Einsen von q nach p verschieben.
A(p) (== A(q)) == 1, p_null>(p-p_null)
somit sind die Anzahl der Einsen bestimmend für die Exceptions des P-Teilsegments.
-> while (A(p) == 1) { p--, q++} die überflüssigen Einsen von p nach q verschieben.
A(p) (== A(q)) == 0, p_null<=(p-p_null)
somit sind die Anzahl der Nullen bestimmend für die Exceptions des P-Teilsegments.
-> while (A(q) == 0) { p--, q++} die überflüssigen Nullen von p nach q verschieben.
A(p) (== A(q)) == 0, p_null>(p-p_null)
somit sind die Anzahl der Einsen bestimmend für die Exceptions des P-Teilsegments.
-> while (A(p) == 0) { p++, q--} die überflüssigen Nullen von q nach p verschieben.
Zum Schluß muß noch sichergestellt werden, daß beide Teilsegmente mindestens einelementig sind. Also
if (q == n) {q=n, p--} (diese Überprüfung fällt weg, wenn man gleich mit q=n startet und q_null berechnet, habe ich für die Erklärung nicht gemacht, um dich nicht zu verwirren, ist im Code aber kein Problem).
Beweis von O(k*n):
Beweise: für eine Unterteilung ist der Aufwand O(n).
oBdA gehe davon aus, daß ich mit p A einmal durchwandere (ob ich nun mit p A durchwandere, oder mit p einen Teil und mit q den anderen, ist aufwandsmäßig gleich). Alle Operationen, die ich bei der Überprüfung von P ausführe, sind O(0) und nicht von n abhängig (das Berechnen von p_null ist eine if-Abfrage und ein Increment, das Berechnen von p_ex ist eine Substraktion, zwei Abfragen und eine Minimumsbestimmung.
Insofern ist der Aufwand zum Überprüfen eines Elements O(0). Das muß für n Elemente je ein Mal geschehen, also O(0) * n -> O(n)
Nun zur Ausnahmeregelung. Hier muß ich maximal für n Elemente überprüfen, ob die Elemente gleich sind. Also auch maximal O(n). Somit der Gesamtaufwand O(n) + O(n) = o(n).
Schließlich müssen k Unterteilungen von Teilarrays vorgenommen werden, wobei jedes Teilarray <= n Elemente besitzt. Also 0(n)*k -> O(k*n) qed.
Den Pseudocode dazu mußt du dann schon selbst machen, will dir ja nicht alles abnehmen, aber der sollte nun wirklich kein Problem mehr sein.
Das Gegenteil von "gut" ist "gut gemeint".
Es ist nur Sand. Doch manchmal kann auch Sand töten...
Es ist nur Sand. Doch manchmal kann auch Sand töten...
-
Count Ypsilon
- Kriechlapf
- Beiträge: 52
- Registriert: 5. Jun 2006, 23:23
Code: Alles auswählen
#!/usr/bin/perl
use Storable qw/dclone/;
use Data::Dumper;
my $string = "0101101111011111101111111111";
my $n = length($string);
my $k = 4;
# #################################################################
# Das Skript findet eine Unterteilung des Strings $string in genau
# $k Segmente, wobei die Summe der "Exceptions" aller Segmente
# minimal ist. "Exceptions" sind die selteneren Ziffern in einem
# Segment.
#
# Laufzeit O(n*k) - leicht ersichtlich an den beiden for-Schleifen.
# #################################################################
#
# Wir beginnen mit einer einzigen unfertigen Loesung,
# bei der noch keine Delimiter gesetzt sind, die keine
# Exceptions hat und im aktuellen Segment daher auch keine
# Nullen und Einsen.
my $loesung = [
{ "delimiters" => [], # Positionen der bislang gesetzen Delimiter
"exceptions" => 0, # Summe Exceptions der abgeschlossenen Segmente
"nullen" => 0, # Summe Nullen im offenen Segment
"einsen" => 0 # Summe Einsen im offenen Segment
}
];
# Zeichen fuer Zeichen abarbeiten
for ($i=0; $i<$n; $i++)
{
$zeichen = substr($string, $i, 1);
# Alle Loesungen, die noch nicht alle Delimiter verbraucht
# haben, duerfen an der aktuellen Position einen setzen.
# (Ausnahme: aktuelle Position = 0)
if ($i > 0)
{
my $loesung_neu = dclone($loesung);
for ($j = 0; $j < $k-1; $j++)
{
# Verwendung des Arrays $loesung: $loesung[x] ist immer
# die bislang (also bis zu dieser Position i im String)
# beste Loesung mit x Delimitern. Es reicht, immer die
# bislang beste zu jeder Delimiter-Zahl aufzuheben,
# denn wenn zwei Loesungen gleichviele Exceptions
# haben, eine davon aber schon mehr Delimiter verbraucht
# hat, wird sie das nie "aufholen".
if (defined($loesung->[$j]))
{
# dclone = kopie der ganzen struktur
$neue_lsg = dclone($loesung->[$j]);
# Delimiter setzen
# (i+1, weil fuer Menschen das 1. Zeichen den Index 0 hat)
push(@{$neue_lsg->{"delimiters"}}, $i + 1);
# Exceptions im so abgeschlossenen Segment ermitteln
my $ex = $neue_lsg->{"einsen"};
$ex = $neue_lsg->{"nullen"} if ($neue_lsg->{"nullen"} < $ex);
# Exception-Zaehler hochzaehlen, Einsen und Nullen reset
$neue_lsg->{"exceptions"} += $ex;
$neue_lsg->{"nullen"} = 0;
$neue_lsg->{"einsen"} = 0;
# nun pruefen, ob die neue Loesung, die jetzt $j+1
# Delimiter braucht, besser oder gleich gut ist wie
# die bislang beste mit $j+1 Delimitern:
my $vergleich = $loesung_neu->[$j+1];
if (!defined($vergleich))
{
# es gibt noch gar keine mit $j+1
$loesung_neu->[$j+1] = $neue_lsg;
}
else
{
# wenn ein Stream laenger wird, kann die Anzahl der Exceptions nie
# kleiner werden, daher ist es zulaessig, die Exception-Zahl auch
# fuer ein nicht abgeschlossenes Segment zu ermitteln.
$ex = $vergleich->{"einsen"};
$ex = $vergleich->{"nullen"} if ($vergleich{"nullen"} < $ex);
$ex += $vergleich->{"exceptions"};
$loesung_neu->[$j+1] = $neue_lsg if ($ex >= $neue_lsg->{"exceptions"});
}
}
}
$loesung = $loesung_neu;
}
# Nullen/Einsen in allen Loesungen hochzaehlen
foreach my $lsg(@{$loesung})
{
$lsg->{"nullen"}++ if ($zeichen eq "0");
$lsg->{"einsen"}++ if ($zeichen eq "1");
}
}
# Array $loesung enthaelt nun an Position $k-1
# die beste Loesung mit $k segmenten (also $k-1 delimitern)
# Exceptions fuer das letzte Segment sind noch nicht gezaehlt
my $lsg = $loesung->[$k-1];
my $ex = $lsg->{"einsen"};
$ex = $lsg->{"nullen"} if ($lsg->{"nullen"} < $ex);
$lsg->{"exceptions"} += $ex;
print "Beste Loesung: ".$lsg->{"exceptions"}." Exceptions\n";
print "Delimiters vor den Positionen ".join(", ", @{$lsg->{"delimiters"}})."\n";
my $p=0;
foreach my $delim(@{$lsg->{"delimiters"}}, length($string))
{
print substr($string, $p, $delim-$p-1);
print "#" if ($delim < length($string));
$p=$delim-1;
}
print "\n";
Hi!
@Prin: Du hast die Aufgabe nicht richtig verstanden. (Ging mir übrigens genauso am Anfang) Das von Dir gelöste Problem kann man übrigens noch einfacher lösen
Es geht nicht darum möglichst gleich viele Nullen und Einsen in jedem Segment zu bekommen, sondern möglichst viele von der einen Sorte und möglichst keine von der anderen!
Ein Beispiel für Eingabe und korrekte optimale Antwort:
Gruß damh
@Prin: Du hast die Aufgabe nicht richtig verstanden. (Ging mir übrigens genauso am Anfang) Das von Dir gelöste Problem kann man übrigens noch einfacher lösen
Es geht nicht darum möglichst gleich viele Nullen und Einsen in jedem Segment zu bekommen, sondern möglichst viele von der einen Sorte und möglichst keine von der anderen!
Ein Beispiel für Eingabe und korrekte optimale Antwort:
Code: Alles auswählen
Input= 1110101000101000101
Max. fragments (k)=3
Minimum der gesamten Ausnahmen=5
Benutzte Unterteilungen=2
Best:
erg=111 0101000101000 101
erg=111 010100010100010 1
erg=11101 01000101000 101
erg=11101 0100010100010 1
erg=1110101 000101000 101
erg=1110101 00010100010 1
also inzwischen hatte ich etwa 1h nach eröffnung des threads einen stroke of genius und jetzt weiß ich wie ich es lösen muss.
damit beende ich die deadline adhoc ^^
werde mir gleich mal die lösungen anschauen, natürlich halte ich mich an das, was ich gesagt habe, falls bisher eine korrekte lösung eingereicht wurde.
nur die erste korrekte lösung inklusive damh kriegen was (weil ich den schon so viel genervt habe ^^)
ob PM, FV oder post hier im thread, ist mir als eingereichte arbeit egal gewesen und natürlich kriegt nicht jeder, der die lösng eines anderen kopiert auch was ^^
damh: danke für deine hilfe, auch wenn ich sie am ende leider nicht wirklich genutzt habe. aber deine baumidee finde ich generell unheimlich interessant, weil das wäre mir wohl als allerletztes gekommen.
was deine algorithmen angeht: also die letzten beiden deines progs sind way too slow, aber der erste ist ziemlich fast, den muss ich mal genauer begutachten ^^
damit beende ich die deadline adhoc ^^
werde mir gleich mal die lösungen anschauen, natürlich halte ich mich an das, was ich gesagt habe, falls bisher eine korrekte lösung eingereicht wurde.
nur die erste korrekte lösung inklusive damh kriegen was (weil ich den schon so viel genervt habe ^^)
ob PM, FV oder post hier im thread, ist mir als eingereichte arbeit egal gewesen und natürlich kriegt nicht jeder, der die lösng eines anderen kopiert auch was ^^
damh: danke für deine hilfe, auch wenn ich sie am ende leider nicht wirklich genutzt habe. aber deine baumidee finde ich generell unheimlich interessant, weil das wäre mir wohl als allerletztes gekommen.
was deine algorithmen angeht: also die letzten beiden deines progs sind way too slow, aber der erste ist ziemlich fast, den muss ich mal genauer begutachten ^^
damh: Dann hast du meinen Lösungsansatz nicht verstanden. Ich versuche gar nicht, möglichst gleichviele Nullen und Einsen zu haben, sondern ich unterteile einen String S in zwei Teilstrings, in denen möglichst gleich viele exceptions vorkommen, wobei der eine Teilstring von der linken Seite gezählt, der zweite von der rechten Seite gezählt wird.
Ich zähle nur die Nullen im String und errechne die Anzahl der Einsen als Anzahl der gezählten Elemente - Anzahl der Nullen. Aber ich unterteile den String in zwei Teilstrings, die möglichst gleich viele Exceptions haben, da das insgesamt die wenigsten Fehlerstellen geben wird.
Ich zähle nur die Nullen im String und errechne die Anzahl der Einsen als Anzahl der gezählten Elemente - Anzahl der Nullen. Aber ich unterteile den String in zwei Teilstrings, die möglichst gleich viele Exceptions haben, da das insgesamt die wenigsten Fehlerstellen geben wird.
Das Gegenteil von "gut" ist "gut gemeint".
Es ist nur Sand. Doch manchmal kann auch Sand töten...
Es ist nur Sand. Doch manchmal kann auch Sand töten...
prinegon, deine lösung ist aber nicht zwingend korrekt.
111000000000100000000000 # 11111111110000011111111111111100
hier ist der delimiter optimal gesetzt. dein algo würde den rechten string wählen und den delimiter dort setzen:
111000000000100000000000 # 111111111100000111111111111111 # 0
optimal wäre mit 2 delimitern aber:
111 # 000000000100000000000 # 1111111111000011111111111111100
Count: mein perl-wissen ist leider net das beste. kannst du mal ganz pseudomäßig beschreiben, was du in der innersten schleife genau machst?
111000000000100000000000 # 11111111110000011111111111111100
hier ist der delimiter optimal gesetzt. dein algo würde den rechten string wählen und den delimiter dort setzen:
111000000000100000000000 # 111111111100000111111111111111 # 0
optimal wäre mit 2 delimitern aber:
111 # 000000000100000000000 # 1111111111000011111111111111100
Count: mein perl-wissen ist leider net das beste. kannst du mal ganz pseudomäßig beschreiben, was du in der innersten schleife genau machst?
if (defined($loesung->[$j]))
// was heißt denn das? wichtig? ne, denk net.
{
# dclone = kopie der ganzen struktur
$neue_lsg = dclone($loesung->[$j]);
// ....kopieren der ganzen struktur? kopierst du da ein array? das wäre schlecht, da kopieren zeit kostet, wenn dein array O(k)/O(n) felder groß ist, dann is dein algo zu langsam
# Delimiter setzen
# (i+1, weil fuer Menschen das 1. Zeichen den Index 0 hat)
push(@{$neue_lsg->{"delimiters"}}, $i + 1);
// quak, das kann ich beim besten willen net entziffern ^^
// was heißt denn das? wichtig? ne, denk net.
{
# dclone = kopie der ganzen struktur
$neue_lsg = dclone($loesung->[$j]);
// ....kopieren der ganzen struktur? kopierst du da ein array? das wäre schlecht, da kopieren zeit kostet, wenn dein array O(k)/O(n) felder groß ist, dann is dein algo zu langsam
# Delimiter setzen
# (i+1, weil fuer Menschen das 1. Zeichen den Index 0 hat)
push(@{$neue_lsg->{"delimiters"}}, $i + 1);
// quak, das kann ich beim besten willen net entziffern ^^
-
Count Ypsilon
- Kriechlapf
- Beiträge: 52
- Registriert: 5. Jun 2006, 23:23
Das Array hat maximal k-1 Elemente, das Kopieren ist vernachlässigbar und auch nur aus Bequemlichkeit so gemacht, wenn es nicht bloss auf das O-Kalkuel ankommt, sondern davon unabhaengig auch noch schnell gehen soll ;-) kann man das effizienter machen.kane hat geschrieben: // ....kopieren der ganzen struktur? kopierst du da ein array? das wäre schlecht, da kopieren zeit kostet, wenn dein array O(k)/O(n) felder groß ist, dann is dein algo zu langsam
Ich hatte gedacht, Perl ist so simpel, dass es jeder verstehen muss ;-) also sorry, war wohl n Fehler. An der Stelle wird einfach die aktuelle Position in die Liste der Delimiter hinzugefuegt!kane hat geschrieben: push(@{$neue_lsg->{"delimiters"}}, $i + 1);
// quak, das kann ich beim besten willen net entziffern ^^
Leider habe ich anhand von damhs Beispiel mittlerweile feststellen muessen, dass mein Programm in dem Fall an der besten Loesung vorbei schlittert. Es ist also zwar sehr schnell, tut aber nicht, was es soll ;-)
Das Problem ist meine Annahme, dass ich mir zu jeder Anzahl Delimiter nur die bisher beste Loesung merken muesse, oder anders gesagt: Dass der erste Delimiter der besten Loesung mit 3 Delimitern immer auch der (einzige) Delimiter der besten Loesung mit nur einem Delimiter sein muss. Das stimmt aber nicht. Ich denke zwar, dass ich es noch retten kann, aber das probiere ich dann mal in Ruhe als Bastelaufgabe - ist ja jetzt, wo offenbar Loesungen gefunden wurden, akademisch.
In jedem Fall wird aber meine Herangehensweise nur *eine* optimale Loesung und nie *alle* liefern.
Y.
Ich will mal meine Version auch nicht vorenthalten.
Sie scheint so weit ich es getestet habe zu funktionieren und besteht aus 3 verschiedenen Lösungsansätzen.
Version 2 mit unkompletter Ausgabe ist die schnellste für große k(Segmentzahl) und n(Wortlänge).
Für kleine k und n ist Version 1 schneller und liefert eine vollständige Antwort.
Bei großen k und n und vollständiger Ausgabe sollte Version 2 mit kompletter Ausgabe genommen werden.
Die O-Klasse kann ich nicht genau angeben (bzw. habe ich gerade keine Lust zu). Sie ist allerdings glaube ich schlechter als O(kn)
Sourcecode: (ohne Dokumentation)
http://home.tu-clausthal.de/~jv/SplitString.java
Gruß damh
bzw. hier: (Die Tabs werden leider falsch angezeigt im Forum)
Sie scheint so weit ich es getestet habe zu funktionieren und besteht aus 3 verschiedenen Lösungsansätzen.
Version 2 mit unkompletter Ausgabe ist die schnellste für große k(Segmentzahl) und n(Wortlänge).
Für kleine k und n ist Version 1 schneller und liefert eine vollständige Antwort.
Bei großen k und n und vollständiger Ausgabe sollte Version 2 mit kompletter Ausgabe genommen werden.
Die O-Klasse kann ich nicht genau angeben (bzw. habe ich gerade keine Lust zu). Sie ist allerdings glaube ich schlechter als O(kn)
Sourcecode: (ohne Dokumentation
)http://home.tu-clausthal.de/~jv/SplitString.java
Gruß damh
bzw. hier: (Die Tabs werden leider falsch angezeigt im Forum
)
Code: Alles auswählen
import java.io.*;
import java.util.*;
public class SplitString
{
String input;
int maxfrag;
SplitString(String input, int maxfrag, int version)
{
long startzeit= (new Date()).getTime();
long endzeit=0;
if (version==1)
{
System.out.println("************************************************");
System.out.println("******** Version 1: ****************************");
System.out.println("************************************************");
this.input=input;
this.maxfrag=maxfrag;
Vector<BaumElement> oldlist= new Vector<BaumElement>();
Vector<BaumElement> newlist= new Vector<BaumElement>();
BaumElement tmp= new BaumElement(0,0,0,0,'w',"");
oldlist.add(tmp);
boolean letzter=false;
int mingex=Integer.MAX_VALUE;
for (int i=0; i<input.length(); i++)
{
char momch= input.charAt(i);
// System.out.println("Char "+i+"= "+momch+"; oldlist.size()="+oldlist.size());
if (i==input.length()-1) letzter=true;
for (int j=0; j<oldlist.size(); j++)
{
BaumElement oldbe= oldlist.get(j);
BaumElement newbe= null;
if (oldbe.zweigtyp==momch)
{
oldbe.ok++;
oldbe.weg.append(momch);
newlist.add(oldbe);
if ((letzter) && (oldbe.gex<mingex)) mingex=oldbe.gex;
} else if (oldbe.zweigtyp=='w')
{
oldbe.zweigtyp=momch;
oldbe.ok++;
oldbe.weg.append(momch);
newlist.add(oldbe);
if ((letzter) && (oldbe.gex<mingex)) mingex=oldbe.gex;
} else {
newbe= new BaumElement(oldbe.knicke+1, 0,
1, oldbe.gex, momch,
oldbe.weg.toString()+" "+momch);
if (newbe.knicke<maxfrag)
{
newlist.add(newbe);
if ((letzter) && (newbe.gex<mingex)) mingex=newbe.gex;
}
oldbe.ex++;
oldbe.gex++;
oldbe.weg.append(momch);
if (oldbe.ex<=oldbe.ok)
{
newlist.add(oldbe);
if ((letzter) && (oldbe.gex<mingex)) mingex=oldbe.gex;
}
else if (oldbe.knicke==0) {
oldbe.gex=oldbe.gex-oldbe.ex+oldbe.ok;
int tmp1=oldbe.ok;
oldbe.ok=oldbe.ex;
oldbe.ex=tmp1;
oldbe.zweigtyp=momch;
newlist.add(oldbe);
if ((letzter) && (oldbe.gex<mingex)) mingex=oldbe.gex;
}
}
}
oldlist.clear();
oldlist=newlist;
newlist=new Vector<BaumElement>();
}
endzeit= (new Date()).getTime();
System.out.println("mingex="+mingex);
int minknicke=Integer.MAX_VALUE;
for (int j=0; j<oldlist.size(); j++)
{
BaumElement oldbe= oldlist.get(j);
if (oldbe.gex<=mingex)
{
if (oldbe.knicke<minknicke) minknicke=oldbe.knicke;
// System.out.println(oldbe);
}
}
System.out.println("minknicke="+minknicke);
for (int j=0; j<oldlist.size(); j++)
{
BaumElement oldbe= oldlist.get(j);
if ((oldbe.gex<=mingex) && (oldbe.knicke<=minknicke))
{
System.out.println(oldbe);
}
}
} else {
//optimierte Version
if (complete)
{
System.out.println("************************************************");
System.out.println("******** Version 2: (ausführlich=langsam) ******");
System.out.println("************************************************");
} else {
System.out.println("************************************************");
System.out.println("******** Version 2: (schnell) ******************");
System.out.println("************************************************");
}
this.input=input;
this.maxfrag=maxfrag;
Vector<BaumElement> list= new Vector<BaumElement>();
Vector<Vector<BaumElement>> oldlisto= new Vector<Vector<BaumElement>>();
Vector<Vector<BaumElement>> newlisto= null;
BaumElement tmp= new BaumElement(0,0,0,0,'w',"");
list.add(tmp);
oldlisto.add(list);
boolean letzter=false;
int mingex=Integer.MAX_VALUE;
int size=0;
for (int i=0; i<input.length(); i++)
{
// double p=1.0*i/input.length();
// System.out.print(String.format("%f",p)+"%\n");
System.out.print(i+"/"+input.length()+" fertig. Letzte Listengröße= ");
boolean fast=false; // schnellste Variante ist, wenn es jedes Mal optimiert wird
if (letzter) fast=false;
else if ((i%10)==9) fast=false;
char momch= input.charAt(i);
size=0;
// System.out.print("Char "+i+"= "+momch+"; sum(oldlisto.*.size())=");
if (i==input.length()-1) letzter=true;
newlisto= new Vector<Vector<BaumElement>>();
for (int j=0; j<oldlisto.size()+1; j++)
{
Vector<BaumElement> leer= new Vector<BaumElement>();
newlisto.add(leer);
}
for (int j=0; j<oldlisto.size(); j++)
{
size+=oldlisto.get(j).size();
for (int k=0; k<oldlisto.get(j).size(); k++)
{
BaumElement oldbe= oldlisto.get(j).get(k);
BaumElement newbe= null;
if (oldbe.zweigtyp==momch)
{
oldbe.ok++;
oldbe.weg.append(momch);
if (momch=='0') insert(newlisto.get(j),oldbe,fast);
else insert(newlisto.elementAt(j+1),oldbe,fast);
if ((letzter) && (oldbe.gex<mingex)) mingex=oldbe.gex;
} else if (oldbe.zweigtyp=='w')
{
oldbe.zweigtyp=momch;
oldbe.ok++;
oldbe.weg.append(momch);
if (momch=='0') insert(newlisto.get(j),oldbe,fast);
else insert(newlisto.elementAt(j+1),oldbe,fast);
if ((letzter) && (oldbe.gex<mingex)) mingex=oldbe.gex;
} else {
newbe= new BaumElement(oldbe.knicke+1, 0,
1, oldbe.gex, momch,
oldbe.weg.toString()+" "+momch);
if (newbe.knicke<maxfrag)
{
if (momch=='0') insert(newlisto.get(j),newbe,fast);
else insert(newlisto.elementAt(j+1),newbe,fast);
if ((letzter) && (newbe.gex<mingex)) mingex=newbe.gex;
}
oldbe.ex++;
oldbe.gex++;
oldbe.weg.append(momch);
if (oldbe.ex<=oldbe.ok)
{
if (momch=='0') insert(newlisto.get(j),oldbe,fast);
else insert(newlisto.elementAt(j+1),oldbe,fast);
if ((letzter) && (oldbe.gex<mingex)) mingex=oldbe.gex;
}
else if (oldbe.knicke==0) {
oldbe.gex=oldbe.gex-oldbe.ex+oldbe.ok;
int tmp1=oldbe.ok;
oldbe.ok=oldbe.ex;
oldbe.ex=tmp1;
oldbe.zweigtyp=momch;
if (momch=='0') insert(newlisto.get(j),oldbe,fast);
else insert(newlisto.elementAt(j+1),oldbe,fast);
if ((letzter) && (oldbe.gex<mingex)) mingex=oldbe.gex;
}
}
}
}
for (int j=0; j<oldlisto.size(); j++)
{
oldlisto.elementAt(j).clear();
}
oldlisto.clear();
oldlisto=newlisto;
System.out.print(size+" \r");
}
System.out.println(input.length()+"/"+input.length()+" fertig. Letzte Listengröße= "+size+" ");
endzeit= (new Date()).getTime();
System.out.println("mingex="+mingex);
int minknicke=Integer.MAX_VALUE;
for (int j=0; j<oldlisto.size(); j++)
{
for (int k=0; k<oldlisto.get(j).size(); k++)
{
BaumElement oldbe= oldlisto.get(j).get(k);
if (oldbe.gex<=mingex)
{
if (oldbe.knicke<minknicke) minknicke=oldbe.knicke;
// System.out.println(oldbe);
}
}
}
System.out.println("minknicke="+minknicke);
System.out.println("Best:");
for (int j=0; j<oldlisto.size(); j++)
{
for (int k=0; k<oldlisto.get(j).size(); k++)
{
BaumElement oldbe= oldlisto.get(j).get(k);
if ((oldbe.gex<=mingex) && (oldbe.knicke<=minknicke))
{
System.out.println(oldbe);
}
}
}
System.out.println("Full:");
for (int j=0; j<oldlisto.size(); j++)
{
for (int k=0; k<oldlisto.get(j).size(); k++)
{
BaumElement oldbe= oldlisto.get(j).get(k);
System.out.println(oldbe);
}
}
}//Version 2 ende
long diff=endzeit-startzeit;
System.out.println("Benötigte Zeit in Millisekunden: "+diff);
}
static boolean complete=false;
private void insert(Vector<BaumElement> v, BaumElement be, boolean fast)
{
boolean found=false;
if (!fast)
{
for (int i=0; i<v.size(); i++)
{
BaumElement mombe= v.get(i);
if ((complete && (be.knicke<mombe.knicke) && (be.gex<mombe.gex)) //es werden alle besten Versionen gehalten => ausführliche Version (benötigt mehr Speicher und Rechenzeit)
|| (!complete && (be.knicke<=mombe.knicke) && (be.gex<=mombe.gex))) //es wird nur eine beste Version gehalten => deutlich schnellere Version, dafür gibt es aber nur eine Lösung aus der Menge der optimalsten Lösungen
{
if (!found) v.set(i,be);
else {
v.remove(i);
i--;
}
found=true;
} else if ((be.knicke>mombe.knicke) && (be.gex>mombe.gex))
{
found=true;
}
}
}
if (!found) v.add(be);
}
public static void main(String argv[])
{
String input= argv[0];
int k=Integer.valueOf(argv[1]);
if (k<1)
{
System.out.println("Illegal fragmentnumber: "+k);
System.exit(255);
}
System.out.println("Input= "+input);
System.out.println("Max. fragments (k)="+k);
complete=false;
SplitString spstr= new SplitString(input, k, 2);
complete=true;
spstr= new SplitString(input, k, 2);
spstr= new SplitString(input, k, 1);
/* int relativeHoehe=0;
int[] absoluteHoehe= new int[input.length()];
// Baumstruktur aufbauen
for (int i=0; i<input.length(); i++)
{
if (input.charAt(i)=='0')
{
relativeHoehe++;
absoluteHoehe[i]=relativeHoehe;
}
else if (input.charAt(i)=='1')
{
relativeHoehe--;
absoluteHoehe[i]=relativeHoehe;
}
else {
String fmt= "%"+i+"s^";
System.out.println("Illegal character:\n"+
input+"\n"+
String.format(fmt, ""));
System.exit(255);
}
}
// Auswerten der Ergebnisse
System.out.println("relative height: "+relativeHoehe);
int experfrag= (int)Math.ceil(1.0f*Math.abs(relativeHoehe) / k);
System.out.println("Max. exceptions per fragment: "+ experfrag);
if (relativeHoehe<0) experfrag=experfrag*(-1);
int gesuchteHoehe=experfrag;
int nr=1;
int lastend=0;
if (k>Math.abs(relativeHoehe))
{
k=Math.abs(relativeHoehe);
if (k>1) System.out.println("Only "+k+" fragments needed.");
else System.out.println("Only "+1+" fragment needed.");
}
for (int i=0; i<absoluteHoehe.length; i++)
{
if (nr>=k)
{
String fmt= "%"+(lastend+1)+"s";
System.out.println("Substring "+nr+++":"+
String.format(fmt, "")+
input.substring(lastend));
System.exit(0);
}
if (absoluteHoehe[i]==gesuchteHoehe)
{
String fmt= "%"+(lastend+1)+"s";
System.out.println("Substring "+nr+++":"+
String.format(fmt, "")+
input.substring(lastend, i+1));
lastend=i+1;
gesuchteHoehe=gesuchteHoehe+experfrag;
}
}
*/
}
public class BaumElement
{
public int knicke=0; //seit Wurzel
public int ex=0; //seit letztem Knick
public int ok=0; //seit letztem Knick
public int gex=0; //seit Wurzel
public char zweigtyp='u'; //seit letztem Knick
public StringBuffer weg=null;
BaumElement(int knicke, int ex, int ok, int gex, char zweigtyp, String weg)
{
this.knicke=knicke;
this.ex=ex;
this.ok=ok;
this.gex=gex;
this.zweigtyp=zweigtyp;
this.weg=new StringBuffer(weg);
}
public String toString()
{
return "knicke="+knicke+"; gex="+gex+"; erg="+weg.toString();
}
}
}
Zuletzt geändert von damh am 28. Sep 2006, 21:18, insgesamt 1-mal geändert.
Wer ist online?
Mitglieder in diesem Forum: 0 Mitglieder und 9 Gäste