C# String in einem Char-Array finden

[Krik]

Moin,


ich bin noch sehr neu in der C#-Programmierung. Bitte nicht gleich hauen. ^^


Ich habe dieses Char-Array:

public static const char[] DEFAULT_CHARACTERS_NUMBERS = {'9', '8', '7', '6', '5', '4', '3', '2', '1'};

Und ich habe diesen String:

char[] sequence = "534";

• Ich will jetzt, dass der Inhalt von sequence so sortiert wird, wie es in der Konstante vorgegeben ist, z. B.
  "534" -> "543" wenn {'9', '8', '7', '6', '5', '4', '3', '2', '1'}
  "534" -> "345" wenn {'1', '2', '3', '4', '5', '6', '7', '8', '9'} usw.
• Ich will anschließend herausfinden, ob der Inhalt von sequence eine ununterbrochene Reihe in der Konstante bildet, z. B.
  "543" -> {'9', '8', '7', '6', '5', '4', '3', '2', '1'} -> ununterbrochene Reihe
  "643" -> {'9', '8', '7', '6', '5', '4', '3', '2', '1'} - keine ununterbrochene Reihe
• Sowohl der Inhalt der Konstanten als auch von sequence können verschiedene Zeichen sein. sequence enthält niemals Zeichen, die nicht in der vorgegebene Konstanten drin steht.

Ich habe mich jetzt schon eine ganze Weile damit beschäftigt und bin nun schon in der 6. Verschachtelung angekommen und werfe das jetzt hin. Da muss es doch einen einfachen Weg dafür geben.
Mein Problem ist taucht doch immer wieder bei der Programmierung auf, dafür muss .Net doch irgendetwas bieten.

Weiß da jemand etwas?


Gruß, Laurin

 

[1668mib]

Edit:
Ok, ich hab natürlich quatsch erzählt... ^^
also ich glaube so langsam versteh ich das Problem erst :-)

char[] result = new char[sequence.Length];
            bool sequenceComplete = false;
            bool sequenceInRow = false;
            int currentPos = 0;
            int resultIndex = 0;
            int hitsInRow = 0;
            while (currentPos < DEFAULT_CHARACTERS_NUMBERS.Length)
            {
                char current = DEFAULT_CHARACTERS_NUMBERS[currentPos];
                
                // check if current is member of sequence
                bool hit = false;
                for (int i = 0; i < sequence.Length; i++)
                {
                    if (sequence[i] == current)
                    {
                        hit = true;
                        break;
                    }
                }
                if (hit)
                {
                    // yes, so add it to result
                    result[resultIndex++] = current;
                    hitsInRow++;
                    if (resultIndex == sequence.Length)
                    {
                        // end of sequence reached...
                        sequenceComplete = true;
                        sequenceInRow = (hitsInRow == resultIndex);
                        break;
                    }
                } else
                {
                    hitsInRow = 0;
                }

                currentPos++;
            }
            sequence = result;

            System.Console.WriteLine("Sequenz vollständig enthalten: " + sequenceComplete);
            System.Console.WriteLine(new string(sequence));
            System.Console.WriteLine("In Reihe: " + sequenceInRow);

 

[cx01]

Du musst beide Strings sortieren und dann schauen, ob der erste String den zweiten enthält. Also so:

private bool f(string x, string y)
{
    var sortedX = new String(x.OrderBy(a => a).ToArray());
    var sortedY = new String(y.OrderBy(a => a).ToArray());
    return sortedX.Contains(sortedY);
}

 

[BullshitBingo]

Hi,

mal eine Frage vorweg: warum brauchst du DEFAULT_CHARACTERS_NUMBERS, um zu entscheiden, ob du aufsteigend oder absteigend sortierst? Könntest ja einfach ein boolean-Flag nehmen.

Wie dem auch sei, wenn du es so machen willst, dann kannst du ja leicht prüfen, wie sortiert werden soll. Dazu brauchst du ja nur die ersten beiden Werte von DEFAULT_CHARACTERS_NUMBERS vergleichen. Ist der erste Wert größer als der zweite --> absteigend sortieren! Anderenfalls halt aufsteigend.

