Hallo Stefan,
Ist die Frage jetzt gelöst oder noch offen?
Ich denke mal - gelöst.
Und geht es darum, die nächste Nummer zu finden, oder alle?
Sowohl als auch 
[Algorithmus]
Danke für Deine gute Zusammenfassung. Ich hatte „damals“ eine
Weile damit herumgespielt und kam zu interessanten Ergebnissen
bezüglich der Laufzeit. Mich würde mal interessieren, wie
lange der Algorithmus in Java auf gängigen Maschinen braucht.
Vorteil gegenüber Permutationen: auch bei ungünstigen Zahlen
kommt man sehr schnell zu einem Ergebnis.
Die Dauer ist proportional zur Länge der Zahl.
Wahrscheinlich irgendwie „exponentiell“ ansteigend.
Hier eine Implementierung:
[Implementierung]
IMHO geht dieser Deiner nur mit Ziffern 0…9 (oder täusche
ich mich)? Um längere Sequenzen zu testen, könnte man ja
praktischerweise Buchstaben verwenden: ‚abcdefghijklm‘.
Wenn man alle Permutationen braucht, dann ist der Algorithmus
aber nicht sehr effizient.
In C (sorry, Java-Forum) erhalte ich folgende Laufzeiten
abhängig von der Stringlänge:
PIII/700MHz, MS-VC 6.0
------------------------------------------------------------------------
abc (L=3) -\> cba, 5 iter, 0.000 sek
abcd (L=4) -\> dcba, 23 iter, 0.000 sek
abcde (L=5) -\> edcba, 119 iter, 0.000 sek
abcdef (L=6) -\> fedcba, 719 iter, 0.000 sek
abcdefg (L=7) -\> gfedcba, 5039 iter, 0.000 sek
abcdefgh (L=8) -\> hgfedcba, 40319 iter, 0.015 sek
abcdefghi (L=9) -\> ihgfedcba, 362879 iter, 0.094 sek
abcdefghij (L=10) -\> jihgfedcba, 3628799 iter, 0.812 sek
abcdefghijk (L=11) -\> kjihgfedcba, 39916799 iter, 8.859 sek
abcdefghijkl (L=12) -\> lkjihgfedcba, 479001599 iter, 106.141 sek
Athlon XP/3400+ (2400MHz, single channel), gcc 3.3.3 -O6
-------------------------------------------------------------------------
abc (L=3) -\> cba, 5 iter, 0.000 sek
abcd (L=4) -\> dcba, 23 iter, 0.000 sek
abcde (L=5) -\> edcba, 119 iter, 0.000 sek
abcdef (L=6) -\> fedcba, 719 iter, 0.000 sek
abcdefg (L=7) -\> gfedcba, 5039 iter, 0.000 sek
abcdefgh (L=8) -\> hgfedcba, 40319 iter, 0.000 sek
abcdefghi (L=9) -\> ihgfedcba, 362879 iter, 0.030 sek
abcdefghij (L=10) -\> jihgfedcba, 3628799 iter, 0.340 sek
abcdefghijk (L=11) -\> kjihgfedcba, 39916799 iter, 3.570 sek
abcdefghijkl (L=12) -\> lkjihgfedcba, 479001599 iter, 43.150 sek
Interessant ist hier imho, wie „schwerhändig“ sich der Athlon-64
bei der Suche verhält. Und das gegen einen popeligen P3-700
mit Via-Board
Also, das Problem ist zwar gelöst, aber dennoch von
Interesse. Ich hänge mal im Angang den C-Quelltext
dran.
Danke & Grüße
CMБ
-------------------------- [permutx.c] ------------------------------
#include
#include
#include
#include
int SmlstLargerPos(const char \*s, int pos, int end)
{
int p=pos+1, pval=s[pos]; /\* finde den kleinsten Wert s[?] \*/
const char \*q; /\* der größer ist als s[pos] \*/
for(q=s+p; q pval && \*q s+start; q--) /\* suche rueckwaerts den ersten \*/
if(\*(q-1) gib dessen Position zurueck \*/
}
int FindSolutionOf(char \*s, int len, int verbose) /\* Hier der Algorithmus \*/
{
void SwitchPositions (char \*s, int p, int q); /\* vorwaerts-deklarationen \*/
void SortSequenceAt (char \*s, int len); /\* von Hilfsfunktionen \*/
int pos, nIter=0;
while( (pos = ReversionIncomplAt( s, 0, len )) \>= 0 ) {
if( verbose ) printf("\n%s", s);
SwitchPositions ( s, pos, SmlstLargerPos(s, pos, len) );
SortSequenceAt ( s+pos+1, len-pos-1 );
++nIter;
}
return nIter;
}
/\* - - - [Eintrittspunkt] - - - - - - - - - - - - - - - - - - - - - - - \*/
int main()
{
char sequence[] = "abcdefghijkl" /\*"0123456789"\*/;
char workseq[sizeof sequence];
int len, nIter, maxlen=strlen( sequence );
clock\_t nClocks;
memset(workseq, 0, sizeof workseq);
for(len=3; len %s, %d iter, %.3f sek\n", workseq, nIter,
(double)(clock()-nClocks)/CLOCKS\_PER\_SEC);
}
return 0;
}
/\* - - - [Hilfsfunktionen] - - - - - - - - - - - - - - - - - - - - - - \*/
void SwitchPositions(char \*s, int p, int q) /\* --- SwitchPositions --- \*/
{
int t = s[p]; /\* tausche Inhalt vo s an \*/
s[p] = s[q], s[q] = t; /\* den Positionen p und q \*/
}
/\* Char-Vergleichsfunktion fuer qsort\*/
int \_cmp\_( const void \*p1, const void \*p2 ) { return \*(char\*)p1 - \*(char\*)p2; }
/\* qsort-wrapper (stdlib) \*/
void SortSequenceAt( char \*s, int l ) { qsort(s, l, sizeof \*s, \_cmp\_); }
__END__