Hypercell ein ] Hypercell aus ] Zeige Navigation ] Verstecke Navigation ]
c++.net  
   

Die mobilen Seiten von c++.net:
https://m.c-plusplus.net

  
C++ Forum :: Die Artikel ::  Permutationen  
Gehen Sie zu Seite 1, 2  Weiter
  Zeige alle Beiträge auf einer Seite
Auf Beitrag antworten
Autor Nachricht
GPC
Global Moderator

Benutzerprofil
Anmeldungsdatum: 11.07.2004
Beiträge: 7433
Beitrag GPC Global Moderator 08:35:28 10.04.2007   Titel:   Permutationen            Zitieren

Dieser Artikel ist eine Leihgabe von www.codeplanet.eu und wurde von StarShaper geschrieben (Original: http://www.codeplanet.eu/ ....... .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.

C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 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:

C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// ============================================================================
// 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.

C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// ============================================================================
// 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.

C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// ============================================================================
// 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.

C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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


Zuletzt bearbeitet von GPC am 19:24:26 06.07.2010, insgesamt 8-mal bearbeitet
Unregistrierter





Beitrag Unregistrierter 20:39:09 11.04.2007   Titel:              Zitieren

:live: Cooler Artikel. Endlich mal wieder was zum lesen :)
Christoph@work
Unregistrierter




Beitrag Christoph@work Unregistrierter 14:21:49 30.04.2007   Titel:   Re: Permutationen            Zitieren

Zitat:
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
Moderator

Benutzerprofil
Anmeldungsdatum: 06.04.2001
Beiträge: 9103
Beitrag Jester Moderator 16:16:28 30.04.2007   Titel:              Zitieren

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.

_________________
Mod im Mathe-Forum

Die dümmsten Programmierer schreiben die dicksten Programme.
Ben04
Autor

Benutzerprofil
Anmeldungsdatum: 10.10.2004
Beiträge: 1635
Beitrag Ben04 Autor 20:41:11 30.04.2007   Titel:              Zitieren

Die Permutationen einer ungrordneten Sequenz lassen sich auch ganz leicht mit std::next_permutation ohne sort realisieren:
C++:
1
2
3
4
5
6
7
8
9
10
11
12
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.

C++:
result.insert(result.end(), cs);

Wieso nicht einfach push_back?

Zitat:
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.
King2
Unregistrierter




Beitrag King2 Unregistrierter 17:56:25 06.12.2007   Titel:              Zitieren

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=2^3-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=2^2-1=15 OK


Bitte um Code oder Hilfe!!!

Am besten iterativ lösen!!

Mfg Peter
Winkelspinne
Unregistrierter




Beitrag Winkelspinne Unregistrierter 18:40:36 08.12.2007   Titel:              Zitieren

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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
Mitglied

Benutzerprofil
Anmeldungsdatum: 08.04.2010
Beiträge: 1
Beitrag spacerat Mitglied 09:41:21 08.04.2010   Titel:   All Permutations - non-recursive            Zitieren

C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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


Zuletzt bearbeitet von spacerat am 10:16:51 08.04.2010, insgesamt 3-mal bearbeitet
knivil
Mitglied

Benutzerprofil
Anmeldungsdatum: 11.02.2009
Beiträge: 7325
Beitrag knivil Mitglied 09:48:47 08.04.2010   Titel:              Zitieren

Link zu Permutation.zip ist tot.

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
-- 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.

_________________
If it were not for laughter, there would be no Tao.
Sie können einen Beitrag nicht so schnell nach Ihrem letzten absenden, bitte warten Sie einen Augenblick.


Zuletzt bearbeitet von knivil am 10:15:17 08.04.2010, insgesamt 1-mal bearbeitet
Houston
Unregistrierter




Beitrag Houston Unregistrierter 21:12:44 27.06.2010   Titel:              Zitieren

knivil schrieb:
Link zu Permutation.zip ist tot.


-> Ich wiederhole: Link zu Permutation.zip ist tot.
Over&Out
C++ Forum :: Die Artikel ::  Permutationen  
Gehen Sie zu Seite 1, 2  Weiter
Auf Beitrag antworten

Zeige alle Beiträge auf einer Seite




Nächstes Thema anzeigen
Vorheriges Thema anzeigen
Sie können keine Beiträge in dieses Forum schreiben.
Sie können auf Beiträge in diesem Forum antworten.
Sie können Ihre Beiträge in diesem Forum nicht bearbeiten.
Sie können Ihre Beiträge in diesem Forum nicht löschen.
Sie können an Umfragen in diesem Forum nicht mitmachen.

Powered by phpBB © 2001, 2002 phpBB Group :: FI Theme

c++.net ist Teilnehmer des Partnerprogramms von Amazon Europe S.à.r.l. und Partner des Werbeprogramms, das zur Bereitstellung eines Mediums für Websites konzipiert wurde, mittels dessen durch die Platzierung von Werbeanzeigen und Links zu amazon.de Werbekostenerstattung verdient werden kann.

Die Vervielfältigung der auf den Seiten www.c-plusplus.de, www.c-plusplus.info und www.c-plusplus.net enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt (vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden. Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.