2 Zeichenketten / Arrays vergleichen

Kolumbus

Hallo Gemeinschaft,

in meinem Programm erzeuge ich zwei Zahlenfolgen deren Inhalt Zahlen von 1 bis 29 sind. Nun möchte ich die Zahlenfolgen auf gleiche Sequenzen vergleichen, und diese Sequenzen dann weiter verwenden.
Die beiden Zahlenfolgen können in 1, 2, oder 3 Stellen übereinstimmen. Die übereinstimmenden Sequenzen können jedoch an unterschiedlichen Positionen stehen.
Nehmen wir als Beispiel die Zahlenfolgen A= 2,3 und B= 2,2,3. Am Ende möchte ich die übereinstimmende Sequenz 2,3 zur verfügung haben. Um die Zahlenfolgen zu untersuchen, habe ich die Möglichkeit, diese in Arrays oder AnsiStrings zu speichern:

// Vereinfachte Darstellung für Zustand nach der Erzeugung:

// Variante 1 - Zahlenfolge in Array (0 bedeutet leer)
int ZaFoA[4]= {2,3,0,0};
int ZaFoB[4]= {2,2,3,0};

// Variante 2 - Zahlenfolge in AnsiString (Zeichen . und # zur einfacheren Untersuchung)
AnsiString ZaFoA= "2.3#";
AnsiString ZaFoB= "2.2.3#";

Ich bekomme es leider nicht hin, ohne 20 Seiten Quelltext zu füllen. Hat nich jemand einen Tip für mich? Wie würdet Ihr das angehen?

Also ich würde
-die beiden Folgen in einen Container legen, die wahlweisen iteratorzugriff erlauben (std::vector, std::string)
- mit einen iterator durch die erste Folge gehen, für jedes Element einen zweiten iterator nehmen, der
+ ein Element voraus,
+ zwei Elemente voraus,
+ drei Elemente voraus,
ist,
- und dann mit diesem Iteratorpaar das im zweiten Container suchen

Braunstein

Das Suchen kann man mit search aus algorithm erledigen

Na ja, so schwer ist das aber auch nicht, lässt sich doch relativ simpel erledigen:

int ZaFoA[4]= {2,3,0,0};
int ZaFoB[4]= {2,2,3,0};
int ZaFoR[4] = {0,0,0,0}; // Ergebnisarray

int test;

for (int x = 0; x < 4; x++)
{
	test = ZaFoA[x];
	if (test == 0) // Nullen im Ausgangsarray ignorieren
		continue;
	for (int y = 0; y < 4; y++)
	{
		if (test == ZaFoB[y])
		{
			for (int z = 0; z < 4; z++)
			{
				if (test == ZaFoR[z])
					break;
				if (ZaFoR[z] == 0)
				{
					ZaFoR[z] = test;
					break;
				}
			}
		}
	}
}

Das Sortieren würde ich vorher in den Ausgangsarrays machen.

Wie willst Du damit Sequenzen finden? Das Teil findet doch nur alle Elemente, die in beiden Reihen vorkommen.

Aus der BCB Hilfe:

equal

#include <algorithm>
 #include <vector>
 #include <functional>
 #include <iostream>
 using namespace std;
 int main()
 {
   int d1[4] = {1,2,3,4};
   int d2[4] = {1,2,4,3};
   //
   // Set up two vectors
   //
   vector<int> v1(d1+0, d1 + 4), v2(d2+0, d2 + 4);
   // Check for equality
   bool b1 = equal(v1.begin(),v1.end(),v2.begin());
   bool b2 = equal(v1.begin(),v1.end(),
                   v2.begin(),equal_to<int>());

   // Both b1 and b2 are false
   cout << (b1 ? "TRUE" : "FALSE")  << " " 
        << (b2 ? "TRUE" : "FALSE") << endl;
   return 0;
 }

witte_ schrieb:

Wie willst Du damit Sequenzen finden? Das Teil findet doch nur alle Elemente, die in beiden Reihen vorkommen.

Du hast recht, das mit den Sequenzen hab ich glatt überlesen...

Kolumbus