So jetzt machst du dich an die Prüfung, ob du eine stetige Reihe hast, indem du einfach über die einzelne Stellen von sequence iterierst. Dabei prüfst du dann, ob die Differenz zwischen sequence - sequence[i+1] > 1 ist. Wenn dem so ist, dann hast du eine unterbrochene Reihe! Vermutlich müsstest du dann auf den Character vorher noch eine toInt-Methode anwenden. Gibt es doch bestimmt unter .NET.

Hoffe, dass ich dein Problem richtig verstanden habe und du mit meinem Vorschlag was anfangen kannst!

 

[1668mib]

@cx01: Der Ansatz ist in meinen Augen zu naiv und leifert auch zu wenig Ergebnisse... geht ja um mehr als nur ob es enthalten ist oder nicht...

@BullshitBingo: Was ist wenn andere Permutationen gelten?

 

[BullshitBingo]

Ja, dann klappt das so natürlich nicht :-) Bin einfach mal davon ausgegangen, dass die Liste absteigend oder aufsteigend sortiert ist...

 

[1668mib]

Was man dir nicht vorwerfen kann, schon alleine deshalb, weil ich selbst nicht weiß, ob es andere geben kann - ein wenig mehr Erklärung hätte nicht geschadet :-)

Auch ich hab in meinem Code ja auch gewisse Annahmen gemacht, wo ich mich nicht sicher bin, ob ich die haben darf...

 

[Krik]

Sry, es ist nicht so ganz rübergekommen:
Die Konstante gibt vor, welche Zeichen in sequence stehen dürfen und wie die Sortierung aussieht.
Sieht sie z. B. so aus: {'A', '1', 'B', '2', usw.},
dann muss sequence = "B21" hinterher so sortiert ausgegeben werden: "1B2".

Welche Zeichen und in welcher Sortierung genau da drin stehen, soll später vom User änderbar sein. Daher nützen mir die Standard-Sortieralgorithmen nichts. Dort wird immer nur nach ASCII-Wert o. ä. sortiert.

So jetzt machst du dich an die Prüfung, ob du eine stetige Reihe hast, indem du einfach über die einzelne Stellen von sequence iterierst. Dabei prüfst du dann, ob die Differenz zwischen sequence - sequence[i+1] > 1 ist. Wenn dem so ist, dann hast du eine unterbrochene Reihe!

Definitiv brauchbarer Vorschlag! Daran habe ich gar nicht gedacht.
Ich hoffe nur, dass das noch performant genug ist, da die Methode das zig (Tausende, vielleicht Millionen) Mal machen muss.


@1668mib
Auch dir danke, dass du gleich einen kompletten Code zusammengeschrieben hast. Ich werde ihn zwar nicht verwenden (selbst ist der Mann ), aber trotzdem danke.



Vielen Dank, Leute! Ich habe offenbar zu kompliziert gedacht.

 

[Metzlor]

Wenn du eh selber einen Code schreiben willst schaue dir einfach

http://de.wikipedia.org/wiki/Quicksort

an. Damit so sortiert wird wie der User festlegt, erstelle eine Funktion

bool Sort(1ter Wert, 2ter Wert)

Der einfach nur true oder falls zurückgibt ob Wert 1 oder 2 größer bzw. kleiner ist.
In Sort kann dann einfach festgelegt werden wie sortiert wird.
Der Rest sollte sich von selbst erklären.

In .NET gibt es schon quicksort, du mußt nur eine bestimmte funktion implementieren dann kann .net
jedes Array automatisch sortieren, funktion ist ähnlich wie s.o.

Funktionsaufruf ist glaube ich Arrayname.sort
es muß nur irgendeine funktion festgelegt werden wie sortiert werden soll.

Ansonsten
http://www.zdnet.de/anwendungsentwi..._arrays_in__net_story-20000201-39149961-1.htm

