如何编写递归方法将 String 提升为所有可能的组合，没有循环或数组？

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, equals, length, substring) 没有循环，没有数组...

这是我到目前为止所做的，我得到了一个 "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)。

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

以下代码执行此操作：

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 函数进行计数：

如果我们没有收到密码（您也可以在此处应用空检查），我们将使用字母表中的第一个 "digit" 创建密码：

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

我们现在 select 要计数的字符。它始终是序列的最后一位，字符串的最后一个字符：

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

为了计数，我们计算字符在字母表中的索引（index magic，从找到的字符中减去第一个字符），索引增加1。为了处理"end of alphabet"，我们使用模运算符。当我们到达字母表的末尾时，它将 return 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];
    }

如何编写递归方法将 String 提升为所有可能的组合，没有循环或数组？

How to write a recursive method to promote a String to all possible combinations, With no loops or arrays?

java

passwords

recursion

combinations