Как написать рекурсивный метод для продвижения строки во все возможные комбинации, без циклов или массивов?

Question

public Password(int length)//a constructor that creates a random password in a given length
public boolean isPassword(String st)//retruns True if the String equals to the password.

Мне нужно сделать рекурсивный метод... взломать пароль... он содержит только строчные буквы. Я могу использовать только: isPassword(),(charAt, равно, длина, подстрока) Нет циклов, нет массивов...

это то, что я сделал до сих пор, я получил строку "a" нужной длины:

/**
 * Recursive method, cracks and return 
 * the right string of Password p.
 * @param p The Password object to crack.
 * @param length The length of the password.
 * @return The String combination of the password.
 */
public static String findPassword(Password p,int length)
{
    String aString;//to store an "aaa.." string in the length of p
    String password;//to store the password

    aString = findPassword("a",length);//recursion method, gets string of a in length
    password = findPassword(aString, p, 0);//recursion method, finds the password

    return password;
}
public static String findPassword(String startString, int length)
{   //recursion to make "aaa..." string in the length of n.
    if (startString.length() != length )//if not in the length
    {
        startString += "a";        //add "a" character
        if(startString.length() == length)//if in the length, 
        {                     //return String
            return startString;
        }
    }                  //call the recursion if still
    return findPassword(startString,length);//not in the length
}

Теперь мне нужно выдвинуть эту строку во все возможные комбинации... и я не знаю, как это сделать без циклов или массива... спасибо!

Answer 1

У меня есть ответ для вас.

Идея взломать пароль состоит в том, чтобы пройти через все возможные комбинации. Комбинации, в основном, представляют собой последовательность, подобную 1,2,3,4, ... (iIrc B-adic последовательности - термин в математике).

Для десятичной последовательности у вас есть цифры 0-9, и правило состоит в том, чтобы переполниться до следующего числа, если вы достигнете конца алфавита (9 в данном случае).

Десятичная система счисления может применяться к чему угодно: двоичные числа имеют алфавит 2 (0,1). шестнадцатеричные числа имеют алфавит 16 (0-9,af).

В пароле, который вы ищете, есть алфавит разрешенного набора символов в вашем пароле. Набор представлен в виде массива символов. Массив определяет порядок и размер набора. Чтобы перебрать пароли, вы применяете алгоритм подсчета к вашему паролю -"число".

Следующий код делает это:

public class PasswordFinder {

    private static final String PASSWORD = "zxy";
    private static final char[] ALPHABET = "abcdefghijklmnopqrstuvwxyz".toCharArray();

    boolean isPassword(String pass) {
        return (pass.equals(PASSWORD));
    }

    boolean findPassword(String password) {
        while (!isPassword(password)) {
            password = next(password);
        }
        return true;
    }

    /* recursive variant, will require up to (ALPHABET.length^(PASSWORD.length+1)) - 1 recursions */

    boolean findPasswordRecursive(String password) {
        if (isPassword(password)) {
            return true;
        }

        return findPasswordRecursive(next(password));
    }

    private String next(String password) {
        if( password.length() == 0 ) {
            return "" + ALPHABET[0];
        }

        char nextChar = password.charAt(password.length()-1);
        int idx = (nextChar - ALPHABET[0] + 1) % ALPHABET.length;
        if( idx == 0 ) {
            return next(password.substring(0, password.length() - 1)) + ALPHABET[0];
        }

        return password.substring(0, password.length() - 1) + ALPHABET[idx];
    }
}

next Функция подсчитывает:

Если мы не получим пароль (вы можете также применить здесь проверку на ноль), мы создадим ее с первой "цифрой" из нашего алфавита:

        if( password.length() == 0 ) {
            return "" + ALPHABET[0];
        }

Теперь мы выбираем символ для подсчета. Это всегда последняя цифра вашей последовательности, последний символ строки:

        char nextChar = password.charAt(password.length()-1);

Для подсчета мы вычисляем индекс символа в алфавите (индекс волшебства, вычитаем первый символ из найденного символа), индекс увеличивается на 1. Чтобы обработать "конец алфавита", мы используем оператор по модулю. Он вернет 0, когда мы достигли конца алфавита.

        int idx = (nextChar - ALPHABET[0] + 1) % ALPHABET.length;

Когда мы дойдем до конца алфавита, нам нужно перейти к следующей цифре и добавить к ней: "9" + 1 => "10", Поскольку переполнение является рекурсивным, мы используем нашу функцию подсчета, чтобы добавить по одной к каждой цифре в пароле и переполнить соответственно. Для этого мы добавляем 1 к префиксу последней цифры и сбрасываем последнюю цифру на "0": "89" + 1 => next("8") + "0"

        if( idx == 0 ) {
            return next(password.substring(0, password.length() - 1)) + ALPHABET[0];
        }

Если нам не нужно переполнять, мы просто увеличиваем последнюю цифру.

        return password.substring(0, password.length() - 1) + ALPHABET[idx];
    }