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 >> |