Permutationen

Hallo,
ich brauche dringend einen Algorithmus, der mir zu einer beliebigen Ziffernfolge alle möglichen Permutationen berechnet! Hat jemand eine Idee??
Schonmal Danke im Voraus!

Gruß
Matthias

CarstenJ

Hallo,

die STL bietet da was:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vcstdlib/html/vcsampsamplenextpermutationstlsample.asp

Da ich mich nicht unbedingt so tief in der C++-Materie befinde, ist das Beispiel aus der MSDN doch etwas kompliziert! Gibt es keinen einfacheren Algorithmus??

hier ein Programm-Auszug:

do
{
	p++;
	cout<<"Person "<<p<<": ";
	cin>>person[p];             //Personen werden eingegeben
}
while(person[p]!="x");          //Eingabestopp mit "x"

for(int b=1;b<p;b++)
{
	int z=0;

    if(person[b]=="a")z=1;      //die Buchstaben "a,b,c,etc."
    if(person[b]=="b")z=2;      //werden durch Zahlen ersetzt!
	if(person[b]=="c")z=3;      
    if(person[b]=="d")z=4;
	if(person[b]=="e")z=5;      
	if(person[b]=="f")z=6;
	if(person[b]=="g")z=7;
	if(person[b]=="h")z=8;
	if(person[b]=="i")z=9;

	cout<<z;                    //Zahlen werden ausgegeben!
}                               //Beispiel: "528196"

Für diese Zahlenfolge müssen jetzt alle möglichen Permutationen berechnet werden! Vielleicht kann mir noch jemand helfen!

(Falls ihr euch fragt, was dieses Programm für einen Sinn hat: Es ist sehr sinnvoll und absolut wichtig! Dieser Auszug ist nur ein Bruchteil des ganzen Programms, ohne diesen Algorithmus komme ich jedoch nicht weiter)

Gruß
Matthias

CarstenJ

Hello again,

Gibt es keinen einfacheren Algorithmus??

Es kommt darauf an:

#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
        string line = "123";

        while(next_permutation(line.begin(), line.end()))
        {
                cout << line << endl;
        }
}

Einfacher geht es nicht. Du kannst dir natürlich auch deinen eigenen Algo schreiben.

Naja das sieht ja schonmal gleich viel übersichtlicher aus!! Ich werds mal probieren! Danke

Matthias

Also, ich krieg hier nen Compilerfehler (VC).

CarstenJ

Hallo,

tja, und welchen? Möglicherweise musst du noch <string> einbinden, das hab ich vergessen.....

Der Algorithmus funktioniert, aber für mein Programm ergibt sich ein kleines Problem:

"string line" arbeitet nur mit Zahlenwerten, wie im Beispiel mit "123"! Diese Zahlen müssen vorher definiert werden!
In meinem Prog werden diese Zahlen aber quasi selbst eingegeben und in der int-Variable "z" gespeichert bzw. ausgegeben(siehe Programm-Auszug oben)! Es muss also eine Möglichkeit geben "string line" mit "z" zu verknüpfen! Gibt es diese Möglichkeit?

string line=z;  //funktioniert nicht

Danke im Voraus!

Gruß
Matthias

Roman1311

Du kannst es mit Stringstreams probieren.

Einzubindende Header:

#include <sstream>

Anschließend wie folgt:

stringstream StrStream;
string line;
int z;

cin >> z;

StrStream << z;
StrStream >> line;

MfG Roman1311

Ich bedanke mich für eure Bemühnungen, aber es hat nicht so ganz funktioniert! Das liegt aber an meinen Programm und nicht an euren Vorschlägen!
Ich habe meinen Quelltext insofern abgeändert, dass jetzt die Zahlenwerte in einem array gespeichert werden! Ich hätte es gleich auf diesem Weg versuchen sollen.

Auszug:

for(int i=0;i<p;i++)
{
    if(person[b]=="a")z[i]=1;
    if(person[b]=="b")z[i]=2;
    if(person[b]=="c")z[i]=3;
    .
    .
    .
    if(person[b]=="n")z[i]=14;

    cout<<z[i]    //mögliche Zahlenfolge in z[i]: 13925
}

Jetzt bleibt nur die Frage wie man aus z[i] alle Permutationen berechnet! Vielleicht hat ja jemand einen fertigen Algo dafür bereit und postet ihn hier!!

Grüße
Matthias