Программа для поиска наименьшей перестановки числа n1, но должна быть больше другого заданного числа n2; выведите «Invalid», если это невозможно

Question

Задача связана с двумя входными целыми числами. Нам нужно найти перестановку n1 так, чтобы ее наименьшее целое число было больше n2.

Я попытался написать код, но не получил правильный вывод. Я не могу понять, как напечатать только самую маленькую перестановку, большую, чем n2. Мой код печатает все перестановки больше n2.

Мой код:

        import java.util.*;
        class kbc{
        public static void main (String args[])  throws Exception {    
        int n1=124;
        int n2=320;
        String s1 = "";
        s1+= n1;
        String s2 = "";
        s2+= n2;
        if(s2.length()>s1.length())
        System.out.println("Invalid");
        else{
            int[] ad = new int[s1.length()];
            for (int i=0; i<s1.length();i++){
                ad[i]= s1.charAt(i)-'0';
            }
            printSmallest(ad,n2,0);
        }
    }
    static void printSmallest(int[] a, int n2, int k) 
    {
        int snum;
        int saved= Integer.MAX_VALUE;
        String s="";
        if (k == a.length) 
        {
            for (int i = 0; i < a.length; i++) 
            {
                s=s+a[i];
            }
            snum = Integer.parseInt(s);
             if(snum>n2){
            if(snum<saved){
                 saved=snum;
             }
             System.out.println(saved);
             }

         }

        else{ 
        for (int i = k; i < a.length; i++){
                int temp = a[k];
                a[k] = a[i];
                a[i] = temp;

                printSmallest(a,n2, k + 1);

                temp = a[k];
                a[k] = a[i];
                a[i] = temp;
        }
        }  
    }
}

Ожидаемый результат:

412

Вывод кода:

421
412

Answer 1

То, как вы выбираете символы для перестановки, вызывает проблему. Если вы выберете символы в порядке возрастания их значения ASCII, то это не будет проблемой. Получив нужный номер, вы можете сказать рекурсии, что «ОК, я нашел свой ответ, не звоните снова». Вы можете проверить этот код. Я не сильно изменил твой код.

class kbc {

    private static boolean taken[];
    private static boolean found = false;
    public static void main (String args[])  throws Exception {    
        int n1=124;
        int n2=320;
        String s1 = "";
        s1+= n1;
        String s2 = "";
        s2+= n2;
        if(s2.length()>s1.length())
            System.out.println("Invalid");
        else {
            taken = new boolean[s1.length()];
            char[] ad = new char[s1.length()];
            char[] tempArray = s1.toCharArray();
            Arrays.sort(tempArray);
            s1 = new String(tempArray);
            printSmallest(ad, s1, n2,0);
        }
    }
    static void printSmallest(char[] a, String s1, int n2, int k) 
    {
        if(found)
            return;
        int snum;
        int saved= Integer.MAX_VALUE;
        String s="";
        if (k == a.length) 
        {
            for (int i = 0; i < a.length; i++) 
            {
                s=s+a[i];
            }
            snum = Integer.parseInt(s);
            if(snum>n2){
                if(snum<saved){
                    saved=snum;
                    found = true;
                }
                System.out.println(saved);
            }

        }
        else{ 
            for (int i = 0; i < a.length; i++){
                if(!taken[i] && !found) {
                    taken[i] = true;
                    a[k] = s1.charAt(i);
                    printSmallest(a, s1, n2, k + 1);
                    taken[i] = false;
                }
            }
        }  
    }
}