Das zweite Praktikum beschäftigt sich mit Operationen und Darstellungen von Permutationen sowie der Erzeugung von Gruppenelementen. Weiterhin sollen Erzeuger und Gruppenordnungen für geometrische Objekte definiert werden.
| Skript-Anfang | Praktikum 2 – Seite 1 |
|---|---|
| Skript-Ende | Praktikum 2 – Seite 2 |
Operationen und Darstellungen von Permutationen
Implementieren Sie die Multiplikation und die Inversion von Permutationen in Sn. Verwenden Sie die Listennotation als Darstellung im Rechner und beachten Sie die Laufzeit von O(n) für beide Routinen. Implementieren Sie die Zyklennotation als Ausgabe von Permutationen. Beachten Sie dabei die drei Konventionen: Sortieren nach dem kleinsten Element innerhalb eines Zykels, Weglassen von Einerzyklen und die gesonderte Darstellung der Identität.
Konsolenausgabe des folgenden Quellcodes
Ausgaben Zykel (Offset 1):
vA [5,4,3,2,1] = (1,5)(2,4)
vB [2,4,1,3,5] = (1,2,4,3)
vC [2,5,4,3,1] = (1,2,5)(3,4)
vD [3,2,6,9,5,7,1,8,4] = (1,3,6,7)(4,9)
id [1,2,3,4,5] = id5
Multiplikation von:
(1,5)(2,4) * (1,2,4,3) -> (1,4,3,5)
Inversion:
(1,2,5)(3,4) -> (1,5,2)(3,4)Includes und Deklarationen
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>
#include <assert.h>
#include <algorithm>
using namespace std;
string list_to_cycle(vector<unsigned int>& vVector, int iOffset);
string output_list(vector<unsigned int>& vVector, int iOffset);
bool isId(vector<unsigned int>& vTmp);
vector<unsigned int> invertieren(vector<unsigned int>& vVector);
vector<unsigned int> multiplizieren(vector<unsigned int>& vLinks, vector<unsigned int>& vRechts);Main()
int main() {
int iTmp[] = {0,1,2,3,4};
vector<unsigned int> vID(iTmp, iTmp + sizeof iTmp / sizeof iTmp[0]);
int iTmp2[] = {4,3,2,1,0};
vector<unsigned int> vA(iTmp2, iTmp2 + sizeof iTmp2 / sizeof iTmp2[0]);
int iTmp3[] = {1,3,0,2,4};
vector<unsigned int> vB(iTmp3, iTmp3 + sizeof iTmp3 / sizeof iTmp3[0]);
int iTmp4[] = {1,4,3,2,0};
vector<unsigned int> vC(iTmp4, iTmp4 + sizeof iTmp4 / sizeof iTmp4[0]);
// 3,2,6,9,5,7,1,8,4 // http://cims.nyu.edu/~kiryl/teaching/aa/les100103.pdf (1367)(49)
int iTmp5[] = {2,1,5,8,4,6,0,7,3};
vector<unsigned int> vD(iTmp5, iTmp5 + sizeof iTmp5 / sizeof iTmp5[0]);
// Umwandlung in Zykelnotation (Offset 1)
cout << "Ausgaben Zykel (Offset 1):\n";
cout << "vA [5,4,3,2,1] = " << list_to_cycle(vA,1) << "\n";
cout << "vB [2,4,1,3,5] = " << list_to_cycle(vB,1) << "\n";
cout << "vC [2,5,4,3,1] = " << list_to_cycle(vC,1) << "\n";
cout << "vD [3,2,6,9,5,7,1,8,4] = " << list_to_cycle(vD,1) << "\n";
cout << "id [1,2,3,4,5] = " << list_to_cycle(vID,1)<< "\n\n";
//Multiplizieren (Offset 1)
vector<unsigned int> vTmp=multiplizieren(vA,vB);
cout << "Multiplikation von: \n"
<< list_to_cycle(vA,1)
<< " * "
<< list_to_cycle(vB,1)
<< " -> "
<< list_to_cycle(vTmp,1)
<< "\n\n";
// Invertieren (Offset 1)
vTmp = invertieren(vC);
cout << "Inversion: \n";
cout << list_to_cycle(vC,1) << " -> " << list_to_cycle(vTmp,1);
cout << "\n\n";
}Multiplikation
vector<unsigned int> multiplizieren(vector<unsigned int>& vLinks, vector<unsigned int>& vRechts)
{
vector<unsigned int> tmp(vRechts.size(),0);
for (unsigned int i=0;i<vRechts.size();i++)
{
tmp[i]=vLinks[vRechts[i]];
}
return tmp;
}Inversion
vector<unsigned int> invertieren(vector<unsigned int>& vVector)
{
vector<unsigned int> tmp(vVector.size(),0);
for (unsigned int i=0;i<vVector.size();i++)
{
tmp[vVector[i]]=i;
}
return tmp;
}Ausgabe in Zykelnotation
string list_to_cycle(vector<unsigned int>& vVector, int iOffset) {
stringstream ss;
if (isId(vVector)) {
ss << "id" << vVector.size();
} else {
bool bAktiv[vVector.size()];
for (unsigned int i = 0; i < vVector.size(); i++) {
bAktiv[i] = true;
}
for (unsigned int i = 0; i < vVector.size(); i++) {
if (bAktiv[i]) {
if (i == vVector[i]) {
bAktiv[i] = false;
continue;
} else {
ss << "(";
ss << i + iOffset;
bAktiv[i] = false;
int j = i;
while (bAktiv[vVector[j]]) {
j = vVector[j];
ss << "," << j + iOffset;
bAktiv[j] = false;
}
ss << ")";
}
}
}
}
return ss.str();
}Hilfsfunktionen
bool isId(vector<unsigned int>& vTmp) {
for (unsigned int i = 0; i < vTmp.size(); i++) {
if (i != vTmp[i]) {
return false;
}
}
return true;
}
string output_list(vector<unsigned int>& vVector, int iOffset)
{
stringstream ss;
if (isId(vVector)==true)
{
ss << "id" << vVector.size();
}
else
{
ss << "[";
for (unsigned int i=0;i<vVector.size();i++)
{
ss << vVector[i]+ iOffset;
if (i<vVector.size()-1)
{
ss << ",";
}
}
ss << "]";
}
return ss.str();
}Erzeugung von Gruppenelementen
Entwerfen und implementieren Sie einen Algorithmus, welche bei Eingabe einer Liste von Permutationen \(\pi_0, \cdots, \pi_{l-1} \in S_n\) alle Gruppenelemente der von diesen Permutationen erzeugten Gruppe \( G=\left \langle \pi_0 ,\cdots, \pi_{l-1} \right \rangle \) generiert. Dokumentieren und erläutern Sie alle Schritte nachvollziehbar.
Konsolenausgabe des folgenden Quellcodes
Aufgabe 2:
Erzeuger:
(0,1,2,3)
(0,1)(2,3)
Gruppenelemente:
[1,2,3,0] | (0,1,2,3)
[1,0,3,2] | (0,1)(2,3)
[2,3,0,1] | (0,2)(1,3)
[0,3,2,1] | (1,3)
[2,1,0,3] | (0,2)
id4 | id4
[3,0,1,2] | (0,3,2,1)
[3,2,1,0] | (0,3)(1,2)Includes und Deklarationen
Für diese Aufgabe benötigen wir die Invertierung nicht mehr. Stattdessen deklarieren wir nun eine Funktion zur Überprüfung der Gleichheit von zwei Vektoren sowie die Funktion zur Erzeugung aller Gruppenelemente.
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>
#include <assert.h>
#include <algorithm>
using namespace std;
string list_to_cycle(vector<unsigned int>& vVector, int iOffset);
string output_list(vector<unsigned int>& vVector, int iOffset);
bool isId(vector<unsigned int>& vTmp);
vector<unsigned int> multiplizieren(vector<unsigned int>& vLinks, vector<unsigned int>& vRechts);
void create_group(vector< vector<unsigned int> >& vErzeuger);
bool areEqual(vector<unsigned int>& vA, vector<unsigned int>& vB);Main()
int main() {
cout << "Aufgabe 2:\n\n";
vector< vector<unsigned int> > vErzeuger;
vector<unsigned int> vErzeuger1;
vErzeuger1.push_back(1);
vErzeuger1.push_back(2);
vErzeuger1.push_back(3);
vErzeuger1.push_back(0);
vector<unsigned int> vErzeuger2;
vErzeuger2.push_back(1);
vErzeuger2.push_back(0);
vErzeuger2.push_back(3);
vErzeuger2.push_back(2);
vErzeuger.push_back(vErzeuger1);
vErzeuger.push_back(vErzeuger2);
create_group(vErzeuger);
}Erzeugung aller Gruppenelemente
void create_group(vector< vector<unsigned int> >& vErzeuger)
{
vector< vector<unsigned int> > vSchlange;
vector< vector<unsigned int> > vAblage;
vector<unsigned int> tmp;
cout << "Erzeuger:\n";
for (unsigned int i=0;i<vErzeuger.size();i++)
{
vAblage.push_back(vErzeuger.at(i));
vSchlange.push_back(vErzeuger.at(i));
cout << list_to_cycle(vErzeuger.at(i),0) << "\n";
}
cout << "\n";
// Läuft solange die Qu nicht leer ist
while (vSchlange.size()>0)
{
// Laufe alle Erzeuger ab und wende sie auf das erste Element in Q an
for (unsigned int j=0;j<vErzeuger.size();j++)
{
// Erzeuge Element
vector<unsigned int> vT = multiplizieren(vErzeuger.at(j),vSchlange.at(0));
bool unknown=true;
// Prüfe ob Element bekannt ist
for (unsigned int x=0;x<vAblage.size();x++)
{
tmp=vAblage.at(x);
if (areEqual(vT, tmp)==true)
{
unknown=false;
break;
}
}
//wenn unbekannt, kommt es auf die Q
if (unknown==true)
{
vSchlange.push_back(vT);
vAblage.push_back(vT);
}
}
// entferne erstes Element aus Q nachdem alle Erzeuger drόber sind
tmp=vSchlange.at(0);
vSchlange.erase(vSchlange.begin());
}
// Ausgabe der Ablage
cout << "Gruppenelemente:\n";
for (unsigned int i=0;i<vAblage.size();i++)
{
cout << output_list(vAblage.at(i),0) << " | " << list_to_cycle(vAblage.at(i),0) << "\n";
}
}Hilfsfunktionen
Hier ist die Vergleichsfunktion zweier Integer-Vektoren zu finden. Eine wesentlich effizientere Vergleichsmethode wäre es den Rang beider Vektoren zu bestimmen und diesen zu vergleichen. Für dieses Praktikum ist diese Lösung jedoch ausreichend.
bool areEqual(vector<unsigned int>& vA, vector<unsigned int>& vB)
{
// Größe weicht ab / vermeidet Fehler
if (vA.size()!=vB.size())
{
// Groessenabweichung
return false;
}
// Vergleiche Stellenweise
for (unsigned int i=0;i<vA.size();i++)
{
if (vA[i]!=vB[i])
{
// Stellenweise Abweichung
return false;
}
}
// Sie sind gleich
return true;
}Erzeuger von geometrischen Objekten
Definieren Sie für folgende Gruppen Erzeuger und generieren Sie alle Gruppenelemente mit der Routine aus Aufgabe 2. Wie sind die Gruppenordnungen?
Symmetriegruppe D3 des regulären Dreiecks
Erzeuger:
(0,1,2)
(0,1)
Gruppenelemente:
[1,2,0] | (0,1,2)
[1,0,2] | (0,1)
[2,0,1] | (0,2,1)
[0,2,1] | (1,2)
[2,1,0] | (0,2)
id3 | id3Die Ordnung der Gruppe beträgt 6.
Symmetriegruppe V4 eines Rechtecks mit unterschiedlicher Seitenlänge
Erzeuger:
(0,1)(2,3)
(0,2)(1,3)
Gruppenelemente:
[1,0,3,2] | (0,1)(2,3)
[2,3,0,1] | (0,2)(1,3)
id4 | id4
[3,2,1,0] | (0,3)(1,2)Die Ordnung der Gruppe beträgt 4.
Symmetriegruppe T des Tetraeders
Erzeuger:
(0,1,2)
(0,3)(1,2)
Gruppenelemente:
[1,2,0,3] | (0,1,2)
[3,2,1,0] | (0,3)(1,2)
[2,0,1,3] | (0,2,1)
[2,1,3,0] | (0,2,3)
[3,0,2,1] | (0,3,1)
id4 | id4
[1,3,2,0] | (0,1,3)
[0,2,3,1] | (1,2,3)
[3,1,0,2] | (0,3,2)
[0,3,1,2] | (1,3,2)
[2,3,0,1] | (0,2)(1,3)
[1,0,3,2] | (0,1)(2,3)Die Gruppenordnung beträgt 12.
Symmetriegruppe Q des Würfels
Erzeuger:
(0,1,2,3)(4,5,6,7)
(0,3,7,4)(1,2,6,5)
Gruppenelemente:
[1,2,3,0,5,6,7,4] | (0,1,2,3)(4,5,6,7)
[3,2,6,7,0,1,5,4] | (0,3,7,4)(1,2,6,5)
[2,3,0,1,6,7,4,5] | (0,2)(1,3)(4,6)(5,7)
[2,6,7,3,1,5,4,0] | (0,2,7)(1,6,4)
[0,3,7,4,1,2,6,5] | (1,3,4)(2,7,5)
[7,6,5,4,3,2,1,0] | (0,7)(1,6)(2,5)(3,4)
[3,0,1,2,7,4,5,6] | (0,3,2,1)(4,7,6,5)
[6,7,3,2,5,4,0,1] | (0,6)(1,7)(2,3)(4,5)
[3,7,4,0,2,6,5,1] | (0,3)(1,7)(2,4)(5,6)
[6,5,4,7,2,1,0,3] | (0,6)(1,5)(2,4)(3,7)
[1,0,4,5,2,3,7,6] | (0,1)(2,4)(3,5)(6,7)
[4,7,6,5,0,3,2,1] | (0,4)(1,7)(2,6)(3,5)
[4,5,1,0,7,6,2,3] | (0,4,7,3)(1,5,6,2)
id8 | id8
[7,3,2,6,4,0,1,5] | (0,7,5)(1,3,6)
[7,4,0,3,6,5,1,2] | (0,7,2)(1,4,6)
[5,4,7,6,1,0,3,2] | (0,5)(1,4)(2,7)(3,6)
[0,4,5,1,3,7,6,2] | (1,4,3)(2,5,7)
[5,1,0,4,6,2,3,7] | (0,5,2)(3,4,6)
[2,1,5,6,3,0,4,7] | (0,2,5)(3,6,4)
[5,6,2,1,4,7,3,0] | (0,5,7)(1,6,3)
[4,0,3,7,5,1,2,6] | (0,4,5,1)(2,3,7,6)
[1,5,6,2,0,4,7,3] | (0,1,5,4)(2,6,7,3)
[6,2,1,5,7,3,0,4] | (0,6)(1,2)(3,5)(4,7)Die Gruppenordnung beträgt 24.
Symmetriegruppe I des Ikosaeders
Erzeuger:
(1,2,3,4,5)(6,7,8,9,10)
(0,3,10,9,1)(4,6,11,8,5)
Gruppenelemente:
[0,2,3,4,5,1,7,8,9,10,6,11] | (1,2,3,4,5)(6,7,8,9,10)
[3,0,2,10,6,4,11,7,5,1,9,8] | (0,3,10,9,1)(4,6,11,8,5)
[0,3,4,5,1,2,8,9,10,6,7,11] | (1,3,5,2,4)(6,8,10,7,9)
[3,2,10,6,4,0,7,5,1,9,11,8] | (0,3,6,7,5)(1,2,10,11,8)
[4,0,3,6,7,5,11,8,1,2,10,9] | (0,4,7,8,1)(2,3,6,11,9)
[10,3,2,9,11,6,8,7,4,0,1,5] | (0,10,1,3,9)(4,11,5,6,8)
[0,4,5,1,2,3,9,10,6,7,8,11] | (1,4,2,5,3)(6,9,7,10,8)
[3,10,6,4,0,2,5,1,9,11,7,8] | (0,3,4)(1,10,7)(2,6,5)(8,9,11)
[4,3,6,7,5,0,8,1,2,10,11,9] | (0,4,5)(1,3,7)(2,6,8)(9,10,11)
[10,2,9,11,6,3,7,4,0,1,8,5] | (0,10,8)(1,2,9)(3,11,5)(4,6,7)
[5,0,4,7,8,1,11,9,2,3,6,10] | (0,5,1)(2,4,8)(3,7,9)(6,11,10)
[6,3,10,11,7,4,8,5,0,2,9,1] | (0,6,8)(1,3,11)(2,10,9)(4,7,5)
[6,4,3,10,11,7,9,8,5,0,2,1] | (0,6,9)(1,4,11)(2,3,10)(5,7,8)
[9,10,2,1,8,11,5,7,6,3,0,4] | (0,9,3,1,10)(4,8,6,5,11)
[0,5,1,2,3,4,10,6,7,8,9,11] | (1,5,4,3,2)(6,10,9,8,7)
[3,6,4,0,2,10,1,9,11,7,5,8] | (0,3)(1,6)(2,4)(5,10)(7,9)(8,11)
[4,6,7,5,0,3,1,2,10,11,8,9] | (0,4)(1,6)(2,7)(3,5)(8,10)(9,11)
[10,9,11,6,3,2,4,0,1,8,7,5] | (0,10,7)(1,9,8)(2,11,5)(3,6,4)
[5,4,7,8,1,0,9,2,3,6,11,10] | (0,5)(1,4)(2,7)(3,8)(6,9)(10,11)
[6,10,11,7,4,3,5,0,2,9,8,1] | (0,6,5,3,7)(1,10,8,2,11)
[9,2,1,8,11,10,7,6,3,0,5,4] | (0,9)(1,2)(3,8)(4,11)(5,10)(6,7)
[1,0,5,8,9,2,11,10,3,4,7,6] | (0,1)(2,5)(3,8)(4,9)(6,11)(7,10)
[7,4,6,11,8,5,9,1,0,3,10,2] | (0,7,1,4,8)(2,6,9,3,11)
[11,10,9,8,7,6,5,4,3,2,1,0] | (0,11)(1,10)(2,9)(3,8)(4,7)(5,6)
[7,5,4,6,11,8,10,9,1,0,3,2] | (0,7,9)(1,5,8)(2,4,11)(3,6,10)
[11,6,10,9,8,7,1,5,4,3,2,0] | (0,11)(1,6)(2,10)(3,9)(4,8)(5,7)
[10,6,3,2,9,11,1,8,7,4,0,5] | (0,10)(1,6)(2,3)(4,9)(5,11)(7,8)
[1,9,2,0,5,8,4,7,11,10,3,6] | (0,1,9,10,3)(4,5,8,11,6)
id12 | id12
[3,4,0,2,10,6,9,11,7,5,1,8] | (0,3,2)(1,4,10)(5,6,9)(7,11,8)
[4,7,5,0,3,6,2,10,11,8,1,9] | (0,4,3)(1,7,10)(2,5,6)(8,11,9)
[10,11,6,3,2,9,0,1,8,7,4,5] | (0,10,4,2,6)(1,11,5,9,7)
[5,7,8,1,0,4,2,3,6,11,9,10] | (0,5,4)(1,7,3)(2,8,6)(9,11,10)
[6,11,7,4,3,10,0,2,9,8,5,1] | (0,6)(1,11)(2,7)(3,4)(5,10)(8,9)
[9,1,8,11,10,2,6,3,0,5,7,4] | (0,9,5,2,8)(3,11,4,10,7)
[1,5,8,9,2,0,10,3,4,7,11,6] | (0,1,5)(2,8,4)(3,9,7)(6,10,11)
[7,6,11,8,5,4,1,0,3,10,9,2] | (0,7)(1,6)(2,11)(3,8)(4,5)(9,10)
[11,9,8,7,6,10,4,3,2,1,5,0] | (0,11)(1,9)(2,8)(3,7)(4,6)(5,10)
[1,2,0,5,8,9,7,11,10,3,4,6] | (0,1,2)(3,5,9)(4,8,10)(6,7,11)
[2,0,1,9,10,3,11,6,4,5,8,7] | (0,2,1)(3,9,5)(4,10,8)(6,11,7)
[8,5,7,11,9,1,10,2,0,4,6,3] | (0,8)(1,5)(2,7)(3,11)(4,9)(6,10)
[8,9,1,5,7,11,4,6,10,2,0,3] | (0,8,10)(1,9,2)(3,5,11)(4,7,6)
[8,1,5,7,11,9,6,10,2,0,4,3] | (0,8,2,5,9)(3,7,10,4,11)
[11,7,6,10,9,8,2,1,5,4,3,0] | (0,11)(1,7)(2,6)(3,10)(4,9)(5,8)
[8,11,9,1,5,7,0,4,6,10,2,3] | (0,8,6)(1,11,3)(2,9,10)(4,5,7)
[6,7,4,3,10,11,2,9,8,5,0,1] | (0,6,2,4,10)(1,7,9,5,11)
[9,11,10,2,1,8,0,5,7,6,3,4] | (0,9,6)(1,11,4)(2,10,3)(5,8,7)
[2,10,3,0,1,9,5,8,11,6,4,7] | (0,2,3)(1,10,4)(5,9,6)(7,8,11)
[4,5,0,3,6,7,10,11,8,1,2,9] | (0,4,6,10,2)(1,5,7,11,9)
[5,8,1,0,4,7,3,6,11,9,2,10] | (0,5,7,6,3)(1,8,11,10,2)
[9,8,11,10,2,1,3,0,5,7,6,4] | (0,9,7)(1,8,5)(2,11,4)(3,10,6)
[1,8,9,2,0,5,3,4,7,11,10,6] | (0,1,8,7,4)(2,9,11,6,3)
[7,11,8,5,4,6,0,3,10,9,1,2] | (0,7,3,5,6)(1,11,2,8,10)
[11,8,7,6,10,9,3,2,1,5,4,0] | (0,11)(1,8)(2,7)(3,6)(4,10)(5,9)
[2,1,9,10,3,0,6,4,5,8,11,7] | (0,2,9,8,5)(3,10,11,7,4)
[8,7,11,9,1,5,2,0,4,6,10,3] | (0,8,4,1,7)(2,11,3,9,6)
[2,3,0,1,9,10,8,11,6,4,5,7] | (0,2)(1,3)(4,9)(5,10)(6,8)(7,11)
[5,1,0,4,7,8,6,11,9,2,3,10] | (0,5,8,9,2)(3,4,7,11,10)
[7,8,5,4,6,11,3,10,9,1,0,2] | (0,7,10)(1,8,9)(2,5,11)(3,4,6)
[2,9,10,3,0,1,4,5,8,11,6,7] | (0,2,10,6,4)(1,9,11,7,5)Die Gruppenordnung beträgt 60. Es gilt verallgemeinert: \(|\text{Gruppenelemente}|=|\text{Knoten}|*|\text{Kanten pro Knoten}|\).