Permutation

[Lord Calf]

Guten Tag,

ich habe hiermal eine doch recht einfache und nicht gute laufzeit fähige Version eines Permutationsalgorithmus für ein 7 buchstabiges Wort.
Gibt es hier jemand der die nextPermutation() in der <algorithm> verständlich machen kann oder en Beispiel für einen n-buchstabigen Algorithmus hat ?

#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

int main()
{
int n = 7, Iw1, Iw2, Iw3, Iw4, Iw5, Iw6, Iw7, z = 1, h;

char lw[6], ausgabew[6];
ofstream perm("perm.txt", ios::out);

/*
cout << "Geben sie ein 7 Buchstabiges Wort ein !\n\n";

for (int i=0; i<n; i++)
{
	cin >> lw[i];
}
*/

lw[0] = 's';
lw[1] = 't';
lw[2] = 'e';
lw[3] = 'p';
lw[4] = 'h';
lw[5] = 'a';
lw[6] = 'n';

	for (Iw1 = 0; Iw1 < n; Iw1++)
	{
		for (Iw2 = 0; Iw2 < n; Iw2++)
		{
			for (Iw3 = 0; Iw3 < n; Iw3++)
			{
				for (Iw4 = 0; Iw4 < n; Iw4++)
				{
					for (Iw5 = 0; Iw5 < n; Iw5++)
					{
						for (Iw6 = 0; Iw6 < n; Iw6++)
						{
							if (Iw6 != Iw5 && Iw6 != Iw4 && Iw6 != Iw3 && Iw6 != Iw2 && Iw6 != Iw1 && Iw5 != Iw4 && Iw5 != Iw3 && Iw5 != Iw2 && Iw5 != Iw1 && Iw4 != Iw1 && Iw4 != Iw2 && Iw4 != Iw3 && Iw3 != Iw1 && Iw3 != Iw2 && Iw2 != Iw1)
							{
								Iw7 = 28 - (Iw1 + Iw2 + Iw3 + Iw4 + Iw5 + Iw6) - 7;

								// Excel:
                                // ausgabew = lw(Iw1) & lw(Iw2) & lw(Iw3) & lw(Iw4) & lw(Iw5) & lw(Iw6) & lw(Iw7)

								ausgabew[0] = lw[Iw1];
								ausgabew[1] = lw[Iw2];
								ausgabew[2] = lw[Iw3];
								ausgabew[3] = lw[Iw4];
								ausgabew[4] = lw[Iw5];
								ausgabew[5] = lw[Iw6];
								ausgabew[6] = lw[Iw7];

								for (int j=0; j<7; j++)
								{
									cout << ausgabew[j];
									perm << ausgabew[j];
								}

								cout << "\n";
								perm << "\n";

							}
						}
					}
				}
			}
		}
	}

	perm.close();

return 0;
}

Danke für gute Ansätze

[camper]

next_permutation() arbeitet über lexikografische ordnung der elemente - um damit alle permutationen zu erwischen, muss zunächst sortiert werden. der vorteil ist, dass das ganze auch bei vorhandensein doppelter elemente funktioniert.
eine einfache rekursive funktion, die keine rücksicht auf doppelte elemente nimmt und keine lexikografische ordnung erfordert (sie allerdings erhält, wenn die menge sortiert war), könnte so aus sehen:

char s[] = "abcdefghi";
void do_something(); // wird für jede einzelne permutation aufgerufen
void iterate_perm(char* where, int level)
{
    if ( level > 1 )
    {
        for ( int i = 0; i < level; ++i )
        {
            iterate_perm( where + 1, i - 1 );
            std::swap( where[ 0 ], where[ 1 ] );
        }
    }
    else
    {
        do_something();
    }
}
int main()
{
    iterate_perm( s, sizeof( s ) - 1 );
}

man kann hier noch einiges verbessern, das ist nur zur verdeutlichung des konzepts.

[Lord Calf]

Was ist das Problem das der hier in der CMD nix ausgibt ??

#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;

char s[] = "abcdefghi"; 

void sleep()
{
	int c=50 ,d=0;

	while (d!=c)
	{
		int start=time(0);

		while(start==time(0))
		{
			// tue nichts
		}

		d+=5;
	}
}

// void do_something(); // wird für jede einzelne permutation aufgerufen 

void iterate_perm (char* where, int level) 
{ 
    if (level > 1) 
    { 
        for (int i = 0; i < level; i++) 
        { 
            iterate_perm (where + 1, i - 1); 
            std::swap (where [0], where [1]); 
        } 
    } 
    else 
    { 
        sleep();
    } 
} 

int main() 
{ 
    iterate_perm (s, sizeof(s) - 1);

	for (int i=0; i<sizeof(s)-1; i++)
	{
		cout << s[i];
	}

	return 0;
}

Greez Sven aus Dresden

[camper]

das liegt daran, dass die funktion mist ist :p

void iterate_perm (char* where, int level)
{
    if (level > 1)
    {
        for (int i = 0; i < level; i++)
        {
            std::swap (where [0], where [i]);
            iterate_perm (where + 1, level - 1);
            std::swap (where [0], where [i]);
        }
    }
    else
    {
        std::cout << s << std::endl;
    }
}

so müsste es funktionieren.