Returning Next Permutation of a number

Question

The problem is stated here. I wrote a code to accomplish the task.

/**
 * Created by aditya on 16-10-2014.
 */

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        int n = scan.nextInt();
        int k = scan.nextInt();
        ArrayList<Integer> list = new ArrayList<Integer>(k);
        ArrayList<Integer> list_out = new ArrayList<Integer>(k);
        for (int i = 0; i < k; i++) {
            list.add(scan.nextInt());
        }
        for (int j = 0; j < k; j++) {
            list_out.add(next_perm(list.get(j), n));
        }
        for (int temp : list_out) {
            System.out.println(temp);
        }
        System.out.flush();
    }

    public static int next_perm(int k, int n) {
        int perm = 0;
        int number = k;
        int num[] = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = number % 10;
            number /= 10;
        }
        int k_max = 0;
        for (int i = 0; i < n; i++) {
            if (i == (n-1))
                break;
            if (num[i + 1] >= num[i]) {
                ++k_max;
            } else if (num[i + 1] < num[i]) {
                break;
            }
        }
        if(k_max==(n-1))return k;
        int j_max = k_max+1;
        for (int i = k_max; i >= 0; i--) {
            if (num[i] > num[k_max + 1]) {
                --j_max;
            } else {
                break;
            }
        }
        int temp=num[j_max];
        num[j_max]=num[k_max+1];
        num[k_max+1]=temp;
        for(int i=k_max,j=0;i>j;i--,j++){
            int tempo = num[i];
            num[i]=num[j];
            num[j]=tempo;
        }
        for (int i = 0; i < n; i++) {
            perm += num[i] * (int) Math.pow(10, i);
        }
        return perm;
    }
}

And I manually ran all permutations of 1,2,..n for n=1 to 4 and got the correct results. For those of you wondering about the logic see here. No warnings or errors are displayed. When submitted to the online judge it declares it a wrong answer (after conducting 9 tests). [See below for link and results] The 9 tests must be a subset of all permutations of n=1 to 9 corresponding to each test so at least my 4 tests should be correct, but my code passes no tests, please help me I see no bugs.

Edit: See a sample input-output for the case of n=4 here.Added below too

Note: I converted "\n" to "space" for space issues in question

(Input) 4 24 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321

(Output) 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 4321

Edit: See results here. Added here too:

Problem: NEXTPERM
State: Wrong Answer
Total score for this submission: 0

Test Case #0 for 2 points Wrong Answer Runtime: 0.12

Test Case #1 for 2 points Wrong Answer Runtime: 0.124

Test Case #2 for 2 points Wrong Answer Runtime: 0.124

Test Case #3 for 2 points Wrong Answer Runtime: 0.12

Test Case #4 for 2 points Wrong Answer Runtime: 0.116

Test Case #5 for 2 points Wrong Answer Runtime: 0.124

Test Case #6 for 2 points Wrong Answer Runtime: 0.124

Test Case #7 for 2 points Wrong Answer Runtime: 0.14

Test Case #8 for 2 points Wrong Answer Runtime: 0.108

Test Case #9 for 2 points Wrong Answer Runtime: 0.124

I believe this problem is essentially finding the next larger number using the same set of digits. Have a look at this: http://stackoverflow.com/questions/9368205/given-a-number-find-the-next-higher-number-which-has-the-exact-same-set-of-digi — Sinstein, Oct 17 '14 at 05:20
@Sinstein yes but it would be time consuming for the case of arge number of digits, see [this](http://math.stackexchange.com/questions/976594/finding-next-permutation-of-a-number) — RE60K, Oct 17 '14 at 05:21
You only have to deal with a maximum of 10 digits, and you only need to find the next permutation, not the `jth` permutation. Start scanning from the right and for every digit you encounter check if there exists a digit smaller in value than it in its preceding set of digits, if you find one, swap the 2, else move on to the next digit. This gives an order of `O(n^2)` which for `n = 1000` is not bad. — Sinstein, Oct 17 '14 at 05:26
@Sinstein not being rude, what do you think, will it complete in 3 seconds for n=10? — RE60K, Oct 17 '14 at 05:29
I am pretty sure it will. Moreover, the answer in the link provided accomplishes that task in `O(n)`. — Sinstein, Oct 17 '14 at 06:16
anyways thanks for being helpful @Sinstein, btw did you find any error to mine? — RE60K, Oct 17 '14 at 07:17

score 0 · Accepted Answer · answered Feb 04 '15 at 20:00

Apparently It worked with:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 * Created by Aditya on 14-10-2014.
 */
public class Main {

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        ArrayList<String> lines = new ArrayList<String>();
        ArrayList<String> words = new ArrayList<String>();
        ArrayList<String> words_2 = new ArrayList<String>();
        boolean once_entered = true;
        for (int i = 0; i < n; i++) {
            lines.add(i, scan.nextLine() + " ");
        }
        for (int i = 0; i < n; i++) {
            String word = "";
            for (int j = 0; j < lines.get(i).length(); j++) {
                char char_0 = lines.get(i).toLowerCase().charAt(j);
                if ((int) (char_0) >= (int) ('a') && (int) (char_0) <= (int) ('z')) {
                    word += char_0;
                    once_entered = false;
                } else if (!once_entered) {
                    words.add(word);
                    word = "";
                    once_entered = true;
                }
            }
        }
        for (int i = 0; i < words.size(); i++) {
            boolean contains =false;
            for(int j=0;j<words_2.size();j++){
                if(words_2.get(j).contentEquals(words.get(i)))
                    contains=true;
            }
            if(!contains)
                words_2.add(words.get(i));
        }
        Collections.sort(words_2);
        System.out.println(words_2.size());
        for (int i = 0; i < words_2.size(); i++) {
            System.out.println(words_2.get(i));
        }
    }
}

Seems there was some problem with duplicates and some minor ones.

Returning Next Permutation of a number

Edit: See a sample input-output for the case of n=4 here.Added below too

Edit: See results here. Added here too:

1 Answers1