Java 具有给定字符数组中所有可能组合/排列的蛮力算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18685518/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
brute forcer algorithm with all possible combinations / permutation in a given char array
提问by Masood Ahmad
Need help for this simple thing that is annoying me. I have seen many similar algorithms but I want to do this in exactlythe stated way to reach ALLpossible combinations / permutation in a given charset array.
需要帮助来解决这个让我烦恼的简单事情。我见过许多类似的算法，但我想按照规定的方式做到这一点，以达到给定字符集数组中所有可能的组合/排列。
lets take an example of a password cracker brute forcer
让我们举一个密码破解者暴力破解器的例子
e.g char[] charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();?
例如 char[] charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();？
stated way:
陈述方式：
its like this. for the current example.
就像这样。对于当前示例。
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
Code I reached so far:
到目前为止我达到的代码：
(well not a solution though) is to have as many for loops as the length of charset array. that is insane. this works ok. but i need intelligent one.
（虽然不是解决方案）是具有与字符集数组长度一样多的 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);
}
}
}
}
采纳答案by Christian Trimble
To solve this without recursion, it helps to keep an array of the indices for your current result. Here is a template class that will produce the result you are looking for:
为了在不递归的情况下解决这个问题，它有助于为当前结果保留一个索引数组。这是一个模板类，它将产生您正在寻找的结果：
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);
}
You can then extend the template to print each element to STDOUT:
然后，您可以扩展模板以将每个元素打印到 STDOUT：
new Bruteforce() {
public void element(char[] result, int offset, int length) {
System.out.println(new String(result, offset, length));
}
}.generate("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
NOTE: This code assumes that the input string does not contain any duplicate characters.
注意：此代码假定输入字符串不包含任何重复字符。
回答by Peter Lawrey
You can use recusrion and a couple of loops.
您可以使用 recusrion 和几个循环。
public static void printCombinations(int length) {
printCombinations(new char[length], 0, 0);
}
private static void printCombinations(char[] chars, int idx, int mask) {
if (idx == chars.length) {
System.out.println(chars);
return;
}
for (int i = 0; i < 26; i++) {
int mask2 = 1 << i;
if ((mask2 & mask) == 0) {
chars[idx] = (char) ('A' + i);
printCombinations(chars, idx + 1, mask | mask2);
}
}
}
public static void main(String[] args) throws Exception {
for (int i = 1; i <= 3; i++)
printCombinations(i);
}
prints
印刷
A
B
...
ZYWX ... DCBA
A combination has no repeating characters so it wouldn't be ZZZZZ...
组合没有重复的字符，所以它不会是 ZZZZZ ...
回答by Olayinka
A pseudo-code
一个伪代码
initialize globalComb, an empty array of strings (to keep all combination)
initialize prevComb, an array of strings with an empty string (the previous set of combination)
while(the length of first string in prevComb is not of desired length)
initialize temp, an empty array of strings (a temporary one)
for(each string s in prevComb)
for(each char c in the alphabet)
insert s + c in temp
insert s + c in globalComb
end for
end for
lastComb = temp
return globalComb
the size of globalCombmust be sum(k=1, k=desired length)26^k. If the desired length is 26, I doubt if an average laptop can hold an array of such strings. Instead of storing in a global array, you can just print the strings out.
的大小globalComb必须是 sum(k=1, k=desired length)26^k。如果所需的长度是 26，我怀疑普通的笔记本电脑是否可以容纳这样的字符串数组。您可以将字符串打印出来，而不是存储在全局数组中。
回答by rendon
You need to use recursion. The complexity of the algorithm is exponential. I hope I understood the problem.
您需要使用递归。算法的复杂度是指数级的。我希望我理解了这个问题。
public class Generator {
private char[] charset;
public Generator()
{
charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
}
public void generate(String str, int pos, int length)
{
if (length == 0) {
System.out.println(str);
} else {
for (int i = pos; i < charset.length; i++) {
generate(str + charset[i], i, length - 1);
}
}
}
public static void main(String[] args)
{
Generator test = new Generator();
//test.generate("", 1);
for (int length = 1; length < 5; length++) // Change 5 with the length of charset
test.generate("", 0, length);
}
}
回答by Null
public class Generator {
private char[] charset;
private int min; //var added for min char length
private int max; //var added for max char length
public Generator() {
charset = "abcdefghijklmnopqrstuvwxyzAEIOU0123456789!@#$%^&*()-_+=~`[]{}|:;<>,.?/BCDFGHJKLMNPQRSTVWXYZ".toCharArray();
min = 2; //char min start
max = 5; //char max end
}
public void generate(String str, int pos, int length) {
if (length == 0) {
System.out.println(str);
} else {
//This if statement resets the char position back to the very first character in the character set ('a'), which makes this a complete solution to an all combinations bruteforce!
if (pos != 0) {
pos = 0;
}
for (int i = pos; i < charset.length; i++) {
generate(str + charset[i], i, length - 1);
}
}
}
public static void main(String[] args) {
Generator bruteforce = new Generator();
for (int length = bruteforce.min; length < bruteforce.max; length++) // Change bruteforce.min and bruteforce.max for number of characters to bruteforce.
bruteforce.generate("", 0, length); //prepend_string, pos, length
}
}
I've modified rendon's example above- https://stackoverflow.com/revisions/18685721/1Note: it allow all combinations, and added min and max vars
我已经修改了上面 rendon 的示例 - https://stackoverflow.com/revisions/18685721/1注意：它允许所有组合，并添加了最小和最大变量
回答by Meir Bookatz
I have come up with this piece of code
this will run to 8 didgets/letters
eg. if you are using just capital letters A to Z:
A
B
...
...
ZZZZZZZY
ZZZZZZZZ
我想出了这段代码，它将运行到 8 个 didgets/letters
例如。如果您只使用大写字母 A 到 Z：
A
B
...
...
ZZZZZZZY
ZZZZZZZZ
char[] ch = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
for (int i = 0; i < ch.length; i++) {
char c1 = ch[i];
for (int j = 0; j < ch.length; j++) {
char c2 = ch[j];
for (int k = 0; k < ch.length; k++) {
char c3 = ch[k];
for (int l = 0; l < 10; l++) {
char c4 = ch[l];
for (int m = 0; m < 10; m++) {
char c5 = ch[m];
for (int n = 0; n < 10; n++) {
char c6 = ch[n];
for (int o = 0; o < 10; o++) {
char c7 = ch[o];
for (int p = 0; p < 10; p++) {
char c8 = ch[p];
currentString = "" + c1 + c2 + c3 + c4 + c5 + c6 + c7 + c8;
System.out.println(currentString);
}
}
}
}
}
}
}
}
回答by Ben Manwaring
A more object orientated solution
更面向对象的解决方案
Usage known length
用法已知长度
final String target = "ABC";
final char[] charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
BruteForce.bruteForce(charset, 5, string -> {
System.out.println(string);
return string.equals(target);
});
Usage unknown length
用法未知长度
final String target = "ABC";
final char[] charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
// Use your looping method of choice
boolean found = false;
int length = 1;
while (!found) {
found = BruteForce.bruteForce(charset, length, string -> {
System.out.println(string);
return string.equals(target);
});
length++;
}
Implementation
执行
public class BruteForce {
public static boolean bruteForce(@NonNull final char[] input, final int length, @NonNull final Closure closure) {
final char[] chars = new char[length];
final IncrementalCharSequence incrementalCharSequence = new IncrementalCharSequence(input, chars);
// Use your looping method of choice
do {
if (closure.compare(new String(chars))) {
return true;
}
} while (incrementalCharSequence.increment());
return false;
}
}
public interface Closure {
boolean compare(@NonNull final String string);
}
public class IncrementalCharSequence {
@NonNull
private final char[] input;
@Nullable
private final IncrementalCharSequence subIncrementalCharSequence;
@NonNull
private final char[] chars;
private final int index;
private int currentIndex;
public IncrementalCharSequence(@NonNull final char[] input, @NonNull final char[] chars) {
this(input, chars, 0);
}
private IncrementalCharSequence(@NonNull final char[] input, @NonNull final char[] chars, final int index) {
this.input = input;
this.chars = chars;
this.index = index;
if (index + 1 < chars.length) {
this.subIncrementalCharSequence = new IncrementalCharSequence(input, chars, index + 1);
} else {
this.subIncrementalCharSequence = null;
}
currentIndex = 0;
chars[index] = input[currentIndex];
}
/**
* Increment the char sequence
*
* @return {@code true} if incremented, {@code false} if rolled over to zero index
*/
public boolean increment() {
if (subIncrementalCharSequence != null && subIncrementalCharSequence.increment()) {
return true;
} else if (currentIndex < input.length) {
chars[index] = input[currentIndex];
currentIndex++;
return true;
} else {
currentIndex = 0;
chars[index] = input[currentIndex];
return false;
}
}
}
