Hallo an alle.


Folgende Ausgangssituation:

Ich habe ca. 100 Strings mit einer länge von 50 - 80 Zeichen.
Enthalten sind 10-25 mal die "1", die restlichen Zeichen sind "0". (String als Datentyp soll hier keine Rolle spielen, kann auch Integer sein).

Zum Muster:
Vorgegeben ist die Anzahl der "1" aus denen das Muster besteht (Zwei-Acht);
Mehr als 1 mal pro String ist egal, entscheidend ist das häufigste Muster, dass in allen Strings EIN mal vorkommt (wie bereits gesagt, falls das Muster mehr als ein mal pro String vorkommt soll es ignoriert werden)

Häufigstes Vorkommen:

String 1: A000A
String 2: A000A
String 3: AA000
String 4: 00A0A
String 5: 0000A

Mögliche Ergebnisse: 2 mal AxxxA (String 1,2)
3 mal AA (String 1,2,3)
1 mal AxA (String 4)
1 mal AxxA (String 4)
String 5 ist kein gültiges Ergebnis, da A nur 1 mal vorkommt (mind.2 mal ist ein MUSS)
--> Das häufigste Muster = AA
--> Der Rest ist nicht von Interesse

Jeder String ist als Schleife zu betrachten.
Heißt: die letzten Ziffern eines Strings können auch der Beginn eines Musters sein.
--> z.B.: letzte Ziffer = erste stelle des Musters, dann geht es wieder (im gleichen String) von vorne los!
(die letzte Ziffer ist nur ein Beispiel. Soll nur heißen, dass der String eine in sich geschlossene Endlosschleife darstellt und jeder Index der Start und Endindex sein kann).

Ergebnis soll so aussehen: "10101" kommt in 85 von 100 Strings vor.

Beispiel: 2 mal die "1"

100000000000 -
101000000000 Fundstelle 1
100000000010 Fundstelle 2
100001000010 Fundstelle 3
010000000001 Fundstelle 4
100100000000 -

Lösung: 1x1 kommt in 4 von 6 Strings vor
(x kann sowohl für 1 als auch 0 stehen!)

Beispiel 2:

1001001 -->*
1000001
1111111 -->*

Lösung: 1xxxxx1 kommt in 3 von 5 Strings vor.


* --> entscheidend ist nicht was zwischen zwei "1" liegt, sondern der Abstand zwischen den zwei "1".

Meine Idee bis jetzt:
jeden String mit mehr als 2-8 (je nach dem was gesucht wird) "1" zu extrahieren und in einem Array oder einer List zu speichern.
Beim zweiten zu durchsuchenden String dann eine Abfrage mit einzubauen, die folgendes macht:
-ist der String vorhanden wird der dazugehörige Counter hochgezählt
-ist der String noch nicht enthalten, ins Array mit einfügen


Das ganze soll halt auch mit acht "1" möglich sein und ich habe nicht annähernd eine Idee wie ich dieses Problem lösen soll.
Ich hoffe ich konnte das Problem einigermaßen erklären.

Bin für alle Vorschläge offen. Vielen Dank vorab an alle Helfenden.

wie unten bereits erwähnt läuft dieses Thema auch noch hier:
board.gulli.com/thre...llen-strings-finden/

und hier:

www.mycsharp.de/wbb2...d.php?threadid=67929

Gruß Buddha23

P.s.: Danke für die Hinweise und Sorry für die Anfängerfehler
Ich weiß. Die Erklärung ist nicht die beste.
Falls Fragen auftauchen, bitte ich euch diese zu posten damit ich die Erklärung ändern/ergänzen kann.

Bitte verlinke Cross-Posts in anderen Foren. Es wäre doch wirklich schade, wenn sich jemand einen schönen Algorithmus ausdenkt und dann feststellen muss, dass auf einer anderen Seite schon längst der gleiche oder ein noch besserer vorgeschlagen wurde.

Zum Problem: Aus deiner Beschreibung werde ich noch nicht ganz schlau, besonders von dem "Häufigsten Vorkommen" sehe ich nichts in den Beispielen.

Ich denke ich habe das schon verstanden, wenn ich das richtig verstehe, dann sollte das mit einer List<String> so umsetzbar sein, dazu müsstest du dann noch die Anzahlen speichern.