Ich werde den fertigen Code heute Nachmittag mal posten. Vielleicht könnt ihr mir dann noch Tips zum verkürzen geben...

Den Codeschnipsel von sir_ment finde ich sehr interessant. Haben doch neulich einige hier im Forum mit mir darüber diskutiert und mir klargemacht, dass ein Vektor kein Array ist und das mit "vector" im Zusammenhang mit VCL / BCB immer std::vector gemeint ist. Nun schau sich einer das Beispiel aus der BCB-Hilfe von sir_ment an: Der werden die eindimmensionalen int-Arrays doch glatt "vector" genannt

akari

Hallo

Kolumbus schrieb:

Nun schau sich einer das Beispiel aus der BCB-Hilfe von sir_ment an: Der werden die eindimmensionalen int-Arrays doch glatt "vector" genannt

Wo werden da Arrays als Vektoren bezeichnet?

Im Code gibt es 2 Vektoren die auch so bezeichnet werden

// Set up two vectors
vector<int> v1..., v2...;

bis bald
akari

Kolumbus

Ich dachte der Kommentar bezieht sich auf die Initializierung darüber.. Jetzt bin ich wach! Ich nehme Alles zurück und behaupte hiermit das Gegenteil!

Kolumbus

So, habe fertig!

Ich habe eine angenehm übersichtliche Variante gefunden. Ich arbeite mit int-Arrays (2x2-dimensional, 2x1-dimensional). String-Arrays waren für Zahlenreihen-Vergleiche zu unhandlich.
Das Ganze dient übrigens der Berechnung des größten gemeinsamen Teiler (ggT) zweier Zahlen zwischen 1 und 60. Dazu werden durch Primfaktorzerlegung 2 Zahlenreihen gebildet, aus denen dann gleiche Sequenzen gefunden werden müssen.
Durch das Verfahren zur Ermittlung des ggT kommt erschwerend zu meinem Eingangspost hinzu, dass gleiche Sequenzen auch aus Teilsequenzen der Zahlenreihen bestehen können. Erleichternd wirkt jedoch, dass die Zahlenreihen hier nur aus den 10 ersten Primzahlen bestehen können und maximal 5 Elemente besitzen:

Beispiel:
Zahl 1: 10
Zahl 2: 30 
Zahlenreihe 1: 2, 5
Zahlenreihe 2: 2, 3, 5
gleiche Sequenz: 2, 5

Nun gehe ich wie folgt vor:
1 Anlegen eines const int Array PrimZ[10] mit den Primzahlen
2 Ermittlung der Zahlenreihen durch Primfaktorzerlegung und Speichern der Werte in int Array PriFakt[2][5]
3 Vergleichen der einzelnen Elemente von PriFakt[0][] und PriFakt[1][] mit jedem Element von PrimZ[10] und Speichern der Häufigkeit von Übereinstimmungen in FaktCount[2][10]
4 Vergleichen der Häufigkeiten in FaktCount[0][i] und FaktCount[1][i] (wenn beide nicht 0) und kleineres FaktCount[][i] * PrimZ[i] zum Ergebniswert multiplizieren

Beispiel:
// Zahlen werden an Funktion ggT übergeben:
int ZahlA= 10, ZahlB= 30;
// Deklarationen und Initialisierungen:
int ggT=1;
int FaktCount[2][10]= {{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0}};
int PriFakt[2][5]= {{0,0,0,0,0},{0,0,0,0,0}};
// Schritt 1:
const int PrimZ[10]= {2,3,5,7,11,13,17,19,23,29};
// Schritt 2 - Ergebnis:
PriFakt[2][5]= {{2,5,0,0,0},{2,3,5,0,0}}
// Schritt 3 - Ergebnis:
FaktCount[2][10]= {{1,0,1,0,0,0,0,0,0,0},{1,1,1,0,0,0,0,0,0,0}}
// Schritt 4 - Ergebnis:
ggT= 1*((1*2)*(1*5))= 10;

Ich bin stolz auf mich (uhh was stinkt hier so nach Eigenlob?)

Falls sich jemand für den Code oder die Problematik interessiert, stehe ich zur Verfügung.