Binäre Orthonormalmatrix



  • Hallo

    Ich versuche eine Matrix in C++ zu programmieren, mit L Zeilen und N Spalten. Die Koeffizienten sollen nur 0 oder 1 sein und random gewählt werden mit folgender Einschränkung:

    Die L Zeilenvektoren sollen alle orthonormal zueinander stehen. Dies ist nur möglich, wenn keine zwei Einser in den Spalten untereinander stehen. Ferner dürfen in keiner Zeile mehr als eine Eins stehen, sonst wäre die Länge nicht mehr Eins.

    Zum Beispiel sowas:

    0000001
    1000000
    0000010

    Ich bin bis jetzt soweit gekommen, dass ich ein Array von 0 bis N-1 random geshuffelt habe und eine mit Nullen gefüllte Matrix, welche die orthonormalen Zeilenvektoren enthalten soll, initialisiert habe.

    Nun würde ich gerne die Zeilen dieser Matrix mit einer for Schleife ablaufen und in jeder Zeile demjenigen Spaltenkoeffizient den Inhalt 1 zuweisen, welcher der Inhalt des Spaltenkoeffizient des geshuffelten Vektors ist.

    Also konkret wenn z.B. der geshuffelte Vektor beginnt mit (3, 5,....) bei der Matrix in der ersten Zeile in der dritten Spalte eine 1 steht und in der zweiten Zeile in der 5. Spalte eine 1 ist usw...

    Mein Code bis jetzt sieht wie folgt aus:

    #include <iostream> 
    #include <stdlib.h>
    #include <vector>
    #include <iterator>
    #include <stdlib.h>
    #include <algorithm>
    
    #define N 30      //Anzahl der Spalten
    #define L 4       //Anzahl der Zeilen
    
    using namespace std;
    //=============================================
    //Fisher-Yates-Shuffle-Algorithmus
    void FisherYates(std::vector<int>& vec)
    {
        int n = vec.size();
        for (int i = n - 1; i > 0; --i)
        {
            std::swap(vec[i], vec[rand() % (i + 1)]);
        }
    }
    //=============================================
    int main () {                                      
    int ik,il;
    
    //Erstelle Array Sequenz 0,1,2,3,...,N-1
    int Sequenz[N];
    for(il=0; il<N; il++){Sequenz[il]=il;}
    
    //Berechnet aus Array Sequenz den Vektor sequenz
    vector<int> sequenz;
    sequenz.insert( sequenz.begin() , Sequenz , Sequenz + N ) ; 
    
    //Wendet Fisher-Yates Algorithmus zum shuffeln an
    FisherYates(sequenz);
    
    //Ausgabe des geshuffelten Vektors (Kopie des Ausgabestreams aus der STL)
    std::copy(sequenz.begin(), sequenz.end(), std::ostream_iterator<int>(std::cout, " "));
    
    cout << endl;
    
    //Erstellt (L x N) Matrix muster mit Vektoren 
    vector< vector<int> > muster( L,vector<int>(N) );
    
    //Setzen der zueinander orthonormalen Zeilenvektoren
    
    for(ik=0 ; ik<L; ik++)
    {
        for(il=0; il<N; il++)
        {                 
    
        //To DO: Was steht hier drinnen?
    
        }
    
    cout << "\n";
    }
    
    //Ausgabe der zueinander orthonormalen Zeilenvektoren
    for(ik=0; ik<L; ik++)
    {
        for(il=0; il<N; il++)
        {
        cout << muster[ik][il];
        }
    cout << "\n";
    }
    
    //=============================================
    return 0;                                                                                             
    }
    //=============================================
    

    Ich habe im Code 'To DO' einkommentiert. Ich denke da muss jetzt die Ersetzung der 1-er in den jeweiligen Spaltenindizes hinein aber ich weiss nicht wie es geht.

    Ich habe mit replace, if_replace und swap etwas herum gespielt aber das war nicht zielführend. Würde mir bitte jemand Helfen wie ich hier nun weiter gehe?

    Danke für die Hilfe und Grüße



  • Ich konnte das Problem selbst lösen. Verzeihung für den Doppelpost.

    Hier mein fertiges Programm falls jemand wissen möchte was ich getan habe:

    //Programm berechnet L zufällige, binäre, paarweise orthonormale Zeilenvektoren der Länge N
    #include <iostream> 
    #include <stdlib.h>
    #include <vector>
    #include <iterator>
    #include <stdlib.h>
    #include <algorithm>
    
    #define N 5      //Anzahl der Spalten
    #define L 3       //Anzahl der Zeilen
    
    using namespace std;
    //=============================================
    //Fisher-Yates-Shuffle-Algorithmus
    void FisherYates(std::vector<int>& vec)
    {
        int n = vec.size();
        for (int i = n - 1; i > 0; --i)
        {
            std::swap(vec[i], vec[rand() % (i + 1)]);
        }
    }
    //=============================================
    int main () {                                      
    int ik,il;
    
    int Sequenz[N];
    for(il=0; il<N; il++){Sequenz[il]=il;}
    
    vector<int> sequenz;
    sequenz.insert( sequenz.begin() , Sequenz , Sequenz + N ) ; 
    
    FisherYates(sequenz);
    
    vector< vector<int> > muster( L,vector<int>(N) );
    
    //Setze orthonormale Zeilenvektoren
    il=0;
    for(ik=0; ik<L; ik++)
    {
    
       muster[ik][sequenz[il]]=1;          
       il++;
    }  
    
    //Ausgabe der zueinander orthonormalen Zeilenvektoren
    for(ik=0; ik<L; ik++)
    {
        for(il=0; il<N; il++)
        {
        cout << " " << muster[ik][il];
        }
    cout << "\n";
    }
    
    //cout << "\n";
    //for(int il : sequenz){cout << sequenz[il] << " ";}
    
    //=============================================
    return 0;                                                                                             
    }
    //=============================================
    


  • Ich würds einfach mit ner bool Tabelle machen:
    L Einträge, für die L Spalten.
    Zufallszahl z0 zwischen 0 und L-1 würfeln,
    in der 1. Spalte an dieser Pos ne 1 setzen.
    Dann in der Tabelle die Position als verwendet markieren.
    In der nächsten Runde ne Zufallszahl z1 zw. 0 und L-2 würfeln, weil ja
    nur noch L-1 Positionen für die 1 belegt werden können.
    Die Zahl z1 kann man als Index in die Tabelle verwenden, wobei natürlich die belegten Einträge zu überspringen sind.
    Usw. bis man alle N<=L Zeilen gefüllt hat.


Log in to reply