Zwei Arrays auf Permutation prüfen

[forumnewbie]

Hi,

nächste Aufgabe: zwei Arrays, die aus int-Werten bestehen, sollen auf Permutation überprüft werden. Arrays dürfen nicht verändert werden und die Funktion sollte effizient sein.

Eine mögliche Lösung habe ich, die aber nicht effizient ist. Ich kopiere diese Arrays in zwei andere, sortiere sie mit einem Algorithmus und überprüfe, ob die Arrays identisch sind.
Das Problem ist, dass sich die Zahlen anscheinend wiederholen können, also z.B. array1[] = {1,2,3,4,4,1} und array2[] = {2,1,3,4,1,4}. Würden sich die Zahlen nicht wiederholen, dann könnte ich mit zwei for-Schleifen eine Matrix aufbauen und dann jedes Element aus dem ersten Array jedes mal mit allen Elementen aus dem zweiten Array überprüfen. Da sich aber die Zahlen wiederholen, muss ich mir wahrscheinlich irgendwie die Stellen in dem zweiten Array auch merken und diese bei weiteren Durchläufen nicht berücksichtigen. Das ist aber wahrscheinlich keine gute Lösung und ich weiß im Moment auch nicht, wie ich das effizient realisieren kann.
Hat jemand zufällig eine Idee bzw. einen Vorschlag für eine effiziente Lösung?

Danke!

[Xin]

Sind die Arrays unterschiedlich groß => keine Permutation.

Leg ein Array Occupied an, dass die gleiche Größe hat und initialisiere es mit Nullen.

Iteriere über Array1.
. Suche das aktuelle Element in Array2 und merke Dir den Index.
. . Occupied[Index] == 0, dann auf 1 setzen.
. . Occupied[Index] == 1, dann weitersuchen.
. Wenn Du keinen Index gefunden hast, der frei ist => keine Permutation.

Für alle Elemente einen Index gefunden? => Permutation.

[cloidnerux]

Wenn die beiden Arrays nur aus Zahlen bestehen, könnte man einmal die Summe aller Elemente und einmal das Produkt aller Elemente bilden und auf Gleichheit prüfen.
Da sich Additive abweichungen (Eine Zahl +1, eine -1) sich in der Multiplikation bemerkbar machen und Multiplikative Abweichungen(z.B einmal ein Element *1/2, eins *2) in der Summe, sollte dies eine geeignete Antwort liefern, ob zwei Mengen an Zahlen eine Permutation voneinander darstellen.
Es ist aber nicht bewiesen, dass dies für alle möglichen Mengen an Zahlen gilt, auch muss man beachten dass bei der Multiplikation vieler Zahlen zu einem Überlauf des int führen kann, hier muss man evt mit Restklassen arbeiten.

[forumnewbie]

Danke! Ich habe das mit einem Hilfsarray occupied[] gemacht und es klappt.
Ich denke, dass unser Prof. das genau so in der Prüfung sehen will.

Aber die andere Idee hat mir auch sehr gefallen. Sollte die Aufgabe zu schwer werden oder ich nicht mehr genug Zeit haben, dann werde ich eine Funktion schreiben, die einfach eine Summe und ein Produkt aus Elementen jedes Arrays bildet und überprüft, ob beide Summen UND beide Produkte gleich sind. Die Variablen summe und produkt werde ich als double definieren.
Und wenn die Arrays unterschiedliche Länge haben, dann wird die Funktion gleich ohne Überprüfung mit einem Rückgabewert beendet.
Ich hoffe, dass er diesen Lösungsvorschlag auch mit ein paar Punkten bewertet, bzw. auch andere Lösungsvorschläge akzeptiert .

[cloidnerux]

Aber die andere Idee hat mir auch sehr gefallen. Sollte die Aufgabe zu schwer werden oder ich nicht mehr genug Zeit haben, dann werde ich eine Funktion schreiben, die einfach eine Summe und ein Produkt aus Elementen jedes Arrays bildet und überprüft, ob beide Summen UND beide Produkte gleich sind. Die Variablen summe und produkt werde ich als double definieren.
Und wenn die Arrays unterschiedliche Länge haben, dann wird die Funktion gleich ohne Überprüfung mit einem Rückgabewert beendet.

Ich habe mal ein kleines Testprogramm geschrieben:

Code: Alles auswählen

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
	int array1[100], array2[100];
	unsigned long long a1s = 0, a2s = 0;
	double a1p=1.0, a2p = 1.0;
	srand ( time(NULL) );
	for(int a = 0; a < 1000000; a++)
	{
		a1s = 0;
		a1p = 1;
		a2s = 0;
		a2p = 1;
		for(int i = 0; i < 100; i++)
		{
			array1[i] = rand() + 1;
			array2[i] = rand() + 1;

		}
		for(int i = 0; i < 100; i++)
		{
			a1s += array1[i];
			a1p = (array1[i] % 2 == 0)?(a1p/array1[i]):(a1p*array1[i]);
			a2s += array2[i];
			a2p = (array2[i] % 2 == 0)?(a2p/array2[i]):(a2p*array2[i]);
		}
		cout << a1s << " "<< a1p << " "<< a2s << " "<< a2p << " " << endl;
		if(a1s == a2s && a1p == a2p)
		{
			cout << "Permutation!" << endl;
			for(int i = 0; i < 100; i++)
			{
				cout << array1[i]  << " | " << array2[i] << endl;
			}
			getchar();
		}
	}
	getchar();
	return 0;
}

Das Produkt wird schnell zu groß, ich hatte bei 100 Zahlen dauerhaft Infinity, weswegen ich alle durch 2 Teilbahren zahlen mit der Potenz -1 multipliziert habe, das verfälscht das Ergebnis nicht.
Das ist eine Lösungsmöglichkeit, die an sich sehr Performant wäre und eben auf einer sehr Elementaren Lösung basiert, also wenig Bugs produzieren wird.
Aber was Problematisch werden wird, ist die Gleitkomma Genauigkeit von Computern und die Begrenzte Zahlenmenge von 32/64-Bit.
Damit ist es an sich eine sehr elegante, mathematische Lösung, aber in der Praxis als Algorithmus schlecht nutzbar, weil es in die Grauzonen der Numerik geht.