Menu Close

Diskrete Strukturen (Praktikum 3)

Maximilian Krieg 0 Comments

Das dritte Praktikum baut auf den Erkenntnissen des zweiten Praktikums auf und behandelt nun die Erzeugung von Bahnen. Zur Validierung der Korrektheit gibt es in der zweiten Aufgabe Testparameter, die erreicht werden müssen. Der hier beschriebene Quellcode stellt nur den für die Abgabe präsentierten Code dar. Weitere Resultate und Funktionen sind im Original-Code zu finden.

Skript-AnfangPraktikum 3 – Seite 1
Skript-EndePraktikum 3 – Seite 2

Erzeugung von Bahnen und Transversale

Schreiben Sie ein Programm, welches bei Eingabe einer Permutationsgruppe (über die Erzeuger) \(G=\left \langle \gamma_0,\cdots ,\gamma_{l-1} \right \rangle \leq S_n\) die Bahnen G\X auf der Menge X der k-Teilmengen der n elementigen Menge {0, … , n – 1} berechnet. Das Programm soll für jede Bahn einen Repräsentanten angeben.

Includes und Deklarationen

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>
#include <assert.h>
#include <algorithm>
using namespace std;
 
void multiply_subset_permutation(vector<unsigned int>& vSubset, vector<unsigned int>& vPermutation, vector<unsigned int>& vResult);
bool inResult(vector<unsigned int>& v1, vector<unsigned int>& v2);
int binkoeff(int n, int k);
int kSubsetRevDoorRank(vector<unsigned int>& vVec, int k);
vector<unsigned int> kSubsetRevDoorUnrank(int r, int k, int n);
void generate_orbits_new(vector<vector<unsigned int> >& vErzeuger, int n, int k);
vector<unsigned int> bit_to_list(vector<unsigned int>& vBitlist);
string output_list(vector<unsigned int>& vVector, int iOffset);

Main()

int main() {

     // Set 1
     vector<vector<unsigned int> > vErzeuger;
     static const int arr1[] = { 0, 3, 4, 1, 2, 5 };
     static const int arr2[] = { 3, 4, 0, 5, 1, 2 };
     vector<unsigned int> vTmp1(arr1, arr1 + sizeof(arr1) / sizeof(arr1[0]));
     vector<unsigned int> vTmp2(arr2, arr2 + sizeof(arr2) / sizeof(arr2[0]));
     vErzeuger.push_back(vTmp1);
     vErzeuger.push_back(vTmp2);
     generate_orbits_new(vErzeuger, 6, 3);

     // Set 2
     vector<vector<unsigned int> > vErzeuger;
     static const int arr1[] = { 5, 4, 3, 2, 1, 0, 7, 6 };
     static const int arr2[] = { 1, 0, 7, 6, 5, 4, 3, 2 };
     vector<unsigned int> vTmp1(arr1, arr1 + sizeof(arr1) / sizeof(arr1[0]));
     vector<unsigned int> vTmp2(arr2, arr2 + sizeof(arr2) / sizeof(arr2[0]));
     vErzeuger.push_back(vTmp1);
     vErzeuger.push_back(vTmp2);
     generate_orbits_new(vErzeuger, 8, 4); 
 
     // Set 3
     vector<vector<unsigned int> > vErzeuger;
     static const int arr1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 0 };
     static const int arr2[] = { 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
     vector<unsigned int> vTmp1(arr1, arr1 + sizeof(arr1) / sizeof(arr1[0]));
     vector<unsigned int> vTmp2(arr2, arr2 + sizeof(arr2) / sizeof(arr2[0]));
     vErzeuger.push_back(vTmp1);
     vErzeuger.push_back(vTmp2);
     generate_orbits_new(vErzeuger, 14, 5);

    // Set 4
    vector<vector<unsigned int> > vErzeuger;
    static const int arr1[] = { 19, 0, 20, 1, 21, 2, 22, 3, 15, 4, 16, 5, 17, 6, 18, 7, 27, 8, 28, 9, 29, 10, 30, 11, 23, 12, 24, 13, 25, 14, 26, 31 };
    static const int arr2[] = { 21, 9, 27, 0, 22, 10, 28, 3, 17, 13, 23, 4, 18, 14, 24, 15, 5, 25, 11, 16, 6, 26, 12, 19, 1, 29, 7, 20, 2, 30, 8, 31 };
    vector<unsigned int> vTmp1(arr1, arr1 + sizeof(arr1) / sizeof(arr1[0]));
    vector<unsigned int> vTmp2(arr2, arr2 + sizeof(arr2) / sizeof(arr2[0]));
    vErzeuger.push_back(vTmp1);
    vErzeuger.push_back(vTmp2);
    generate_orbits_new(vErzeuger, 31, 5);
   
    return 0;
}

