Aufgabe zu Permutationen

[Cherrycoke]

Hallo,

ich habe an diesen Beitrag eine Aufgabenstellung angehängt, die ich nicht ganz verstehe. Deshalb bitte ich euch einmal kurz um Hilfe.

Zwar weiß ich was eine Permutation ist, allerdings verstehe ich nicht, was das Urbild in der Aufgabenstellung ist. Ich habe es mir mal versucht an einem Beispiel klar zu machen. Sage ich mal meine Menge M = {1, 2, 3}.

Dann könnte ich ja folgende sechs Permutationen erhalten:
123
132
213
231
312
321

Ich mache es mir mit der formalen Definition noch etwas schwer. In der Aufgabenstellung steht, dass ich eine Menge N auf sich selbst abbilde. Diese Abbildung heißt pi. Aber hier fängt es bei mir schon an. Was heißt es denn, eine Menge auf sich selbst Abzubilden?
Wenn ich jetzt N = {1,2} habe, und ich wähle nun ein x aus N, welches ich Abbilden möchte, was passiert denn dann? Ich bin verwirrt, weil mir irgendwie die Funktionsvorschrift fehlt.

Eigentlich ist das wohl Kindergarten³ - aber trotzdem wäre ich froh, wenn mir jemand mal kurz auf die Sprünge helfen könnte.

Danke!

 

[deepthroat]

Hi.

Zwar weiß ich was eine Permutation ist, allerdings verstehe ich nicht, was das Urbild in der Aufgabenstellung ist. Ich habe es mir mal versucht an einem Beispiel klar zu machen. Sage ich mal meine Menge M = {1, 2, 3}.

Dann könnte ich ja folgende sechs Permutationen erhalten:
123
132
213
231
312
321

Ich mache es mir mit der formalen Definition noch etwas schwer. In der Aufgabenstellung steht, dass ich eine Menge N auf sich selbst abbilde. Diese Abbildung heißt pi. Aber hier fängt es bei mir schon an. Was heißt es denn, eine Menge auf sich selbst Abzubilden?

D.h. einfach nur, das das Resultat einer Funktion (also der Wertebereich) ausschließlich Elemente der Eingabemenge (Definitionsbereich) sind.

Bsp: f : int -> int
g: string -> string

oder in C Schreibweise

int f (int);
string g (string);

Gegenbsp:

string x (int); // bildet Integer auf Strings ab

Wenn ich jetzt N = {1,2} habe, und ich wähle nun ein x aus N, welches ich Abbilden möchte, was passiert denn dann? Ich bin verwirrt, weil mir irgendwie die Funktionsvorschrift fehlt.

Das eine Permutation eine Abbildung (also eine Funktion) ist, hast du auch wirklich verstanden?

Bsp:

für N := { 1, 2, 3 }

pi(1) -> 3
pi(2) -> 1
pi(3) -> 2

pi ist eine Permutation.

Du hast jetzt die rechte Seite in einem Array a = [3, 1, 2] gegeben und sollst für ein y ?N ein x ?N ermitteln für das gilt pi(x) = y

Gruß

 

[Cherrycoke]

Das eine Permutation eine Abbildung (also eine Funktion) ist, hast du auch wirklich verstanden?

Bsp:

für N := { 1, 2, 3 }

pi(1) -> 3
pi(2) -> 1
pi(3) -> 2

pi ist eine Permutation.

Nein, ich glaube nicht, dass ich es verstanden habe. Ich verstehe nicht ganz, wie abgebildet wird. Warum wird pi(1) auf die 3 abgebildet?

 

[deepthroat]

Nein, ich glaube nicht, dass ich es verstanden habe. Ich verstehe nicht ganz, wie abgebildet wird. Warum wird pi(1) auf die 3 abgebildet?

pi(1) wird überhaupt nicht abgebildet.

pi ist eine Abbildung. pi bildet ab. D.h. es ist eine Vorschrift, wie etwas abgebildet wird. Eine Abbildung ist doch nur eine Zuordnung von Elementen, also eine Menge von Paaren:

