Find all permutations of 64 byte array?

Question

My aim is to find all permutations of a 64 byte array, and for each permutation check if after performing a function F, it is equal to given byte array.

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

My first thought was to implement a recursive function to generate the permutations. But considering the size, The stack will overflow.

Any efficient way to generate all the permutations? Given Java has large number of libraries?

Answer 1

If I understood correctly, you need to generate all the 64! permutations of a 64 byte array, that is:

64! = 126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000 permutations!

If every permutation and comparison takes one millisecond (worst case time scenario) to be calculated, you'll need:

4023558225072430368576654912961741527234446859923426946943236123009091331506849.3150684931506849315 years to calculate them all in one machine! (The 100th of this monstrosity if every permutation takes a 100th of a millisecond).

So, you should reduce the search space of your problem by applying some heuristics instead of naively listing all possible solutions.

After you reduce your search space to a more treatable number number, like for example: 14! (2 years of computation time in the "one millisecond" case scenario), you can split your calculations over several machines by using 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) to search the solution in every machine:

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;
            }
        }
    }
}