Bahnerzeugung

void generate_orbits_new(vector<vector<unsigned int> >& vErzeuger, int n, int k) {
    vector<vector<vector<unsigned int> > > vOrbits;
 
    // Erzeugung der Menge
    cout << "n: " << n << endl;
    cout << "k: " << k << endl;
    cout << "Subset size: " << binkoeff(n, k) << endl;
 
    // Erzeugung des Vergleichsarrays
    int iElements = binkoeff(n, k);
    vector<bool> isUsed(iElements, false);
 
    for (int i = 0; i < iElements; i++) {
        // Ist die Teilmenge bereits genutzt?
        if (isUsed.at(i) == true)
            continue;
 
        // Noch nicht genutzt
        isUsed.at(i) == true;
 
        // Neue Bahn anlegen
        vector<vector<unsigned int> > vResult;
        vOrbits.push_back(vResult);
 
        // Schlange erzeugen
        vector<vector<unsigned int> > vSchlange;
        vector<unsigned int> vNoName = kSubsetRevDoorUnrank(i, n, k);
        vNoName = bit_to_list(vNoName);
        vSchlange.push_back(vNoName);

        // Laufe solange noch Elemente in der Schlange sind
        while (vSchlange.size() > 0) {
 
            // Durchlaufe alle Erzeuger
            for (unsigned int j = 0; j < vErzeuger.size(); j++) {
 
                // Temporärer Vektor
                vector<unsigned int> vTmp;
 
                multiply_subset_permutation(vSchlange.at(0), vErzeuger.at(j), vTmp);
                sort(vTmp.begin(), vTmp.end());
 
                // Neues Element?
                bool bNew = true;
 
                // Element schon in irgendeiner Bahn?
                for (unsigned int l = 0;
                        l < vOrbits.at(vOrbits.size() - 1).size(); l++) {
                    if (inResult(vTmp, vOrbits.at(vOrbits.size() - 1).at(l))) { // Bereits bekannte Permutation?
                        bNew = false;
                        break;
                    }
                }
 
                if (bNew == true) { 
                    // Nicht bekannt -> Hinzufuegen
                    vSchlange.push_back(vTmp);
                    vOrbits.at(vOrbits.size() - 1).push_back(vTmp);
                    
                    // "Benutzt" setzen --> rank holen
                    int iPos = kSubsetRevDoorRank(vTmp, k);
                    isUsed.at(iPos) = true;
                }
 
            } // for
            vSchlange.erase(vSchlange.begin());
        } // while
    } // for
    
    // Ausgabe
    for (unsigned int m = 0; m < vOrbits.size(); m++) {
        cout << "Bahn " << m + 1 << ": " << vOrbits.at(m).size() 
                << " Elemente, Repraesentant: "
                << output_list(vOrbits.at(m).at(0), 0) << endl;
    }
}

int kSubsetRevDoorRank(vector<unsigned int>& vVec, int k) {
    int i, r, s;
    r = 0;
    if ((k % 2) == 1)
        r = r - 1;
    s = 1;
    for (i = k; i >= 1; i = i - 1) {
        //cout << "i= " << i << endl;
        r = r +binkoeff(vVec.at(i - 1) + 1, i) * s;
        s = -s;
    }
    return (r);
}
 
vector<unsigned int> kSubsetRevDoorUnrank(int r, int n, int k)
{
    vector<unsigned int> vResult(n);
    //cout << "Size: " << vResult.size() << endl;
    int x, i, y;
    x = n;
    for (i = k; i >= 1; i = i - 1) {
        y = binkoeff(x, i);
        while (y > r) {
            x = x - 1;
            y = binkoeff(x, i);
        }
        vResult.at(x) = 1;
        r = binkoeff(x + 1, i) - r - 1;
    }
    return vResult;
}

