Kombinatorik? Problemstellung

[smash]

Hallo,

ich habe einen String in den ich systematisch Leerzeichen einfügen möchte. Das soll so automatisiert werden, dass ich aus dem Originalstring jede mögliche Kombination von eingefügten Leerzeichen erhalte. Also ich nehme immer wieder den Originalstring füge eine Kombination von Leerzeichen ein und wieder von vorn...

Beispiel:

"123"

"1 23"

"12 3"

"1 2 3"

Ich denke man könnte das so lösen:

Man durchläuft die Zahlen von 0 bis zur Anzahl der möglichen Kombinationen von eingefügten Leerzeichen. Innerhalb der Schleife wird die akutelle Zahl in eine binäre Zahl umgerechnet. Jede Stelle der binären Zahl steht für die Lücke zwischen zwei Zeichen im Originalstring. Bei einer 1 für ein Leerzeichen eingefügt, bei einer 0 keines. Das einfügen in den String geschiet von hinten. So ist es egal, dass durch das Einfügen der Leerzeichen der nachfolgende Teilstring verschoben wird.

Hier mal in Java:

	private void setSpaces(){

		for(long i = 0; i < anzahlKombinationen; i++){

			StringBuffer original = new StringBuffer("0123456789");

			boolean[] binary = getAsBinaryArray(i);

			for(int b = binary.length; b > 0; b--){

				if(binary[b]){

					original.insert(b, " ");

				}

			}

		}

	}

Jetzt kommt aber eine zusätzliche Anforderung: In dem String dürfen maximal 4 Zeichen aufeinanderfolgen ohne das ein Leerzeichen dazwischen liegt. Anders ausgedrückt: Spätestens nach vier Zeichen muss ein Leerzeichen erfolgen. Ich habe keine Ahnung ob mein Ansatz dazu noch brauchbar ist oder ob ein ganz neuer her muss. Außerdem wäre es hilfreich zu wissen, wie viele Kombinationen mit diesen Anforderungen möglich sind.

Ich hoffe ihr könnt mich mit Ideen unterstützen.

Vielen Dank im Voraus.

Bearbeitet 5. Januar 2009 von smash

[flashpixx]

Ist die Frage jetzt, dass Du prüfen musst, ob der String eine korrekte Anzahl an Leerzeichen enthalten soll? Dann nimm reguläre Ausdrücke.

Wenn Du jetzt einen String mit Leerzeichen gefüllt werden soll, dann würde ich das als nea erst einmal beschreiben

Phil

[smash]

Danke für deine Antwort. Hab mich wohl nicht klar genug ausgedrückt. Ich versuchs nochmal:

Ich suche einen Algorithmus, der die Leerzeichen an den richten Stellen im String einfügt. Beispielstring: "0123". Ein Leerzeichen könnte zwischen 0 und 1, zwischen 1 und 2 und zwischen 2 und 3 eingefügt werden. Vor der 0 und nach der 3 werden keine Leerzeichen benötigt.

Anzahl der Zeichen im String = 4

Anzahl möglicher Leerzeichen = 4-1 = 3

An jeder dieser Stellen kann nun ein Leerzeichen eingefügt werden, muss aber nicht. Ich möchte alle möglichen Kombinationen / Variationen des Strings mit eingefügten Leerzeichen erhalten. An dieser Stelle fällt es mir schwer mich klar auszudrücken. Für den Beispielstring würde ich folgende Strings als Ergebnis erwarten:

"0 123"

"01 23"

"012 3"

"0 1 23"

"01 2 3"

"0 1 2 3"

Es gibt also mehrere Stellen an denen ein Leerzeichen eingefügt werden könnte. Ich möchte nun den String erhalten, mit allen möglichen Kombinationen von eingefügten Leezeichen.

Mein Lösungsansatz:

Vergleich zum Byte: Ein Byte ist eine 8stellige binäre Zahl. An jeder Stelle steht ein entweder eine Eins oder eine Null. Das ist die parallele zu "Leerzeichen einfügen" oder "Leerzeichen nicht einfügen". Wenn ich alle Kombinationen von Nullen und Einsen in einem Byte erhalten möchte, könnte ich dezimal von 0 bis 255 zählen. Die aktuelle Zahl rechne ich einfach nach binär um und erhalte eine einmalige Kombination von Nullen und Einsen. Beim Zählen von 0 bis 255 und dem Umrechnen ins binäre erhalte ich also alle Kombinationen von Nullen und Einsen die in dem Byte möglich sind.

Übertragen auf die Leerzeichen heißt das:

- Die Anzahl der möglichen Kombinationen errechnen.

- Von 0 bis zur Anzahl der möglichen Kombinationen zählen.

- Die aktuelle Zahl nach binär umrechnen.

- An jeder Stelle der Binärzahl mit einer Eins muss an der entsprechenden Stelle im String ein Leerzeichen eigefügt werden.

Ich habs noch nicht getestet, aber genau das soll der Java Code, den ich gepostet habe, machen.

Jetzt zur zusätzlichen Anforderung:

Es muss sichergestellt sein, das nach spätestens vier Zeichen im String ein Leerzeichen kommt. Ich weiß nicht genau ob das mit meinem Ansatz Lösbar ist oder ob ein ganz neuer her muss.

Vielen Dank nochmal. Bitte fragt noch etwas genauer nach, wenn noch etwas unklar sein sollte.

[flashpixx]

Du gehst von einem String aus der ASCII codiert ist, was ist mit Unicode (Java arbeitet durchaus mit Unicode), dann hat ein Zeichen 2 Byte (16 Bit).