icomparable muß implementiert werden und compareto function erstellt werden.

 

[1668mib]

Zu meinem Code...
- Die gesamte Sortier-Permutation durchlaufen
- Prüfen, ob das aktuelle Element in der Sequenz vorkommt
- wenn ja:
* Wert dem Ergebnis hinzufügen
* Zähler für ununterbrochene Folgenglieder erhöhen
* Schauen, ob Ergebnislänge der Sequenzlänge entspricht => wenn ja fertig, dann schauen ob ununterbrochene Folge = Sequenzlänge ist weil dann wars ununterbrochen
- wenn nein:
* Zähler für ununterbrochene Folgeglieder zurücksetzen

Man könnte das mit dem Zähler auch anders machen...
und zwar
- wenn das aktuelle Zeichen nicht in der Sequenz ist, aber die Ergebnismenge nicht leer ist, kann die Sequenz nicht ununterbrochen sein
=> anfangs von ununterbrochener Sequenz ausgehen, wenn diese Situation hier eintritt dann ist es keine ununterbrochene Sequenz

Und bei der Stetigkeit hab ich ehrlich gesagt nicht kapiert, was damit gemeint ist oder wie das halt konkret umgesetzt werden soll... die Differenz kann doch auch negativ sein
1B2 => ist B größer oder kleiner als 1? und wie ist es mit der 2 dann?

Und irgendwie glaube ich eher dass hier von (streng) monoton gesprochen wird... aber das setzt sortierte Permutationen voraus, wovon nie die Rede war...

@Metzlor: Sorry aber ich versteh nicht wie (Quick)Sort bei der Menge an Informationen, die man aus den Arrays rausholen möchte, was bringen soll...
Ansonsten gilt auch, was ich vorher schon zu BullshitBingo gesagt hab...

So lange die Permutation sortiert ist geht's vielleicht gut... aber was ist, wenn die Permutation durcheinander ist?

 

[BullshitBingo]

OK, dann habe ich eine weitere Idee, hoffentlich irre ich mich nicht :-) Also, deine Konstante gibt dir also die Ordnung vor und wenn ich das richtig verstehe, dann kannst du in deiner Sequenz auch nur Zeichen haben, die in der Konstante enthalten sind, da ja sonst das Sortieren nicht möglich wäre.

Dann betrachten wir einfach die Indizes der Konstante! Du iterierst also über die Sequenz und vergleichst nicht direkt die Werte innerhalb der Sequenz, also nicht sequenz - sequenz[i+1] > 1, sondern du musst dir für sequenz und sequenz[i+1] die Indizes aus der Konstante ermitteln. Schreibst dir einfach eine Methode für.

Z.B. derart: int GetIndexOfCharInKonstante(char sequenz[seqIndex]).

Jetzt hast du für sequenz und sequenz[i+1] die Position der Zeichen in der Konstante ermittelt. Und nun brauchst du doch einfach nur die Positionen vergleichen! So wie du mich vorhin zitiert hast. Also, wenn der Abstand zwischen der Position von sequenz und der Position von sequenz[i+1] größer 1 ist, dann hast du eine Lücke! Diese Informationen kannst du auch einfach zum Sortieren nutzen!

Es ist schon spät und ich hoffe, dass ich das verständlich beschrieben habe. Könnte jetzt das auch in Pseudocode runterschreiben, aber habe nicht so die Lust zu :-)


Aber ein kleines Beispiel noch:

Konstante: [ 1, 2, 3, a, d, z, 7]
Position in Konstante 0, 1, 2,....

Sequenz: "d12"

p1 = Position von seq in Konstante = 4
p2 = Position von seq[i+1] in Konstante = 0


p1 > p2, also swap!

p1 - p2 > 1 also Lücke!


das müsste es doch sein


Wichtiger Hinweis: das funktioniert natürlich nur, wenn deine Konstante in der richtigen Ordnung steht!

 

[Krik]

