001package net.n1da.dev.euler;
002
003import net.n1da.dev.euler.core.*;
004import net.n1da.dev.euler.helper.*;
005
006/**
007 * Solution for problem 24
008 * "<strong>Lexicographic permutations</strong>"
009 * completed on Mon, 29 Jun 2015, 19:46.
010 * 
011 * @author <a href="mailto:nico@danneberg.de">Nico Danneberg</a>
012 * @since 14.04.2015 05:23:47
013 * 
014 * @see <a href="https://projecteuler.net/problem=24" target="_blank">Problem @ Project Euler</a>
015 * @see <a href="http://n1da.net/specials/projekt-euler/problem-24-lexikografische-permutationen/" target="_top">Solution @ Ni-Da-Net</a>
016 */
017public class PE0024 extends Problem {
018
019        /**
020         * Stores the line of chars to permute.
021         */
022        private String line;
023        
024        /**
025         * Stores which permutation is wanted.
026         */
027        private int place;
028        
029        /**
030         * Memory for all necessary permutations.
031         */
032        private int[] factorials;
033        
034        /**
035         * A simple constructor to set {@link Problem#number number}
036         * and {@link Problem#title title}.
037         */
038        public PE0024() {
039                super( 24, "Lexicographic permutations" );
040        }
041
042        /**
043         * Prepares the solution of this problem by setting the {@link #line}
044         * and {@link #place}. Additionally the {@link #factorials} array is
045         * filled matching the length of the character {@link #line}.
046         */
047        @Override
048        public void prepare() {
049                super.prepare();
050                
051                line = "0123456789";
052                place = 1000000;
053                
054                factorials = new int[ line.length()-2 ];
055                
056                int fact = 1;
057                
058                for( int i=0; i<factorials.length; i++ ) {
059                        fact *= ( i+2 );
060                        factorials[ factorials.length-1-i ] = fact;
061                }
062        }
063        
064        /**
065         * This method solves the given problem by running over the
066         * {@link #factorials} array to find the right positions to swap the
067         * characters.
068         * 
069         * @see #swapChar(String, int, int)
070         * @return the one millions permutation of the given characters
071         */
072        @Override
073        public String solve() {
074
075                int nPlace = ( place % 2 == 0 ) ? place-1 : place;
076                
077                for( int i=0; i<factorials.length; i++ ) {
078                        int div = nPlace / factorials[ i ];
079                        line = swapChar( line, i+div, i );
080                        IO.debugln( "step " + i + " => " + line );
081                        nPlace -= div * factorials[ i ];
082                }
083                
084                if( place % 2 == 0 )
085                        line = swapChar( line, line.length()-1, line.length()-2 );
086                
087                return line;
088        }
089
090        /**
091         * Swaps the character at given old to the new position. All chars
092         * following are moved to the right (or left).
093         * 
094         * @param text the line of characters to be changed
095         * @param oPos the old position of the char
096         * @param nPos the new position of the char
097         * @return the changed line of characters
098         */
099        private String swapChar( String text, int oPos, int nPos ) {
100                char[] tmp = new char[ text.length() ];
101                int diff = 0;
102                
103                if( oPos > nPos ) {
104                        for( int i=0; i<text.length(); i++ ) {
105                                if( i == nPos ) {
106                                        diff = 1;
107                                        tmp[ i ] = text.charAt( oPos );
108                                } else if( i == oPos+1 ) {
109                                        diff = 0;
110                                        tmp[ i ] = text.charAt( i );
111                                } else {
112                                        tmp[ i ] = text.charAt( i - diff );
113                                }
114                        }
115                        
116                        return new String( tmp );
117                }
118                
119                if( oPos < nPos ) {
120                        for( int i=text.length()-1; i>=0; i-- ) {
121                                if( i == nPos ) {
122                                        diff = 1;
123                                        tmp[ i ] = text.charAt( oPos );
124                                } else if( i == oPos-1 ) {
125                                        diff = 0;
126                                        tmp[ i ] = text.charAt( i );
127                                } else {
128                                        tmp[ i ] = text.charAt( i + diff );
129                                }
130                        }
131                        
132                        return new String( tmp );
133                }
134                
135                return text;
136        }
137}