Permutationen...

smartina

Wie komme ich am effektivsten auf alle Kombinationen der Zeichen einer Zeichenkette?

Habe zwar schon:

string line = "123";

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

aber damit lässt sich leider nicht 112, 113, 223, 221, 331, 332, 121, 212 etc. herstellen, also das 1 zeichen so oft in einem string vorkommen kann, wie dieser lang ist.

brauche hilfe! :p

ps.: die gesuchte fkt. soll wirklich effektiv sein, da sonst der pc bestimmt bei 10 zeichen im string abschmiert.

smartina schrieb:

ps.: die gesuchte fkt. soll wirklich effektiv sein, da sonst der pc bestimmt bei 10 zeichen im string abschmiert.

Ich will dich nur mal darauf Hinweisen, dass es mit 10 Zeichen etwa 3628800 Möglichkeiten gibt, diese zu kombinieren. Mit anderen Worten kannst du dann selbst bei einer sehr stark optimierten Funktion eine Tasse Kaffe machen oder ins Schwimmbad gehen... oder um es anders auszudrücken: Eine Funktion, welche alle Permutationen in genügend kurzer Zeit generiert gibt es (noch) nicht. Das ist auch der Grund dafür, dass man Permutationen wenn nur möglich immer aus dem Weg gehen soll.

otze

smartina schrieb:

aber damit lässt sich leider nicht 112, 113, 223, 221, 331, 332, 121, 212 etc. herstellen, also das 1 zeichen so oft in einem string vorkommen kann, wie dieser lang ist.

das ist doch dann keine permutation mehr, oder?

vorallem würden dann die möglichkeiten direkt explodieren, in deinem beispiel währen das schon 27 möglichkeiten!

und bei folgendem 10 zeichen langem string:
"1234567890"
sind das schon 10.000.000.000 möglichkeiten!

also nicht wirklich praktikabel!

life

using namespace std;
void getPermutations(const char* orignalString, const int stringSize, const int startIndex, int* indices)
{
	static int counter = 0;
		cout << ++counter << ": ";
	for(int i = 0; i < stringSize; ++i)
		cout << orignalString[indices[i]];
	cout << endl;	

	for(int i = startIndex; i < stringSize; ++i)
	{
		if(indices[i] + 1 < stringSize)
		{
			indices[i] += 1;
			getPermutations(orignalString,stringSize,i,indices);
			indices[i] -= 1;
		}
	}
}

void findPermutations(string& inputString)
{
	int stringSize = inputString.size();
	int* indices = new int[stringSize];
	for(int i = 0; i < stringSize; ++i)
		indices[i] = 0;
	getPermutations(inputString.c_str(),stringSize,0,indices);
    delete indices;
}

int main()
{
	string line = "abcd"; 
	findPermutations(line);
	return 0;
}

btw. 10 zeichen dauern natürlich ewigkeiten, wenn man alle möglichkeiten ausgeben lassen will :>

otze

naja, irgendwann geht dir eh der stackspeicher für die funktion aus, von daher ist die zeit eher das kleinere problem^^

life

hm bei 9 zeichen funktionierts zumindest noch einwandfrei und das sind ja auch schon ~387Millionen Möglichkeiten...
(bei 10 zeichen war mir die wartezeit zu lang )

die maximale rekursionstiefe (n * (n-1)) ist ja aber auch bei 10 zeichen nur 90, von daher weiß ich nicht warum der stack das Problem sein sollte oO