找到 64 字节数组的所有排列？
Find all permutations of 64 byte array?
我的目标是找到一个 64 字节数组的所有排列，并检查每个排列在执行函数 F 后是否等于给定的字节数组。
Consider a Small scale Example: Suppose I have 1234, I would like
to generate all the permutations of a 4 digit number _ _ _ _ and check
each time if it equals 1234
我的第一个想法是实现一个递归函数来生成排列。但是考虑到大小，栈会溢出。
有没有生成所有排列的有效方法？鉴于 Java 有大量图书馆？
至于非递归，这个答案可能有帮助：Permutation algorithm without recursion? Java
至于简单的例子，这里是我制定的递归解决方案：
public class Solution {
public List<List<Integer>> permute(int[] num) {
boolean[] used = new boolean[num.length];
for (int i = 0; i < used.length; i ++) used[i] = false;
List<List<Integer>> output = new ArrayList<List<Integer>>();
ArrayList<Integer> temp = new ArrayList<Integer>();
permuteHelper(num, 0, used, output, temp);
return output;
}
public void permuteHelper(int[] num, int level, boolean[] used, List<List<Integer>> output, ArrayList<Integer> temp){
if (level == num.length){
output.add(new ArrayList<Integer>(temp));
}
else{
for (int i = 0; i < num.length; i++){
if (!used[i]){
temp.add(num[i]);
used[i] = true;
permuteHelper(num, level+1, used, output, temp);
used[i] = false;
temp.remove(temp.size()-1);
}
}
}
}
}
编辑：10 似乎是递归方法在合理时间内完成的最大输入。
对于长度为 10 的输入数组：
Permutation execution time in milliseconds: 3380
编辑：
我快速搜索了可能的实现，并发现了一个建议的算法，作为对另一个问题的答案的一部分。
为了方便起见，下面是https://whosebug.com/users/2132573/jon-b开发的代码。
它正确地创建并打印了整数列表的所有排列。您可以轻松地对数组使用相同的逻辑（致谢 jon-b !!）。
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class HelloWorld {
public static int factorial(int x) {
int f = 1;
while (x > 1) {
f = f * x;
x--;
}
return f;
}
public static List<Integer> permute(List<Integer> list, int iteration) {
if (list.size() <= 1) return list;
int fact = factorial(list.size() - 1);
int first = iteration / fact;
List<Integer> copy = new ArrayList<Integer>(list);
Integer head = copy.remove(first);
int remainder = iteration % fact;
List<Integer> tail = permute(copy, remainder);
tail.add(0, head);
return tail;
}
public static void main(String[] args) throws IOException {
List<Integer> list = Arrays.asList(4, 5, 6, 7);
for (int i = 0; i < 24; i++) {
System.out.println(permute(list, i));
}
}
}
我已经在 http://www.tutorialspoint.com/compile_java8_online.php 中对其进行了测试，它运行良好。
希望对您有所帮助！
如果我没理解错的话，你需要生成所有的64！ 64 字节数组的排列，即：
64！ = 126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000 排列！
如果每次排列和比较都需要一毫秒（最坏情况下的时间场景）来计算，您将需要：
4023558225072430368576654912961741527234446859923426946943236123009091331506849.3150684931506849315 [=229=]机器一年内计算[！ （如果每个排列都需要 100 毫秒，那么这个怪物的第 100 个）。
因此，您应该通过应用一些试探法而不是天真地列出所有可能的解决方案来减少问题的搜索 space。
将搜索 space 减少到更容易处理的数字后，例如：14！ （在 "one millisecond" 案例场景中计算时间为 2 年），您可以使用 Factoradics (an implementation here) to calculate the starting and ending permutation for every machine and then use the following code in every node (an implementation of the Knuth's L-algorithm 将计算拆分到多台机器上）以在每台机器上搜索解决方案：
public class Perm {
private static byte[] sequenceToMatch;
private static byte[] startSequence;
private static byte[] endingSequence;
private static final int SEQUENCE_LENGTH = 64;
public static void main(String... args) {
final int N = 3;
startSequence = readSequence(args[0]);
endingSequence = readSequence(args[1]);
sequenceToMatch = readSequence(args[2]);
permutations();
}
private static boolean sequencesMatch(byte[] s1, byte[] s2) {
for (int i = 0; i < SEQUENCE_LENGTH; i++) {
if (s1[i] != s2[i]) {
return false;
}
}
return true;
}
private static byte[] readSequence(String argument) {
String[] sBytes = argument.split(",");
byte[] bytes = new byte[SEQUENCE_LENGTH];
int i = 0;
for (String sByte : sBytes) {
bytes[i++] = Byte.parseByte(sByte, 10);
}
return bytes;
}
private static void swap(byte[] elements, int i, int j) {
byte temp = elements[i];
elements[i] = elements[j];
elements[j] = temp;
}
/**
* Reverses the elements of an array (in place) from the start index to the end index
*/
private static void reverse(byte[] array, int startIndex, int endIndex) {
int size = endIndex + 1 - startIndex;
int limit = startIndex + size / 2;
for (int i = startIndex; i < limit; i++) {
// swap(array, i, startIndex + (size - 1 - (i - startIndex)));
swap(array, i, 2 * startIndex + size - 1 - i);
}
}
/**
* Implements the Knuth's L-Algorithm permutation algorithm
* modifying the collection in place
*/
private static void permutations() {
byte[] sequence = startSequence;
if (sequencesMatch(sequence, sequenceToMatch)) {
System.out.println("Solution found!");
return;
}
// For every possible permutation
while (!sequencesMatch(sequence, endingSequence)) {
// Iterate the array from right to left in search
// of the first couple of elements that are in ascending order
for (int i = SEQUENCE_LENGTH - 1; i >= 1; i--) {
// If the elements i and i - 1 are in ascending order
if (sequence[i - 1] < sequence[i]) {
// Then the index "i - 1" becomes our pivot index
int pivotIndex = i - 1;
// Scan the elements at the right of the pivot (again, from right to left)
// in search of the first element that is bigger
// than the pivot and, if found, swap it
for (int j = SEQUENCE_LENGTH - 1; j > pivotIndex; j--) {
if (sequence[j] > sequence[pivotIndex]) {
swap(sequence, j, pivotIndex);
break;
}
}
// Now reverse the elements from the right of the pivot index
// (this nice touch to the algorithm avoids the recursion)
reverse(sequence, pivotIndex + 1, SEQUENCE_LENGTH - 1);
break;
}
}
if (sequencesMatch(sequence, sequenceToMatch)) {
System.out.println("Solution found!");
return;
}
}
}
}
我的目标是找到一个 64 字节数组的所有排列，并检查每个排列在执行函数 F 后是否等于给定的字节数组。
Consider a Small scale Example: Suppose I have 1234, I would like to generate all the permutations of a 4 digit number _ _ _ _ and check each time if it equals 1234
我的第一个想法是实现一个递归函数来生成排列。但是考虑到大小，栈会溢出。
有没有生成所有排列的有效方法？鉴于 Java 有大量图书馆？
至于非递归，这个答案可能有帮助：Permutation algorithm without recursion? Java
至于简单的例子，这里是我制定的递归解决方案：
public class Solution {
public List<List<Integer>> permute(int[] num) {
boolean[] used = new boolean[num.length];
for (int i = 0; i < used.length; i ++) used[i] = false;
List<List<Integer>> output = new ArrayList<List<Integer>>();
ArrayList<Integer> temp = new ArrayList<Integer>();
permuteHelper(num, 0, used, output, temp);
return output;
}
public void permuteHelper(int[] num, int level, boolean[] used, List<List<Integer>> output, ArrayList<Integer> temp){
if (level == num.length){
output.add(new ArrayList<Integer>(temp));
}
else{
for (int i = 0; i < num.length; i++){
if (!used[i]){
temp.add(num[i]);
used[i] = true;
permuteHelper(num, level+1, used, output, temp);
used[i] = false;
temp.remove(temp.size()-1);
}
}
}
}
}
编辑：10 似乎是递归方法在合理时间内完成的最大输入。
对于长度为 10 的输入数组：
Permutation execution time in milliseconds: 3380
编辑： 我快速搜索了可能的实现，并发现了一个建议的算法，作为对另一个问题的答案的一部分。
为了方便起见，下面是https://whosebug.com/users/2132573/jon-b开发的代码。 它正确地创建并打印了整数列表的所有排列。您可以轻松地对数组使用相同的逻辑（致谢 jon-b !!）。
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class HelloWorld {
public static int factorial(int x) {
int f = 1;
while (x > 1) {
f = f * x;
x--;
}
return f;
}
public static List<Integer> permute(List<Integer> list, int iteration) {
if (list.size() <= 1) return list;
int fact = factorial(list.size() - 1);
int first = iteration / fact;
List<Integer> copy = new ArrayList<Integer>(list);
Integer head = copy.remove(first);
int remainder = iteration % fact;
List<Integer> tail = permute(copy, remainder);
tail.add(0, head);
return tail;
}
public static void main(String[] args) throws IOException {
List<Integer> list = Arrays.asList(4, 5, 6, 7);
for (int i = 0; i < 24; i++) {
System.out.println(permute(list, i));
}
}
}
我已经在 http://www.tutorialspoint.com/compile_java8_online.php 中对其进行了测试，它运行良好。
希望对您有所帮助！
如果我没理解错的话，你需要生成所有的64！ 64 字节数组的排列，即：
64！ = 126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000 排列！
如果每次排列和比较都需要一毫秒（最坏情况下的时间场景）来计算，您将需要：
4023558225072430368576654912961741527234446859923426946943236123009091331506849.3150684931506849315 [=229=]机器一年内计算[！ （如果每个排列都需要 100 毫秒，那么这个怪物的第 100 个）。
因此，您应该通过应用一些试探法而不是天真地列出所有可能的解决方案来减少问题的搜索 space。
将搜索 space 减少到更容易处理的数字后，例如：14！ （在 "one millisecond" 案例场景中计算时间为 2 年），您可以使用 Factoradics (an implementation here) to calculate the starting and ending permutation for every machine and then use the following code in every node (an implementation of the Knuth's L-algorithm 将计算拆分到多台机器上）以在每台机器上搜索解决方案：
public class Perm {
private static byte[] sequenceToMatch;
private static byte[] startSequence;
private static byte[] endingSequence;
private static final int SEQUENCE_LENGTH = 64;
public static void main(String... args) {
final int N = 3;
startSequence = readSequence(args[0]);
endingSequence = readSequence(args[1]);
sequenceToMatch = readSequence(args[2]);
permutations();
}
private static boolean sequencesMatch(byte[] s1, byte[] s2) {
for (int i = 0; i < SEQUENCE_LENGTH; i++) {
if (s1[i] != s2[i]) {
return false;
}
}
return true;
}
private static byte[] readSequence(String argument) {
String[] sBytes = argument.split(",");
byte[] bytes = new byte[SEQUENCE_LENGTH];
int i = 0;
for (String sByte : sBytes) {
bytes[i++] = Byte.parseByte(sByte, 10);
}
return bytes;
}
private static void swap(byte[] elements, int i, int j) {
byte temp = elements[i];
elements[i] = elements[j];
elements[j] = temp;
}
/**
* Reverses the elements of an array (in place) from the start index to the end index
*/
private static void reverse(byte[] array, int startIndex, int endIndex) {
int size = endIndex + 1 - startIndex;
int limit = startIndex + size / 2;
for (int i = startIndex; i < limit; i++) {
// swap(array, i, startIndex + (size - 1 - (i - startIndex)));
swap(array, i, 2 * startIndex + size - 1 - i);
}
}
/**
* Implements the Knuth's L-Algorithm permutation algorithm
* modifying the collection in place
*/
private static void permutations() {
byte[] sequence = startSequence;
if (sequencesMatch(sequence, sequenceToMatch)) {
System.out.println("Solution found!");
return;
}
// For every possible permutation
while (!sequencesMatch(sequence, endingSequence)) {
// Iterate the array from right to left in search
// of the first couple of elements that are in ascending order
for (int i = SEQUENCE_LENGTH - 1; i >= 1; i--) {
// If the elements i and i - 1 are in ascending order
if (sequence[i - 1] < sequence[i]) {
// Then the index "i - 1" becomes our pivot index
int pivotIndex = i - 1;
// Scan the elements at the right of the pivot (again, from right to left)
// in search of the first element that is bigger
// than the pivot and, if found, swap it
for (int j = SEQUENCE_LENGTH - 1; j > pivotIndex; j--) {
if (sequence[j] > sequence[pivotIndex]) {
swap(sequence, j, pivotIndex);
break;
}
}
// Now reverse the elements from the right of the pivot index
// (this nice touch to the algorithm avoids the recursion)
reverse(sequence, pivotIndex + 1, SEQUENCE_LENGTH - 1);
break;
}
}
if (sequencesMatch(sequence, sequenceToMatch)) {
System.out.println("Solution found!");
return;
}
}
}
}