Bsp:

pi := { (1, 3), (2, 1), (3, 2) }

Die Permutation pi könnte auch anders aussehen, sprich: anders abbilden. Die möglichen Permutationen von {1, 2, 3} hast du doch schon genannt. Jede dieser Permutation so wie du sie aufgeschrieben hast, entspricht einer möglichen Definition von pi.

Gruß

 

[Cherrycoke]

Du hast jetzt die rechte Seite in einem Array a = [3, 1, 2] gegeben und sollst für ein y ?N ein x ?N ermitteln für das gilt pi(x) = y

Ich verstehe es wirklich nicht. Kann ich dann y und x nicht beliebig wählen? Wird nicht jedes Element einmal auf ein anderes abgebildet? Ich bin verwirrt. :-(

Edit [Ergänzung]:

Habe ich denn in Aufgabenstellung a) eine mögliche Definition in Form eines Arrays der Art:

i       1    2    3    4
pi[i]  3   4    2    1

gegeben?

 

[Cromon]

Also dass sich die Menge auf sich selbst abbildet heisst salopp gesagt nichts anderes als: Für jedes Element dieser Menge ist der Funktionswert wieder in dieser Menge und jedes Element der Menge kommt irgendwo als Funktionswert wieder vor. Da eine Permutation ja nichts anderes macht als zwei Elemente zu vertauschen ist es logisch dass Definitionsmenge und Zielmenge identisch sind, die Abbildung also die Definitionsmenge N auf sich selbst abbildet.

Das ist der erste Teil der formalen Definition. Im zweiten Teil steht, dass für jedes Element aus der Definitionsmenge ein eindeutiges Element aus der Bildmenge (= Definitionsmenge) vorhanden ist. (Kurz gesagt: Die Funktion ist bijektiv)

Möglicher Code (zur Veranschaulichung)

void InvertPermutation(int* pInput, int numElems, int* pOutput, int minElem)
{
	int i = 0;
	while(i < numElems)
	{
		pOutput[pInput[i] - minElem] = i + minElem;
		++i;
	}
}

int Invert(int input, int* pInverse, int minElem)
{
	return pInverse[input - minElem];
}

int main()
{
	int pi[] = { 2, 3, 4, 1 };
	int pi_inverse[] = { 0, 0, 0, 0 };
	int i = 1;
	InvertPermutation(pi, 4, pi_inverse, 1);
	while(i <= 4)
	{
		printf("%u => %u => %u\n", i, pi[i - 1], Invert(pi[i - 1], pi_inverse, 1));
		++i;
	}
	getchar();
}

/edit
mit der Ausgabe:
1 => 2 => 1
2 => 3 => 2
3 => 4 => 3
4 => 1 => 4

 

[Cherrycoke]

Ich wollte jetzt nur nochmal sicher gehen ob ich alles richtig verstanden habe.

Ich habe eine Menge N={1,2,3,4} und sage nun zum Beispiel :

pi := { (1, 3), (2, 4), (3, 1), (4,2) }

Dann wären meine Urbilder pi^-1(3) = 1, pi^-1(4) = 2,pi^-1(1) =3 und pi^-1(2) = 4.

Edit: Oh, ich habe den Edit aus dem vorangegangenen Post nicht gesehen. Scheine es ja dann richtig verstanden zu haben.

Was heißt denn: "Die Permutation soll als ein Feld ihrer Funktionswerte gegeben sein"? Bedeutet das, dass ich ein zweidimensionales Feld der Art:

x | pi(x)
1 3
2 2
3 1

Oder habe ich nur ein eindimensionales Feld der Art: 3, 2, 1? Darf ich dann aber annehmen, dass es sich an der ersten Stelle um pi(1) handelt?
habe?

 

[Cromon]

Ich verstehe das als eindimensionales Feld mit pi(1) ist arrPi[0], pi(2) ist arrPi[1], ...