java - 如何编写一个递归方法来将字符串提升为所有可能的组合，而不需要循环或数组？

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,a-f)。

您要查找的密码包含密码中允许的字符集的字母表。该集合以字符数组表示。数组定义了集合的顺序和大小。要迭代密码，您可以将计数算法应用于您的密码“数字”。

以下代码执行此操作:

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。为了处理“字母表末尾”，我们使用模数运算符(operator)。当我们到达字母表末尾时，它将返回 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];
    }