Für spezielle Fälle könnte man vielleicht auch schnellere Lösungen basteln, aber diese Lösung und die von dir beschriebene Vorgehensweise (ab "Meine Idee bis jetzt:") sind schon passend.

N Abend noch mal.
Es würde tatsächlich so funktionieren wie ich mir dachte.
Es gibt aber ein weiteres Problem. Die Laufzeit.
Ich glaube nicht, dass ich genug Zeit habe es mehr als einmal in meinem Leben zu testen

Dann zeig doch mal deinen Quelltext, das lässt sich garantiert optimieren, denn bei den von dir genannten Anzahlen an Strings sollte das eigentlich sofort durch sein. Oder ich habe noch nicht genau verstanden was du genau machen willst.

Ein ähnliches Problem findest du hier, da habe ich in Delphi eine Lösung gepostet:
www.delphi-forum.de/viewtopic.php?t=90351

Auf ein Neues

Der Beispielstring: (64 bit)
1001 1111 1011 1101 0011 0010 0000 0010 0100 0000 1000 0010 1000 0101 0010 01010

Gesucht wird nach jedem Muster das aus 2-8 "1" beseht.
Ob nach 2,3,4,5,6,7 oder 8 "1" gesucht wird, lege ich vorher fest.

Beispiel mit 2 mal "1":

1001 oder 1111 oder 1011 oder 1101 oder 0011 oder 00100000001 wären jeweils eine Lösung für das Muster 1xx1
(das x steht für jeweils genau eine Ziffer. es ist egal was an diesen stellen steht)

-> sind nur ein paar Möglichkeiten die ich für jeden einzelnen String suchen muss.

Bin spätestens am Montag wieder an meinem eigenen Rechner, dann poste ich auch meinen Code.

Ich hoffe es ist verständlicher geworden, warum ich bedenken wegen der Laufzeit habe.

buddha23 hat folgendes geschrieben :

Gesucht wird nach jedem Muster das aus 2-8 "1" beseht. Ob nach 2,3,4,5,6,7 oder 8 "1" gesucht wird, lege ich vorher fest.

Das heißt du gehst bei 2 dann diese Muster durch?
1001, 1010, 1100, 0101, 0110, 0011?

Wie lang sollen denn die Muster sein? Da gäbe es natürlich sehr viele Muster, wenn es mehr Zeichen sind. Aber da wäre es wohl eher sinnvoll jeweils die Länge des Musters im String zu betrachten und zu schauen welches der Muster das ist. Und bei 0 und 1 nur könnte man bitweise vielleicht etwas machen.

Aber eigentlich ist eher die Frage ob das wirklich die richtige Herangehensweise ist. Ich meine, welchen Nutzen hat das denn? Gibt es da nicht vielleicht eine bessere Lösung?

So langsam kommen wir dem Problem näher.
Die Muster die du genannt hast sind für 2 nur eine Teillösung, da
1000 1, 1000 0001 aber auch 1000 1111 0001 jeweils Lösungen für 2 sind.

Ich bin auch der Meinung, dass ich falsch an das Problem herangehe.
Mir ist aber auch ganz ehrlich nichts besseres eingefallen.

Bin auch schon den ganzen Tag am googlen, aber anscheinend nicht nach dem richtigen

Ach ok, also es kommt nur darauf an, dass die 1 am Anfang und am Ende steht und wie lang das Muster ist und was dazwischen steht ist egal?

Wie sehen denn dann die Muster mit mehr Einsen aus?
4 Einsen wäre dann eine 1 am Anfang, eine am Ende und 2 irgendwo dazwischen?

Das hieße doch dann, dass man praktisch nur schauen müsste, wo genug Einsen vorkommen. Dann bei der Suche nach 5 Einsen und 8 in dem String müsste man aus der Stochastik bzw. genauer der Kombinatorik (oh ja, das hatte ich im Informatik-Studium...) die Möglichkeiten für 5 aus 8 durchgehen. D.h. man muss gar nicht nach einem bestimmten Muster suchen, sondern kann aus den vorhandenen Einsen die vorkommenden Muster auflisten.

richtig
Für 4 mal "1" muss Anfang und am Ende die 1 stehen.
und dazwischen 2 ODER MEHR "1".

10011001 oder
01001101 oder
11111111
wären alles Lösungen für 4.
Aber leider beim besten willen nicht alle

Wie gesagt was dazwischen liegt ist egal, so lange in der Summe mehr als 4 mal "1" vorkommt.

