Permutationen

GPC

Dieser Artikel ist eine Leihgabe von www.codeplanet.eu und wurde von StarShaper geschrieben (Original: http://www.codeplanet.eu/modules/tutorials/article.php?storyid=7&page=0). Da ich ihn kenne und ich meine Artikel bei ihm veröffentlicht habe, hat er uns im Gegenzug freundlicherweise seine Artikel zur Verfügung gestellt, damit wir sie hier veröffentlichen können.

-------

Dieses Tutorial stellt ein paar grundlegende C++-Funktionen zur Berechnung von Permutationen vor. Dabei wird unter anderem auch ein Vergleich zwischen den einzelnen Algorithmen illustriert, wie z.B. der aus der STL stammenden next_permutation() und einer rekursiv aufrufenden Funktion.

Einführung

Unter einer Permutation versteht man in der Mathematik die Veränderung der Reihenfolge der Elemente einer Menge. Zum Beispiel kann die Permutation eines bestimmten strings bei der Suche nach einem Passwort, dessen Buchstaben zwar bekannt sind, nicht aber deren Reihenfolge, ganz nützlich sein.

Eine Permutation ist mathematisch gesehen eine bijektive Abbildung einer endlichen Menge mit n Elementen auf sich selbst $f: X \rightarrow X$ . Es handelt sich daher einfach um eine Neuanordnung der Elemente. Als solche ist sie eineindeutig und es existiert somit eine Umkehrfunktion. Das bedeutet nichts anderes, als dass Sie aus der Zielmenge wieder eindeutig auf die Bildmenge schließen können.

Permutationen spielen nicht nur in der reinen Kombinatorik eine wichtige Rolle, sondern finden auch in der Spieleentwicklung Verwendung. Darunter zum Beipiel bei der Matrizenberechnung von geometrischen Figuren.

Permutation ohne Wiederholung

Bei der Permutation ohne Wiederholung müssen folgende Voraussetzungen erfüllt sein:

Alle (N) Elemente der Ausgangsmenge unterscheiden sich voneinander.
Es müssen alle (N) Elemente ausgewählt werden.
Ein Element kann nicht mehrmals ausgewählt werden.

Eine Berechnung erfolgt über die Fakultätsbildung , wobei n stellvertretend für die Anzahl der Elemente steht. Falls Ihnen der Begriff der Fakultät nicht geläufig ist, so können Sie anhand der nachfolgenden Formel ersehen, wie diese gebildet wird.

Nehmen wir als Beispiel die folgende Situation an. Ein Einbrecher benötigt zum Öffnen einer durch ein Kombinationsschloss verriegelten Türe einen Code. Nach gründlicher Spurensuche findet er heraus, dass sich auf dem Schloss nur auf vier Tasten Fingerabdrücke befinden. Nämlich auf Taste 3, 4, 5 und 8. Außerdem weiß er, dass beim Codeschloss mit der Seriennummer 25F7-ST66 ein 4-stelliger Zugangscode in der richtigen Reihenfolge eingegeben werden muss. Die Frage lautet nun, wie viele Kombinationen muss unser Einbrecher durchgehen, um das Schloss zu knacken und welche sind das?

Wie bereits oben erläutert, errechnet sich die Anzahl der möglichen Kombinationen aus der Fakultät. Somit ergeben sich für vier unterschiedliche Elemente aus der Menge P insgesamt 24 Permutationen. Nachfolgend sind diese vollständig gelistet: 3458, 3485, 3548, 3584, 3845, 3854, 4358, 4385, 4538, 4583, 4835, 4853, 5348, 5384, 5438, 5483, 5834, 5843, 8345, 8354, 8435, 8453, 8534, 8543.

Nun ist das Ganze für vier Zahlen (Elemente) noch sehr überschaubar und die 24 verschiedenen Permutationen lassen sich problemlos in kurzer Zeit durchdenken. Doch aufgrund des Wachstumsverhaltens von n! steigt die Anzahl an möglichen Permutationen ab 5 Elementen sehr stark an und erreicht bereits für n=69 eine Zahl mit unglaublichen 99 Dezimalstellen! Deshalb wäre es gut, ein Programm zu haben, welches uns die Aufgabe der Berechnung abnimmt. Die C++-Standard-Bibliothek mit ihren mächtigen Algorithmen stellt uns hierfür die Funktionen prev_permutation und next_permutation zur Verfügung. Diese sind in der STD-Header-Datei algorithm versammelt. Der Algorithmus prev_permutation generiert für den Bereich [first, last] alle vorhergehenden Permutation der Elemente, während next_permutation dies für alle nachfolgenden macht.

Geordnete Elemente

Beachten Sie, dass der STL-Algorithmus davon ausgeht, dass alle Elemente lexikographisch geordnet vorliegen! Existiert eine vor-/nachfolgende Permutation wird true zurückgegeben. Das untere Programm erzeugt für die Buchstaben A, B und C insgesamt sechs Permutationen.

// Calculate Permutations - using STL Algorithms
#include <iostream>
#include <algorithm>

int main()
{
    char f[] = { 'A', 'B', 'C' }, *const fn = f + sizeof(f) / sizeof(*f);
    unsigned int i = 0;

    do
    {
        std::cout << ++i << ". Permutation: ";
        copy(f, fn, std::ostream_iterator<char>(std::cout, " "));
        std::cout << std::endl;
    }
    while(std::next_permutation(f, fn));

    return 0;
}

Der Algorithmus aus der STL generiert alle nachfolgenden Permutationen für die Elemente A, B, und C, die in Frage kommen und gibt diese auf den Bildschirm aus.

Ungeordnete Elemente

Wie lässt sich der Algorithmus nun auch bei lexikographisch ungeordneten Wörtern (Elementen), wie z.B. monkey verwenden? Vielleicht können Sie es sich schon denken!? Wir müssen den string einfach nur ordnen lassen bevor wir diesen an die STL-Funktion übergeben.

Wir benutzen dafür die STL-Funktion stable_sort(). Im Durchschnitt ist die auf Qicksort basierende sort()-Funktion zwar etwas schneller, kann aber unter Umständen das Laufzeitverhalten des Programms negativ beeinflussen. Werfen wir nun einmal einen Blick auf die veränderte Funktion mit dem neuen Namen SSTL_Permutation:

// ============================================================================
// Function:    SSTL_Permutation
// Description: Generate all permuted strings for an input string using
//              original STL function next_permutation().
// Parameter:   @input: the input string.
// Return:      A vector of all permuted strings.
// Note:        STL next_permutation permutes the string input to the 
//              lexicographically next string as an arrangement, and then 
//              returns true. Due to this reason, the STL function stable_sort
//              is called before.
// ============================================================================
vector<string> SSTL_Permutation(const char *input)
{
    vector<string> result;
    string cs = input;

    stable_sort(cs.begin(), cs.end());  

    do   
        result.insert(result.end(), cs);
    while(next_permutation(cs.begin(), cs.end())); 

    return result;
}

Wir haben der Funktion einen Container (vector) vom Typ string spendiert. Dieser Container soll unsere generierten Permutationen aufnehmen und verwalten. Die do while() Schleife erzeugt alle Permutationen und fügt diese in den vector ein. Nun werden auch lexikographisch unsortierte strings korrekt verarbeitet.

Eine weitere Möglichkeit, dieses Ziel zu erreichen, besteht darin die Standard-STL-Funktion next_permutation neu zu implementieren, so dass diese auch mit unsortierten strings umgehen kann. Sehen Sie sich dazu einfach mal die folgende Implementierung samt der aufrufenden Funktion ISTL_Permutation an.

// ============================================================================
// File:        STLPermutation.cpp 
// Description: Implementation of standard STL function next_permutation
// ============================================================================
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// generate associative container pair key
typedef map<char, int> POSITION_MAP;

// STL: Extended TEMPLATE FUNCTION _next_permutation from algorithm standard header
// permute and test for pure ascending, using operator<
template<class _BidIt> inline
bool _next_permutation(_BidIt _First, _BidIt _Last, POSITION_MAP *pMap/*default=NULL*/)
{   
   _BidIt _Next = _Last;
   if (_First ==_Last || _First == --_Next) return (false);

   for (; ; )
   {   
      _BidIt _Next1 = _Next;
      if (pMap? (*pMap)[*--_Next] < (*pMap)[*_Next1]: 
                *--_Next < *_Next1)      
      {   
         _BidIt _Mid = _Last;
         for (; !(pMap? (*pMap)[*_Next] < (*pMap)[*--_Mid]: 
                        *_Next < *--_Mid);); 

         std::iter_swap(_Next, _Mid);
         std::reverse(_Next1, _Last);   
         return (true);
      }

      if (_Next == _First)
      {   
         std::reverse(_First, _Last);
         return (false);
      }
   }
}

// ============================================================================
// Function:    ISTL_Permutation
// Description: Generate all permuted strings for an input string using
//              extended STL function _next_permutation().
// Parameter:   @input: the input string.
//              @bOrdered: flag to set optionally ordering On/Off.
// Return:      A vector of all permuted strings.
// Note:        STL next_permutation permutes the string input to the 
//              lexicographically next string as an arrangement, and then 
//              returns true. If the string is in descending order then 
//              it returns false.
// ============================================================================
vector<string> ISTL_Permutation(const char *input, bool bOrdered/*default=true*/)
{
    POSITION_MAP mapPos;
    vector<string> result;
    string cs = input;

    if(!bOrdered)
        for(unsigned int i=0; i<cs.length(); i++)
            mapPos.insert(pair<char, unsigned int>(cs[i], i));   

    do   
        result.insert(result.end(), cs);   
    while (_next_permutation(cs.begin(), cs.end(), bOrdered ? NULL : &mapPos)); 

    return result;
}

Sicherlich erscheint Ihnen diese Lösung etwas umständlicher und ineffizienter. Aber sie ist performancetechnisch der oberen Funktion ungefähr gleichzusetzen. Bis auf die Tatsache, dass sie aufgrund der Neuimplementierung von next_permutation etwas länger ausfällt. Wie Sie nun wahrscheinlich schon erkannt haben, nennen wir diese neue Funktion _next_permutation. Es handelt sich im Prinzip um den originalen STL Algorithmus der lediglich ein klein wenig modifiziert wurde. Die Funktion ISTL_Permutation() nimmt insgesamt zwei Parameter auf. Zum einen den input string und zum anderen das Flag bOrdered, welches es der Funktion ermöglichen soll auch lexikographisch ungeordnete strings in allen Kombinationen auszugeben.

Im Default-Modus ist das Flag true und die Template-Funktion _next_permutation verhält sich wie die Standard-Implementierung aus der STL. Wird allerdings explizit false übergeben, generiert die Funktion auch für unsortierte input strings alle Permutationen.

Dazu wird der Code um einen assoziativen Container der Klasse map erweitert. Die Klasse map verwaltet Paare von Schlüsseln und Werten. Mit Hilfe des Schlüssels kann dann eindeutig auf den zugeordneten Wert zugegriffen werden. Der mit typedef vereinbarte Name vereinfacht die spätere Benutzung, ähnlich wie Sie es z.B. sicherlich schon von C-Structs her kennen. Sobald das Flag bOrdered false ist (string ist also unsortiert), wird die if() Bedingung ausgeführt und ein Schlüsselpaar, ein sogenanntes pair-key, bestehend aus einem char und einem unsigned int angelegt und in das map-Objekt eingefügt. Im char wird der Buchstabe und im unsigned int dessen Position im string gespeichert. Dieses Paar wird anschließend an _next_permutation() übergeben. Dort führt (*pMap)[*i]<(*pMap)[*j] einen Sortierungsvergleich aus und liefert alle Permutationen zurück. Fertig ist die erweiterte STL-Funktion.

Permutation mit Wiederholung

Bisher haben wir nur Fälle kennengelernt, in welchen die vorliegenden Elemente im string sich nicht wiederholt haben. Zum Beispiel ABC oder 3458 oder monkey. Allerdings kann es auch sein, dass der string mehrere Elemente gleicher Art beinhaltet. ABBA ist ein Beispiel dafür. Folgende Voraussetzungen gelten für Permutationen mit Wiederholungen.

Mindestens 2 Elemente der Ausgangsmenge sind identisch, d.h. die Elemente der Ausgangsmenge unterscheiden sich nicht alle voneinander.
Es müssen alle (N) Elemente ausgewählt werden.
Ein Individualelement kann nicht mehrmals ausgewählt werden, ein Element mit gleicher Eigenschaft hingegen schon. Liegen z.B. 2 rote Kugeln in der Ausgangsmenge, so muss jede der beiden roten Kugeln ausgewählt werden (Wiederholung), eine dritte rote Kugel kann aber nicht ausgewählt werden.

Berechnet wird die Anzahl an möglichen Permutationen über die Formel:

Der zusätzlich hinzugekommene Faktor k stellt die Anzahl der Wiederholungen eines Elementes dar. Auch hier gilt .

So existieren beim string ABBA insgesamt 6 Permuationen. Nämlich diese: AABB, ABAB, ABBA, BAAB, BABA, BBAA. Die bisher beschriebenen iterativen Funktionen reagieren unterschiedlich auf diese neue Situation. Während die Funktion SSTL_Permutation alle Permutationen korrekt berechnet, überspringt die ISTL_Permutation Implementierung 2 Permutationen und gibt nur die strings ABBA, BAAB, BABA, BBAA zurück. Hier sollte man also genau differenzieren.

Permutation mit Hilfe von Rekursion

Ein relativ oft gegangener Weg, Permutationen zu errechnen, ist der über die Rekursion. Der Grund hierfür liegt in der Eigenschaft der Fakultät, welche sich hierfür geradezu anbietet. Obwohl die iterative STL-Lösung in der Performance deutlich besser als die rekursive Lösung abschneidet, wollen wir auch diese hier auflisten.

// ============================================================================
// Function:    REC_Permutation
// Description: Generate all permuted strings for an input string
//              using Recursion
// Parameter:   @input: the input string.
//              @bRepeated: flag to allow optionally element repeat.
// Return:      A vector of all permuted strings.
// ============================================================================
vector<string> REC_Permutation(const char* input, bool bRepeated)
{
    vector<string> result, v1;
    string s1;    
    char ch;
    size_t nLen = strlen(input);      

    if(nLen==1)            // Base case: Add one-char string
        result.insert(result.end(), input);      
    else                    // nLen > 1, need recursion
    {
        for(size_t i=0; i<nLen; i++)
        {
            ch = input[i];       // Extract each char as the first

            // To exclude repeated element
            if (!bRepeated)
            {
                size_t j;

                for (j=0; j<i; j++)
                    if(ch==input[j]) 
                        break;

                if (j<i) continue;   // If i==j, Not a repeated one
            }

            s1 = input;           // Copy the original string
            s1.erase(i, 1);    // Put the rest string into s1

            v1 = REC_Permutation(s1.c_str(), bRepeated); // Recursive 

            for(std::size_type i=0; i < v1.size(); i++)
            {
                s1 = ch + v1[i];   
                result.insert(result.end(), s1);   
            }
        }
    }
    return result;
}

Die rekursive Lösung verhält sich exakt wie die Funktion SSTL_Permutation wenn das Flag bRepeated false ist. Ist es allerdings auf true gesetzt erzeugt die Funktion REC_Permutation immer alle Permutationen, unabhängig davon ob sich vereinzelte strings wiederholen oder nicht.

Weitere Algorithmen

Neben den bisher gezeigten Algorithmen gibt es noch einen weiteren nennenswerten, von Phillip P. Fuchs geschriebenen, Algorithmus welcher in der Geschwindigkeit und Effizienz mit dem aus der STL gleichzieht und sogar unter gewissen Umständen besser abschneidet.

vector<string> PHIL_Permutation(const char* input)
{
    char a[32];
    strcpy(a, input);
    int N = strlen(a);		// constant index ceiling (a[N] length)
    int ax = N - 1;			// constant index ceiling (a[N] length)
    int *p = new int[N+1];  // target array and index control array
    int i, j, tmp;			// index variables and tmp for swap

    for(i = 0; i < N+1; i++)	// p[N] > 0 controls iteration and the index boundary for i
    p[i] = i;

    vector<string> result;
    result.insert(result.end(), a);      

    i = 1;   // setup first swap points to be ax-1 and ax respectively (i & j)
    while(i < N)
    {
        p[i]--;                // decrease index "weight" for i by one
        j = ax - i % 2 * p[i]; // IF i is odd then j = ax - p[i] otherwise j = ax
        i = ax - i;            // adjust i to permute tail (i < j)

        // set Scope
        {
            tmp = a[j];		// swap(a[i], a[j])
            a[j] = a[i];
            a[i] = tmp;
            result.insert(result.end(), a);      
        }

        i = 1;                 // reset index i to 1 (assumed)
        while (!p[i])          // while (p[i] == 0)
        {
            p[i] = i;           // reset p[i] zero value
            i++;                // set new index value for i (increase by one)
        } 
    } 

    delete [] p;
    return result;
}

Benchmark

Um die unterschiedlichen Algorithmen in ihrer Performance und Effizienz testen zu können, habe ich neben den verschiedenen Algorithmen einen Test zum Benchmarken eingebaut. Hier lässt sich deutlich der Unterschied zwischen den unterschiedlichen Algorithmen erkennen. Während die rekursive Methode generell deutlich schlechter als die anderen abschneidet, ist die Methode "STL with SORT" am schnellsten, da die Methode "Implemented STL, Ordered" eben nicht alle Permutationen berechnet. Der Algorithmus von Phillip Fuchs schneidet bei Wiederholungen geringfügig schlechter ab als die STL-Lösung. Dies liegt an der Art der Berechnung. Der Algorithmus von Phillip Fuchs geht nämlich auch bei Wiederholungen alle Permutationen durch. Liegt keine Wiederholung vor, schneidet dieser Algorithmus oft sogar besser als die STL-Lösung ab.

Der nachfolgende Test wurde auf einem P4 mit 2,56GHz und 1024MB RAM durchgeführt.

Das war's! Sie finden das Programm samt Quellcode mit den implementierten Algorithmen weiter unten als Visual Studio 2003.NET gepacktes Projekt vor. Die Permutationen werden in einer Textdatei gespeichert und bis zu einer Stringlänge von 5 auch visuell ausgegeben :p .

Permutationen.zip

Cooler Artikel. Endlich mal wieder was zum lesen

Wir benutzen dafür die STL-Funktion stable_sort(). Im Durchschnitt ist die auf Qicksort basierende sort()-Funktion zwar etwas schneller, kann aber unter Umständen das Laufzeitverhalten des Programms negativ beeinflussen.

sort ist im Durchschnitt schneller, wie kann es dann das Laufzeitverhalten negativer beeinflussen als stable_sort?

Jester

sort verwendet intern ein modifiziertes Quicksort. Das kann im Extremfall zu quadratischer Laufzeit führen (auch wenn sich einige Implementierungen versuchen dagegen zu schützen). stable_sort verwendet was anderes, vermutlich ein merge_sort oder ähnliches, was sich leicht stabil implementieren lässt. merge_sort hat immer nur eine Laufzeit von n*log(n). Vermutlich soll das die Begründung sein.

Ich muß aber zugeben, dass mich das auch nicht wirklich überzeugt. Ich würde einfach std::sort verwenden. In allen praktischen Fällen dürfte man damit schneller sein.

Ben04

Die Permutationen einer ungrordneten Sequenz lassen sich auch ganz leicht mit std::next_permutation ohne sort realisieren:

vector<string> SSTL_Permutation(const char *input)
{
    vector<string> result;
    string str = input, start = str;

    do{
        result.push_back(str);
        next_permutation(str.begin(), str.end());
    }while(str != start);

    return result;
}

Aber da es n! Permutationen gibt ist die Laufzeit mindestens O(n!) da fällt das O(n*log(n)) gar nicht mehr ins Gewicht und daher wird hier am falschen Ende optimiert.

result.insert(result.end(), cs);

Wieso nicht einfach push_back?

Im Default-Modus ist das Flag true und die Template-Funktion _next_permutation verhält sich wie die Standard-Implementierung aus der STL. Wird allerdings explizit false übergeben, generiert die Funktion auch für unsortierte input strings alle Permutationen.

das tut next_permutation doch auch.

C++98 25.3.9 schrieb:

Takes a sequence defined by the range [first, last) and transforms it into the next permutation.
The next permutation is found by assuming that the set of all permutations is lexicographically sorted with respect to operator< or comp. If such a permutation exists, it returns true. Otherwise, it transforms the sequence into the smallest permutation, that is, the ascendingly sorted one, and returns false.

Beim multinomial Coeffizient wäre es nicht schlecht ausdrücklich anzugeben, dass es sich um verschiedene ks handelt und dies durch k_1, k_2, ... k_n deutlich zu machen.

Eine Text Beschreibung wie man next_permutation und Phillip P. Fuchs' Algorithmus implementieren kann wäre interessant gewesen.

Hallo habe folgendes Problem: Ich have ein array mit n Elementen somit habe ich 2^n-1 ergebnisse die in einem bsp so ausshene:

string array={"a","b","c"}

ausgabe:(sollte so sein)
a
b
c
ab
ac
bc
abc

2^n-1=23-1=7 OK

Jedoch wie berechne ich das

Neues bsp:

string array={"a","b","c","2"}

ausgabe:(sollte so sein)
a
b
c
2
ab
ac
a2
bc
b2
.
.
.
abc2

2^n-1=22-1=15 OK

Bitte um Code oder Hilfe!!!

Am besten iterativ lösen!!

Mfg Peter

#include <stdio.h>

void inc (int *a, int max)
{
   (*a)++;
   if (*a == max)
   {
      *a=0;
      inc (a+1, max);
   }
}

void show (int *a, char *str)
{
   if (*a != -1)
   {	
      show (a+1, str);
      putchar (str[*a]);
   }
}

void main (void)
{
   char *str = "abc";
   int out[256];
   memset (out, 0xff, sizeof(out));
   for (;;)
   {
      inc (out, sizeof(str)-1);
      show (out, str);
      printf ("\n");
   }
}

spacerat

std::string default = "12345";

int perm=1, digits=default.size();
for (int i=1;i<=digits;perm*=i++);
for (int a=0;a<perm;a++)
{
	std::string avail=default;
	for (int b=digits,div=perm;b>0; b--) 
	{
		div/=b;
		int index = (a/div)%b;
		printf("%c", avail[index] );
		//avail[index]=avail[b-1]; // fast but not lexigraphic order
		avail.erase(index,1) ; // lexigraphic correct order
	}
	printf("\n");
}
printf("permutations:%d\n",perm);

Fast, non-recursive & simple

(c) Sven Forstmann

knivil

Link zu Permutation.zip ist tot.

-- perm.hs
import Data.List

main :: IO ()
main = do line <- getLine
          putStrLn $ show $ length $ permutations line

> ghci perm.hs -O3
> time echo "ABCDJAFGIH" | ./a.out
3628800

real    0m0.383s
user    0m0.352s
sys     0m0.009s

Das Testsystem war ein Pentium 4 mit 2.8 GHz. Wie vergleichbar diese Werte mit der C/C++ Variante sind, ist wegen Haskells Laziness nicht zu sagen.

knivil schrieb:

Link zu Permutation.zip ist tot.

-> Ich wiederhole: Link zu Permutation.zip ist tot.
Over&Out

GPC

Ich schau mal was ich tun kann...

GPC

Permutationen.zip ist wieder verfügbar.

Kurze (eher nebensächliche) Frage:
Ist das Beispiel mit dem Zahlencode und den Fingerabdrücken nicht ein wenig scheiße? Wenn die vier Tasten bekannt sind, könnte sich eine Taste ja durchaus wiederholen, dann ist die Berechnung der kombinatorischen Möglichkeiten eben keine Fakultät.

SeppJ

LOLAlter schrieb:

Kurze (eher nebensächliche) Frage:
Ist das Beispiel mit dem Zahlencode und den Fingerabdrücken nicht ein wenig scheiße? Wenn die vier Tasten bekannt sind, könnte sich eine Taste ja durchaus wiederholen, dann ist die Berechnung der kombinatorischen Möglichkeiten eben keine Fakultät.

Wie willst du denn aus vier verschiedenen Ziffern eine vierstellige Folge generieren, bei der es Wiederholungen gibt?

MichelRT

SeppJ schrieb:

Wie willst du denn aus vier verschiedenen Ziffern eine vierstellige Folge generieren, bei der es Wiederholungen gibt?

Wahrscheinlich fährt er Toyota

xeroe

Erstmal vielen Dank für den super Beitrag an den Threadersteller.

Ich hätte jedoch eine kleine Frage zu dem STL Algorithmus und zwar möchte ich gerne das ergebnis in ein Array übergeben anstatt es mit cout in die Console zu schreiben.
Das ganze findet ja in folgender Zeile statt:

copy(f, fn, std::ostream_iterator<char>(std::cout, " "));

Ich bin jedoch mit den verwendeten Befehlen nicht vertraut, von daher wäre es schön wenn mir jemand hierbei behilflich sein könnte

Es ist immer besser, wenn du noch konkret beschreibst was du vor hast.

Folgendes schreibt es in einen std::vector und gibt diesen std::vector danach aus:

do
    {
		std::vector<char> v(f, fn);

        std::cout << ++i << ". Permutation: ";

		std::copy(v.begin(), v.end(), std::ostream_iterator<char>(std::cout, " "));

        std::cout << std::endl;
    }
    while(std::next_permutation(f, fn));