Gesucht wird die 1.000.000ste lexikografische Permutation der Ziffern 0, 1, 2, 3, 4, 5, 6, 7, 8 und 9! [ das englische Original ]

Bei diesem Problem habe ich eine sehr lange Zeit darauf verwenden müssen, um einen Algorithmus für die Erzeugung der einzelnen Permutationen zu erkennen / finden. In der nachfolgenden Grafik sieht man am Beispiel der Ziffern 0 bis 3, wie man vorgehen kann:

Nach der Implementation dieses Algorithmus musste ich allerdings feststellen, dass die Laufzeit für Permutationen von mehr als 6 Ziffern nicht mehr akzeptabel war. Ich konnte allerdings auch beobachten, dass viele Permutationen übersprungen werden konnten, was diese Grafik veranschaulicht:

Zur Implementierung dieses Algorithmus bedarf es einer Methode, die einzelne Zeichen in einer Zeichenkette tauscht:

private String swapChar( String text, int oPos, int nPos ) {
   char[] tmp = new char[ text.length() ];
   int diff = 0;

   if( oPos > nPos ) {
      for( int i=0; i<text.length(); i++ ) {
         if( i == nPos ) {
            diff = 1;
            tmp[ i ] = text.charAt( oPos );
         } else if( i == oPos+1 ) {
            diff = 0;
            tmp[ i ] = text.charAt( i );
         } else {
            tmp[ i ] = text.charAt( i - diff );
         }
      }

      return new String( tmp );
   }

   if( oPos < nPos ) {
      for( int i=text.length()-1; i>=0; i-- ) {
         if( i == nPos ) {
            diff = 1;
            tmp[ i ] = text.charAt( oPos );
         } else if( i == oPos-1 ) {
            diff = 0;
            tmp[ i ] = text.charAt( i );
         } else {
            tmp[ i ] = text.charAt( i + diff );
         }
      }

      return new String( tmp );
   }

   return text;
}

Bevor das Problem nun gelöst werden kann, müssen einige lokale Variablen und Speicher vorbereitet werden:

@Override
public void prepare() {
   super.prepare();

   line = "0123456789";
   place = 1000000;

   factorials = new int[ line.length()-2 ];

   int fact = 1;

   for( int i=0; i<factorials.length; i++ ) {
      fact *= ( i+2 );
      factorials[ factorials.length-1-i ] = fact;
   }
}

Damit sind nun alle notwendigen Dinge vorbereitet, so dass die Lösung des Problems relativ trivial erscheint:

@Override
public String solve() {

   int nPlace = ( place % 2 == 0 ) ? place-1 : place;

   for( int i=0; i<factorials.length; i++ ) {
      int div = nPlace / factorials[ i ];
      line = swapChar( line, i+div, i );
      IO.debugln( "step " + i + " => " + line );
      nPlace -= div * factorials[ i ];
   }

   if( place % 2 == 0 )
      line = swapChar( line, line.length()-1, line.length()-2 );

   return line;
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 24 kann man sich hier anschauen!

<< Problem 23

Übersicht

Problem 25 >>