Hab auch bereits über Stochastik/Kombinatorik nachgedacht.
Bräuchte aber wie gesagt ein paar Denkanstöße, da das nicht gerade meine Gebiete sind

Ok, also wenn ich 3 Einsen suche und diese Strings habe:Dann wäre die Lösung 10101, weil es als einziges Muster mit drei Einsen in allen drei Strings vorkommt?

Dann hätte ich da vielleicht eine Idee, so wie ich eben schon meinte.

Und als letztes: Geht es nur um Nullen und Einsen oder allgemein um Zeichen? Weil bei nur 0 und 1 könnte das Speichern der Vorkommnisse relativ einfach werden (bitweise).

Hey,
wenn ich deine Fragestellung richtig verstanden hab sind in
0000A
doch 2 A's drin, oder?
A0000A macht 2 A's

Ich schließ mich dem Budda an: wenn du das so umsetzen willst, dann fliegt dir die Laufzeit durch eine kombinatorische Explosion um die Ohren...

Guten Morgen,
dann werde ich mich mal ein bisschen mit Kombinatorik beschäftigen.
Es können beliebige Zeichen benutzt werden, aber nur 2 davon.
Ob 1 oder 0, A oder B, X oder Y, Gelb oder Grün ist mir egal.
Denk mit 1 und 0 sollte es noch am einfachsten sein

@Thorsten83:
Was du meinst ist nicht richtig.

Die Lösungen wären hier:

0000A und A0000 oder 0A000 oder 00A00 oder 000A0
(aber wie bereits mehrfach erwähnt spielt ein A keine Rolle, sonder 2-8 "A")

Hey,

dass Muster mit nur einer 1 nicht interessieren war schon klar, es ging um die Frage, ob Einsen aus dem String mehrfach verwendet werden dürfen...

Was die Muster mit mehreren Einsen angeht...

Im String 1111 taucht ja sowohl das Muster 1xx1 also auch 1111 auf, die sollen aber separat gezählt werden?

Richtig.
Ich habe ja gesagt, dass der Abstand entscheidend ist, nicht was dazwischen liegt.
Wobei die Häufigkeit des Musters innerhalb eines Strings egal ist.

Der Abstand? Ich dachte 1101 und 1011 sollten separat gezählt werden, oder müssen nur 101 und 1001 z.B. separat gezählt werden, weil der Abstand der äußeren Zeichen anders ist?

Jedenfalls hab ich da eine Idee, ich komm nur gerade nicht so richtig dazu, weil ich was anderes zu tun habe und nur nebenbei immer kurz hier was schreiben kann höchstens.

Ich muss ehrlich zugeben das ich langsam selber den Durchblick/Überblick verliere

1101 kann folgende Muster enthalten: 1xx1, 1x11, 111x, 11, 1x1, 111
1011 kann folgende Muster enthalten: 1xx1, 1x11, 111x, 11, 1x1, 111
Die Strings müssten erst mal seperat betrachtet werden.
Dann extrahiert ich alle möglichen Muster und stelle ganz verduzt fest das es sich im Prinzip um die selben Muster in beiden Strings handelt

buddha23 hat folgendes geschrieben :

Ich muss ehrlich zugeben das ich langsam selber den Durchblick/Überblick verliere

Das merke ich:

buddha23 hat folgendes geschrieben :

1101 kann folgende Muster enthalten: 1xx1, 1x11, 111x, 11, 1x1, 111 1011 kann folgende Muster enthalten: 1xx1, 1x11, 111x, 11, 1x1, 111

Aber ich habs also schon richtig verstanden gehabt, ich muss nachher mal schauen, wie schnell das dann als Programm wird.

// EDIT:
Trotzdem ist das in der Form doch kein praktisches Problem, vermutlich gäbe es für ein konkretes Problem auch eine bessere Lösung...

Nein das war schon richtig was ich vorher gepostet habe.
Man muss den String als eine Art Schleife betrachten.

Die letzte Ziffer kann der Beginn des (selben) Strings sein.
Aber auch die vorletzte Ziffer kann der Beginn sein.
Wie erwähnt eine Schleife

Das was Du machst ist im Prinzip eine huffman codierung. Google doch einfach mal danach, es finden sich sehr schone Lösungsansätze dazu. Daraus kann man - wenn man will - ein eigenes Komprimierungsprogramm erstellen.