具有给定char数组中所有可能组合/置换的暴力算法算法

Question

需要帮助解决这个令我烦恼的简单事情.我已经看到了许多类似的算法,但我想以完全所述的方式来实现这一点,以在给定的字符集数组中达到所有可能的组合/置换.

让我们举个密码破解者暴力破坏者的例子

例如 char[] charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();？

陈述方式:

就像这样.对于当前的例子.

a,b,c,d......z     then at last index "z".  

it goes like      

aa,ab,ac....az.        then      

ba,bb,bc,bd........bz          then

same for ca, cb, and so on.

aaaa,aaab,aaac......aaaz   then

baaa,baab,baac.......baaz   to      zzzzzzzzzzzzzzzzzzzzzzzzzz

我到目前为止的代码:

(尽管不是解决方案)是拥有与charset数组长度一样多的for循环.那太疯狂了.这工作正常.但我需要聪明的一个.

public class Bruteforcer {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
          char[] charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();


         int currentIndex = 0;
         String currentString = "";

         for (int i = 0; i < charset.length; i++) {
            char currentChar = charset[i];

             for (int j = 0; j < charset.length; j++) {

                 char c = charset[j];
                 currentString =  "" +currentChar + c;
                 System.out.println(currentString);

             }


         }


    }
}

Answer 1

要在没有递归的情况下解决这个问题,有助于为当前结果保留索引数组.这是一个模板类,它将生成您正在寻找的结果:

public abstract class Bruteforce
{
  public void generate( char[] input ) {
    char[] result = new char[input.length];
    int[] index = new int[input.length];

    // initialize the arrays.
    Arrays.fill(result, 0, result.length, input[0]);
    Arrays.fill(index,  0, index.length, 0);

    // loop over the output lengths.
    for( int length = 1; length <= input.length; length++ ) {
      int updateIndex = 0;
      do {
        element(result, 0, length);

        // update values that need to reset.
        for(updateIndex = length-1;
            updateIndex != -1 && ++index[updateIndex] == input.length;
            result[updateIndex] = input[0], index[updateIndex] = 0, updateIndex--);

        // update the character that is not resetting, if valid
        if( updateIndex != -1 ) result[updateIndex] = input[index[updateIndex]];
      }
      while(updateIndex != -1);
    }
  }
  public void generate( String input ) {
    generate(input.toCharArray());
  }
  public abstract void element(char[] result, int offset, int length);
}

然后,您可以扩展模板以将每个元素打印到STDOUT:

new Bruteforce() {
  public void element(char[] result, int offset, int length) {
    System.out.println(new String(result, offset, length));
  }
}.generate("ABCDEFGHIJKLMNOPQRSTUVWXYZ");

注意:此代码假定输入字符串不包含任何重复的字符.