Ich verstehe wirklich nicht, warum Du binär arbeiten willst !? Soll das "schneller" sein?

Du musst sicher stellen, dass nach max. 4 Zeichen ein Leerzeichen kommt, also nimm eine RegExpr.

Wenn Du selbst alle Kombinationen erzeugen musst, dann kann ich auch durch den String mehrfach laufen, um alle Leerzeichen Kombinationen zu erzeugen. Schneller wird das nicht wirklich, wenn Du alle brauchst, vor allem wenn es lange Strings sind.

Phil

[Klotzkopp]

Du gehst von einem String aus der ASCII codiert ist, was ist mit Unicode (Java arbeitet durchaus mit Unicode), dann hat ein Zeichen 2 Byte (16 Bit).

Ich verstehe wirklich nicht, warum Du binär arbeiten willst !? Soll das "schneller" sein?

Das Byte dient doch nur dazu, die Positionen der Leerzeichen zu codieren. Jedes Bit steht für ein mögliches Leerzeichen.

Du musst sicher stellen, dass nach max. 4 Zeichen ein Leerzeichen kommt, also nimm eine RegExpr.

Soweit ich das verstanden habe, geht es auch nicht darum, zu prüfen, ob eine Kombination diese Einschränkung erfüllt, sondern ob das mit diesem Ansatz (der Codierung der Leerzeichenpositionen) leicht zu prüfen ist, oder die Anzahl der erlaubten Kombinationen einfach zu ermitteln ist (also einfacher als durch bloßes Durchprüfen).

[smash]

Danke für eure Antworten. Wie ihr seht ist es hier wirklich nicht einfach sich verständlich auszudrücken.

Der echte String um den es geht hat über 4000 Zeichen. Die Anzahl der gesuchten Kombinationen ist also wirklich groß (größer als 2^4000).

Das Byte dient doch nur dazu, die Positionen der Leerzeichen zu codieren. Jedes Bit steht für ein mögliches Leerzeichen.

Soweit ich das verstanden habe, geht es auch nicht darum, zu prüfen, ob eine Kombination diese Einschränkung erfüllt, sondern ob das mit diesem Ansatz (der Codierung der Leerzeichenpositionen) leicht zu prüfen ist, oder die Anzahl der erlaubten Kombinationen einfach zu ermitteln ist (also einfacher als durch bloßes Durchprüfen).

Ich denke da hast du mich fast richtig verstanden. Allerdings geht es mir eher um eine automatische Generierung der Leerzeichen Kombinationen (man denke an die Anzahl...) als um eine Überprüfung. Wenn man so will "Bruteforce Leerzeichensetzung".

Mir geht es vor allem darum, dass ich keine Kombination übersehe. Schön wäre es natürlich auch wenn ich keine doppelten Ergebnisse erzeuge. Die Ergebnisse möchte ich später Filtern.

[Klotzkopp]

Mir geht es vor allem darum, dass ich keine Kombination übersehe. Schön wäre es natürlich auch wenn ich keine doppelten Ergebnisse erzeuge. Die Ergebnisse möchte ich später Filtern.

Bei 4000 Zeichen werden das sehr sehr viele Kombinationen. Ich bezweifle, dass du diese Datenmenge auf irgendeinem derzeit verfügbaren Datenträger speichern kannst, oder auch nur in absehbarer Zeit damit fertig wirst, alle zu ermitteln.

[flashpixx]

Der echte String um den es geht hat über 4000 Zeichen. Die Anzahl der gesuchten Kombinationen ist also wirklich groß (größer als 2^4000). [...]

Mir geht es vor allem darum, dass ich keine Kombination übersehe. Schön wäre es natürlich auch wenn ich keine doppelten Ergebnisse erzeuge. Die Ergebnisse möchte ich später Filtern.

Denn so wie ich das sehe ist dein Problem NP-vollständig, somit ist es zweifelsfrei nicht sinnvoll alle Kombinationen zu berechnen.

Ich würde hier zu einer Approximation raten

Phil

[smash]

Danke für eure Antworten.

Denn so wie ich das sehe ist dein Problem NP-vollständig, somit ist es zweifelsfrei nicht sinnvoll alle Kombinationen zu berechnen.

Gebe dir recht. Wenn ich dich richtig verstehe hätte ich nur dafür sorgen müssen, das ich keine Kombination übersehe.

Bei 4000 Zeichen werden das sehr sehr viele Kombinationen. Ich bezweifle, dass du diese Datenmenge auf irgendeinem derzeit verfügbaren Datenträger speichern kannst, oder auch nur in absehbarer Zeit damit fertig wirst, alle zu ermitteln.

Habe grad über dasselbe nachgedacht und bin zum selben Schluss gekommen.

Damit hat sich meine Bruteforce Strategie wohl erledigt. Schade. Ich muss mir wohl was komplett neues überlegen.

Trotzdem nochmals vielen Dank.

[flashpixx]

Schildere doch einfach mal die Problematik evtl kann man da etwas weiter helfen

HTH Phil

[AndiE]

Hallo,

ich habe einen anderen Ansatz:(Pascalsches Dreieck)

Gegeben sie ein String der Länge 3. Dann gibt es (3 über 0)=1 String ohne Leerzeichen. (3 über 1) = 3 Strings mit 1 Leeerzeichen, (3 über 2) Strings mit 2 Leerzeichen und (3 über 3) Strings mit 3 Leerzeichen.

Die Summe der Zahlen ist 2 hoch 3 gleich 8.

So könntest du die Teilanzahlez berechnen.

Ich denke, die Aufgabe (4000 über 1000) wird jeden Rechner sprengen.

LG

Andre'