Hilfsfunktionen

int binkoeff(int n, int r) {
    int i, b;
    if ((r < 0) || (n < r))
        return (0);
    if ((2 * r) > n)
        r = n - r;
    b = 1;
    if (r > 0)
        for (i = 0; i <= (r - 1); i = i + 1)
            b = (b * (n - i)) / (i + 1);
    return (b);
}
 
bool inResult(vector<unsigned int>& v1, vector<unsigned int>& v2) {
    if (v1.size() != v2.size())
        return false;
 
    for (unsigned int i = 0; i < v1.size(); i++) {
        if (v1.at(i) != v2.at(i))
            return false;
    }
    return true;
}

vector<unsigned int> bit_to_list(vector<unsigned int>& vBitlist) {
    vector<unsigned int> vList;
    for (unsigned int i = 0; i < vBitlist.size(); i++) {
        if (vBitlist.at(i) == 1) {
            vList.push_back(i);
        }
    }
 
    return vList;
}
 
void multiply_subset_permutation(vector<unsigned int>& vSubset,
        vector<unsigned int>& vPermutation, vector<unsigned int>& vResult) {
    for (unsigned int i = 0; i < vSubset.size(); i++) {
        vResult.push_back(vPermutation[vSubset[i]]);
    }
}

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();
}

Eingabe von Testparametern

Testen Sie das Programm für folgende Parameter.

Set 1

n=6

k=3

γ0 = (1, 3)(2, 4)

γ1 = (0, 3, 5, 2)(1, 4)

n: 6 
k: 3 
Subset size: 20  
Bahn 1: 4 Elemente, Repraesentant: [0,3,4] 
Bahn 2: 12 Elemente, Repraesentant: [0,1,4]  
Bahn 3: 4 Elemente, Repraesentant: [0,1,3]

Set 2

n=8

k=4

γ0 = (0, 5)(1, 4)(2, 3)(7, 6)

γ1 = (0, 1)(2, 7)(3, 6)(4, 5)

n: 8  
k: 4  
Subset size: 70 
Bahn 1: 4 Elemente, Repraesentant: [2,3,4,5]  
Bahn 2: 4 Elemente, Repraesentant: [1,2,4,5]  
Bahn 3: 2 Elemente, Repraesentant: [1,2,3,4]  
Bahn 4: 4 Elemente, Repraesentant: [1,2,3,5]  
Bahn 5: 4 Elemente, Repraesentant: [1,3,4,5]  
Bahn 6: 1 Elemente, Repraesentant: [0,1,4,5]  
Bahn 7: 4 Elemente, Repraesentant: [0,1,3,5]  
Bahn 8: 4 Elemente, Repraesentant: [0,1,2,5]  
Bahn 9: 2 Elemente, Repraesentant: [0,2,3,5]  
Bahn 10: 2 Elemente, Repraesentant: [0,3,4,7] 
Bahn 11: 4 Elemente, Repraesentant: [0,3,5,7] 
Bahn 12: 4 Elemente, Repraesentant: [0,2,3,7] 
Bahn 13: 4 Elemente, Repraesentant: [0,2,4,7] 
Bahn 14: 4 Elemente, Repraesentant: [0,2,5,7] 
Bahn 15: 2 Elemente, Repraesentant: [0,1,2,7] 
Bahn 16: 4 Elemente, Repraesentant: [0,1,3,7] 
Bahn 17: 2 Elemente, Repraesentant: [1,3,5,7] 
Bahn 18: 4 Elemente, Repraesentant: [1,2,3,7] 
Bahn 19: 2 Elemente, Repraesentant: [2,4,5,7] 
Bahn 20: 4 Elemente, Repraesentant: [2,3,4,7] 
Bahn 21: 4 Elemente, Repraesentant: [2,3,5,7]
Bahn 22: 1 Elemente, Repraesentant: [2,3,6,7]

Set 3

n=14

k=5

γ0 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)

