Array vergleichen

MungoPower · Hält's aus hier Beiträge: 10

Moin moin.
Ich weiß, dass es bereits einige Beiträge zu diesem Thema gibt, aber so ganz verstehen tu ich es noch nicht -.-

- Ich habe einen array[1..12] of string mit jeweils einem Buchstaben, z.B. array[1] := 'J';
- In einem weiteren Feld kann der Benutzer ein Wort eingeben, dass kürzer ist, als 12 Buchstaben
- Ich möchte nun wissen, ob dieses Wort mit den Buchstaben aus dem ersten Array gelegt wurde

Mein Ansatz:
- Zweites Wort in einem Array verwandeln
- arrays vergleichen, wenn also z.B. array1[1] = array2[4] ist, dann macht er weiter, wenn nicht, nicht
Wie gehtn das möglichst schonend? Ich könnte das nur mit 12 if-anweisungen in ner for schleifen...

Moderiert von Narses: 2. Frage entfernt.

Viele Grüße
MungoPower
Moderiert von Narses: Titel geändert.

platzwart · Verfasst: Do 01.10.09 19:35

MungoPower hat folgendes geschrieben :

Moin moin.
2tes Problem:
Ich möchte den array1 zufällig sortieren, nicht alphabetisch oder so wie immer in den tutorials...

Wenn ich mich nicht täusche, dann ist "zufälliges Sortieren" = nicht sortiert?!?

Zum ersten Teil: Müssen die 12 Buchstaben in einem Array sein, oder darf man die auch als Zeichenkette aneinander hängen?

_________________
Wissenschaft schafft Wissenschaft, denn Wissenschaft ist Wissenschaft, die mit Wissen und Schaffen Wissen schafft. (myself)

Kha · Verfasst: Do 01.10.09 20:35

Du willst also überprüfen, ob ein Array B eine Permutation eines anderen Arrays A ist. Am einfachsten, allerdings nur in O(n²), funktioniert das so:

Du brauchst ein drittes, gleichgroßes Boolean-Array C, vorbelegt mit False
Für jedes Element aus A: Suche ein Element aus B, das damit übereinstimmt und dessen zugehöriger (= gleicher Index) Wert in C False ist. Falls gefunden, setze den Wert in C auf True, ansonsten bist du schon fertig.
Genau wenn C nur True beinhaltet, ist es eine Permutation

_________________
>λ=

MungoPower · Hält's aus hier Beiträge: 10

Zitat:

Wenn ich mich nicht täusche, dann ist "zufälliges Sortieren" = nicht sortiert?!?

Ähm ja, ich meine eigentlich die Buchstaben einfach willkürlich vertauschen, so dass da statt ANGSBUDE eben BUNDESTAG steht.

Zu 1.
Es ist ja keine richtige Permutation, weil das 2te Wort kürzer ist als das erste. Ich will also z.B. prüfen, ob "TAG" in "BUNDESTAG" enthalten ist.

Kha · Verfasst: Do 01.10.09 22:02

MungoPower hat folgendes geschrieben :

Es ist ja keine richtige Permutation, weil das 2te Wort kürzer ist als das erste.

Achso, quasi die Permutation einer Kombination. Wenn du das kleinere Array als A nimmst, C auf die Größe von B setzt und den letzten Schritt weg lässt, sollte mein Algorithmus trotzdem passen.

_________________
>λ=

MungoPower · Hält's aus hier Beiträge: 10

Danke für eure Mühen, ich hab eindlich eine Lösung gefunden..
Ich poste gleich, wie ichs gemeint hab, mom

Jann1k · Verfasst: Do 01.10.09 23:32

Andere Idee:

Ich sortiere beide Arrays (geht denke ich mit maximal O(n log n)) und vergleiche dann beide bis zum Ende vom kürzeren, sind die beiden Arrays bis zum Abbruch gleich ist die Eingabe okay.

Kha · Verfasst: Fr 02.10.09 00:18

[B;C] und [A;B;C] sind sortiert, sie haben trotzdem nicht den gleichen Anfang

.

Edit: Wenn du das allerdings weiter denkst, kommst du zu dem linearen Algorithmus, den ich im Kopf und auch schonmal implementiert habe: Beide Arrays werden jeweils nach gleichen Elementen gruppiert und die Größen der Gruppen festgehalten. Aus [A;B;B;C;B;A] würde beispielsweise [(A,2);(B,3);(C,1)]. Dann muss nur noch überprüft werden, ob die Größe jeder Gruppe im kleineren Array A kleiner als die der entsprechenden Gruppe in B ist. Sortieren ist nicht nötig, deswegen geht auch O(n).

_________________
>λ=

MungoPower · Hält's aus hier Beiträge: 10

Also, hab einfach so gemacht:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

procedure TForm1.BtTauschenClick(Sender: TObject);
var zufallszahl1, zufallszahl2, d : Integer;
    hilfsstring, wort, wort2 : string;
begin
for d := 1 to 4 do
 begin
 zufallszahl1 := (random(Length(EdAnzeige.Text))+1); //EdAnzeige.Text soll umsortiert werden
 zufallszahl2 := (random(Length(EdAnzeige.Text))+1);
 wort := EdAnzeige.Text;
 wort2 := EdAnzeige.Text;
 hilfsstring := EdAnzeige.Text[zufallszahl1];
 wort[zufallszahl1] := wort[zufallszahl2];
 wort[zufallszahl2] := wort2[zufallszahl1];
 EdAnzeige.Text := wort;
 end;
end;

Das ist zwar ein bissel unschön, aber ich fands einfach

Lg,
MungoPower

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme