package coding4fun;

import java.util.ArrayList;
import java.util.List;

/**
 * Find the next permutation in lexicographical order.
 *
 * <pre>
 * Input : 362541
 * Output: 364125
 * </pre>
 */
public class Problem42 {
    private static String nextPermutation(String str) {
        char[] chars = str.toCharArray();
        List<Character> reversed = new ArrayList<>();
        for (int i = chars.length - 1; i >= 1; i--) {
            // in increasing order
            if (chars[i + 1] < chars[i]) {
                for (int j = 0; j < reversed.size(); j++) {
                    // TODO:
                }
            } else {
                reversed.add(chars[i]);
            }
        }
    }

    private static void swap(char[] chars, int i, int j) {
        char tmp = chars[i];
        chars[i] = chars[j];
        chars[j] = tmp;
    }

    public static void main(String[] args) {
        System.out.println(nextPermutation("362541"));
    }
}

@@ -18,60 +18,8 @@
 n;%0A%0A
-import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 /**%0A
@@ -121,16 +121,94 @@
  364125%0A
+ *%0A * Input : 123456%0A * Output: 123465%0A *%0A * Input : 654321%0A * Output: 123456%0A
  * %3C/pre
@@ -348,91 +348,62 @@
     
-List%3CCharacter%3E reversed = new ArrayList%3C%3E();%0A        for (int i = chars.length - 1
+int i = chars.length - 1;%0A        outer:%0A        for (
 ; i 
@@ -474,17 +474,17 @@
 chars%5Bi 
-+
+-
  1%5D %3C ch
@@ -526,106 +526,233 @@
 j = 
-0; j %3C reversed.size(); j++) %7B%0A                    // TODO:%0A                %7D%0A            %7D else %7B
+chars.length - 1; j != i - 1; j--) %7B%0A                    if (chars%5Bj%5D %3E chars%5Bi - 1%5D) %7B%0A                        swap(chars, j, i - 1);%0A                        break outer;%0A                    %7D%0A                %7D%0A            %7D
 %0A   
@@ -756,24 +756,26 @@
         
+%7D%0A
         
 reversed
@@ -770,55 +770,139 @@
     
-reversed.add(chars%5Bi%5D);%0A            %7D%0A        %7D
+for (int j = i, k = chars.length - 1; j %3C k; j++, k--) %7B%0A            swap(chars, j, k);%0A        %7D%0A        return new String(chars);
 %0A   
@@ -1152,16 +1152,156 @@
 2541%22));
+ // 364125%0A        System.out.println(nextPermutation(%22123456%22)); // 123465%0A        System.out.println(nextPermutation(%22654321%22)); // 123456
 %0A    %7D%0A%7D

Update problem 42