γ1 = (0, 13)(1, 12)(2, 11)(3, 10)(4, 9)(5, 8)(6, 7)

n: 14 
k: 5  
Subset size: 2002 
Bahn 1: 14 Elemente, Repraesentant: [1,2,3,4,5] 
Bahn 2: 28 Elemente, Repraesentant: [1,2,3,5,6] 
Bahn 3: 28 Elemente, Repraesentant: [1,3,4,5,6] 
Bahn 4: 28 Elemente, Repraesentant: [1,2,3,6,7] 
Bahn 5: 28 Elemente, Repraesentant: [1,3,4,6,7] 
Bahn 6: 14 Elemente, Repraesentant: [1,2,4,6,7] 
Bahn 7: 28 Elemente, Repraesentant: [1,4,5,6,7] 
Bahn 8: 28 Elemente, Repraesentant: [1,3,5,6,7] 
Bahn 9: 14 Elemente, Repraesentant: [1,3,4,5,7] 
Bahn 10: 28 Elemente, Repraesentant: [1,2,3,7,8] 
Bahn 11: 28 Elemente, Repraesentant: [1,3,4,7,8]  
Bahn 12: 28 Elemente, Repraesentant: [1,2,4,7,8]  
Bahn 13: 28 Elemente, Repraesentant: [1,4,5,7,8]  
Bahn 14: 28 Elemente, Repraesentant: [1,3,5,7,8]  
Bahn 15: 28 Elemente, Repraesentant: [1,5,6,7,8]  
Bahn 16: 28 Elemente, Repraesentant: [1,4,6,7,8]  
Bahn 17: 28 Elemente, Repraesentant: [1,3,6,7,8]  
Bahn 18: 28 Elemente, Repraesentant: [1,3,4,6,8]  
Bahn 19: 28 Elemente, Repraesentant: [1,4,5,6,8]  
Bahn 20: 28 Elemente, Repraesentant: [1,2,3,8,9]  
Bahn 21: 28 Elemente, Repraesentant: [1,3,4,8,9]  
Bahn 22: 28 Elemente, Repraesentant: [1,2,4,8,9]  
Bahn 23: 28 Elemente, Repraesentant: [1,4,5,8,9]  
Bahn 24: 28 Elemente, Repraesentant: [1,3,5,8,9]  
Bahn 25: 14 Elemente, Repraesentant: [1,2,5,8,9] 
Bahn 26: 28 Elemente, Repraesentant: [1,5,6,8,9]  
Bahn 27: 28 Elemente, Repraesentant: [1,4,6,8,9]  
Bahn 28: 28 Elemente, Repraesentant: [1,3,6,8,9]  
Bahn 29: 28 Elemente, Repraesentant: [1,6,7,8,9]  
Bahn 30: 28 Elemente, Repraesentant: [1,5,7,8,9]  
Bahn 31: 28 Elemente, Repraesentant: [1,4,7,8,9]  
Bahn 32: 28 Elemente, Repraesentant: [1,3,7,8,9]  
Bahn 33: 28 Elemente, Repraesentant: [1,3,4,7,9]  
Bahn 34: 28 Elemente, Repraesentant: [1,4,5,7,9]  
Bahn 35: 14 Elemente, Repraesentant: [1,3,5,7,9]  
Bahn 36: 28 Elemente, Repraesentant: [1,5,6,7,9]  
Bahn 37: 28 Elemente, Repraesentant: [1,4,6,7,9]  
Bahn 38: 14 Elemente, Repraesentant: [1,4,5,6,9]  
Bahn 39: 28 Elemente, Repraesentant: [1,3,4,9,10] 
Bahn 40: 28 Elemente, Repraesentant: [1,4,5,9,10] 
Bahn 41: 28 Elemente, Repraesentant: [1,3,5,9,10] 
Bahn 42: 28 Elemente, Repraesentant: [1,2,5,9,10] 
Bahn 43: 28 Elemente, Repraesentant: [1,5,6,9,10] 
Bahn 44: 28 Elemente, Repraesentant: [1,4,6,9,10] 
Bahn 45: 28 Elemente, Repraesentant: [1,3,6,9,10] 
Bahn 46: 14 Elemente, Repraesentant: [1,6,7,9,10] 
Bahn 47: 28 Elemente, Repraesentant: [1,5,7,9,10] 
Bahn 48: 28 Elemente, Repraesentant: [1,4,7,9,10] 
Bahn 49: 28 Elemente, Repraesentant: [1,3,7,9,10] 
Bahn 50: 28 Elemente, Repraesentant: [1,6,8,9,10] 
Bahn 51: 28 Elemente, Repraesentant: [1,5,8,9,10] 
Bahn 52: 28 Elemente, Repraesentant: [1,4,8,9,10] 
Bahn 53: 14 Elemente, Repraesentant: [1,3,8,9,10] 
Bahn 54: 28 Elemente, Repraesentant: [1,3,4,8,10] 
Bahn 55: 28 Elemente, Repraesentant: [1,4,5,8,10] 
Bahn 56: 28 Elemente, Repraesentant: [1,3,5,8,10] 
Bahn 57: 28 Elemente, Repraesentant: [1,5,6,8,10] 
Bahn 58: 28 Elemente, Repraesentant: [1,4,6,8,10] 
Bahn 59: 28 Elemente, Repraesentant: [1,5,7,8,10] 
Bahn 60: 28 Elemente, Repraesentant: [1,4,7,8,10] 
Bahn 61: 28 Elemente, Repraesentant: [1,4,5,7,10] 
Bahn 62: 28 Elemente, Repraesentant: [1,5,6,7,10] 
Bahn 63: 14 Elemente, Repraesentant: [1,5,6,10,11]  
Bahn 64: 28 Elemente, Repraesentant: [1,4,6,10,11]  
Bahn 65: 28 Elemente, Repraesentant: [1,5,7,10,11]  
Bahn 66: 28 Elemente, Repraesentant: [1,4,7,10,11]  
Bahn 67: 28 Elemente, Repraesentant: [1,3,7,10,11]  
Bahn 68: 28 Elemente, Repraesentant: [1,5,8,10,11]  
Bahn 69: 28 Elemente, Repraesentant: [1,4,8,10,11]
Bahn 70: 14 Elemente, Repraesentant: [1,5,9,10,11]  
Bahn 71: 14 Elemente, Repraesentant: [1,3,5,9,11] 
Bahn 72: 28 Elemente, Repraesentant: [1,4,6,9,11] 
Bahn 73: 14 Elemente, Repraesentant: [1,3,6,9,11] 
Bahn 74: 14 Elemente, Repraesentant: [1,5,7,9,11] 
Bahn 75: 28 Elemente, Repraesentant: [1,4,7,9,11] 
Bahn 76: 28 Elemente, Repraesentant: [1,5,8,9,11] 
Bahn 77: 28 Elemente, Repraesentant: [1,4,5,8,11] 
Bahn 78: 14 Elemente, Repraesentant: [1,4,6,8,11] 
Bahn 79: 14 Elemente, Repraesentant: [1,4,7,10,12]

Set 4

n=31

k=5

γ0 = (0, 19, 9, 4, 21, 10, 16, 27, 13, 6, 22, 30, 26, 24, 23, 11, 5, 2, 20, 29, 14, 18, 28, 25, 12, 17, 8, 15, 7, 3, 1)

γ1 = (0, 21, 26, 7, 3)(1, 9, 13, 14, 24)(2, 27, 20, 6, 28)(4, 22, 12, 18, 11)(5, 10, 23, 19, 16)(8, 17, 25, 29, 30)

n: 31
k: 5
Subset size: 169911  
Bahn 1: 155 Elemente, Repraesentant: [0,1,19,20,21]
Bahn 2: 155 Elemente, Repraesentant: [0,2,19,20,21]

...

Bahn 1098: 155 Elemente, Repraesentant: [1,4,7,8,20]
Bahn 1099: 155 Elemente, Repraesentant: [6,7,8,20,22]
Bahn 1100: 155 Elemente, Repraesentant: [2,6,8,20,22]
Bahn 1101: 31 Elemente, Repraesentant: [0,5,8,15,20]

Schreiben Sie einen Kommentar

Ihre E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahren Sie, wie Ihre Kommentardaten verarbeitet werden.

Table of Contents

→ Index