kramann.info

10.2 Alle Permutationen

Hier geht es darum, welche Möglichkeiten es gibt N verschiedene Elemente anzuordnen. Wenn ich einen Apfel, eine Birne und eine Pflaume vor mir habe, gibt es beispielsweise sechs Anordnungen:

abp,bap,apb,bpa,pab,pba

Wie berechnet man, wieviele Anordnungen es für N Elemente gibt?

Lege ich in einem Gedankenexperiment alle N neben mich und suche eines aus, so habe ich dafür N Möglichkeiten. Dieses soll die erste Position einnehmen.

Für das zweite habe ich dann noch N-1 Auswahlmöglichkeiten usw., bis schliesslich das letzte Element übrigbleibt, dass dann als letztes angeordnet wird.

Also ergeben sich für N Dinge N*(N-1)*(N-2)*...*1 Möglichkeiten sie anzuordnen, also N!, sprich "N Fakultät".

Das folgende Programm erzeugt alle Permutationen für beliebige N. Es ist eine Weiterentwicklung des vorangegangenen Kombinationsprogramms mit folgenden Ergänzungen im Algorithmus:

Nach jeder Auswahl wird die Zahlenbasis die bei der Modulo-Division auftaucht um eins reduziert
Es wird gemerkt, welche Plätze mit Elementen belegt sind, die bislang nicht ausgewählt wurden. Nur die werden beim Abzählen der folgenden Auswahlmöglichkeiten berücksichtigt.


#include <iostream>
#include <vector>
#include "vektordef.h"
#include "hilfsmethoden.h"

using namespace std;

long holeAnzahlAllePermutationen(int elementanzahl)
{
    long anzperm = 1;
    long noch_uebrig = (long)elementanzahl;

    for(int i=0;i<elementanzahl;i++)
    {
        anzperm*=noch_uebrig;
        noch_uebrig--;
    }

    return anzperm;
}

void holeItePermutation(int* kombi,long i,int elementanzahl)
{
    long noch_uebrig = (long)elementanzahl;
    bool* warschon = new bool[elementanzahl];
    int  index;

    for(int k=0;k<elementanzahl;k++)
        warschon[k] = false;

    for(int k=0;k<elementanzahl;k++)
    {
        index = i%noch_uebrig;
        i/=noch_uebrig;
        noch_uebrig--;

        int q=0;        
        for(int p=0;p<elementanzahl;p++)
        {            
            if(warschon[p]==false)
                q++;
            if(warschon[p]==false && q-1==index)
            {
                kombi[p] = k;
                warschon[p]=true;
                break;
            }                
        }
    }
}


int main(void)
{    
    cout<<"Das Programm bestimmt alle moeglichen Anordnungen der Wortfolge, die Sie eingeben"<<endl;
    cout<<"Geben Sie eine durch Leerzeichen getrennte Wortfolge ein:"<<endl;

    char puffer[1000];

    cin.getline(puffer,1000);

    string text = wandelCharInString(puffer);

    Stringvektor wort = splitText(text,' ');

    int anzahl = wort.size();

    long moeglich = holeAnzahlAllePermutationen(anzahl);    

    cout<<"Es gibt folgende "<<moeglich<<" Besetzungsmoeglichkeiten fuer den Zug:"<<endl<<endl;

    int* kombi = new int[anzahl];

    for(long i=0;i<moeglich;i++)
    {
        holeItePermutation(kombi,i,anzahl);
        cout<<" Kombination Nr."<<(i+1)<<":   ";
        for(int k=0;k<anzahl;k++)
            cout<<wort.at(kombi[k])<<" ";
        cout<<endl;
    }    
}

Code 10.2-1: C++ Programm "allepermutationen.cpp"

Programm permutation, .cpp, .h und .exe - Dateien gepackt