Die Konstante gibt die Ordnung vor, das hast du richtig erkannt.


Ich habe nach Studium dieses Threads und Google diese Lösung auserkoren:

Array.Sort(KONSTANTE, sequence);

if (String.Compare(KONSTANTE.ToString(), sequence.ToString()) > 0)
{
    // ...                    
}

Es kann so einfach sein.

Ich habe zwar keine Ahnung, ob das wirklich das ausspuckt, das ich mir denke, aber ich hoffe es.
Es ist zu spät und das Programm ist noch lange nicht so weit, dass ich mit Tests anfangen kann. (Überall nur halbfertiger Code, jetzt noch extra eine Testanwendung proggen und das um diese Uhrzeit? Nee...)

 

[BullshitBingo]

Hast du dir wenigstens meinen Beitrag richtig durchgelesen. Weil wenn du das in Code gießt, dann hast du auf jeden Fall eine Lösung. Wenn du anhand der Positionen sortierst, ist es nämlich latte, was in deiner Ordnung (solange sie sortiert ist) drin steht. Und du kannst nen x-beliebigen Sortier-Algorithmus benutzen!

Aber wenn dein gefundener Code macht was er soll, dann haste ja eine Lösung. Viel Erfolg noch!

 

[1668mib]

nÄhm ne, Array.Sort hilft nicht, wenn man sich mal die Beispielausgaben zum Code anschaut...
http://msdn.microsoft.com/de-de/library/85y6y2d3(v=vs.80).aspx

vor allem wieviel von dem was du im ersten Post als gewünschte Ergebnisse genannt hast, würdest du damit rausbekommen?

@Bullshit-Bingo: Dir ist schon klar, dass es viele swaps geben kann?
Die Sache ist nicht so trivial mit den Swaps... aus dem Grund erachte ich es als einfacher die Sortierreihenfolge zu iterieren und dann zu schauen, ob das aktuelle Element in der Sequenz ist und dann hab ich schon mit Sicherheit die passende Stelle... ich denke aber das rechnet sich von der Komplexität her... schließlich ist die Konstante in aller Regel größer als die Sequenz, die Position eines Zeichens von der Sequenz innerhalb der Konstanten zu ermitteln ist deutlich aufwändiger als zu prüfen, ob das Zeichen in der Sequenz vorkommt...

Edit: Wobei es um so besser ist, über die Konstante zu iterieren, je kürzer die Sequenz im Vergleich zur Konstanten ist (- und umgekehrt gilt natürlich eher über die Sequenz, je länger sie ist)

 

[BullshitBingo]

Nun, es ist mir klar, dass es viele Swaps geben kann. Auf Komplexität habe ich jetzt gar nicht geachtet, sondern wollte nur ein Prinzip zeigen, wie man nach Vorgabe einer x-beliebigen Ordnung sortieren kann. Und wie ich in meinem letzten Post geschrieben habe, kann er ja jeden beliebigen Sortier-Algorithmus auf die Positionen/Schlüssel anwenden. Dann wird das mit der Effizienz auch besser.

 

[1668mib]

Der Sortieralgorithmus stellt doch das Problem dar...
Natürlich ist QuickSort schnell, aber nur wenn ein Vergleich zwischen zwei Einträgen auch schnell ist.
Aber wenn ich für den Vergleich erst mal in ein Array nachschauen muss, an welcher Stelle es steht, dann wird das teuer...

im Mittel muss das Array dann pro Vergleich schätzungsweise bis zu einem Drittel (vermutlich eher nur ein Viertel) durchlaufen werden, wenn man sie nach diesem Schema machen würde

char lowerChar(char char1, char char2, char[] KONSTANTE)
{
  for (int i = 0; i < KONSTANTE.Length; i++) {
    if (KONSTANTE[i] == char1) {
      return char1;
    }
    if (KONSTANTE[i] == char2) {
      return char2;
    }
  }

  throw new Exception(...);
}

Aus dem Grund würde ich auf Sortieralgorithmen hier einfach verzichten...