Using brute force to do large scale permutations and combinations

Question

This problem should self explanatory based on namings of variables and functions. In essence I am doing well over 720*720*90 checks/calculations. Hence, this is taking far, far too long. How do I make my code more optimized with regards to time/performance. Space is not an issue. The question is pretty complicated(at least in my opinion), so please let me know what I should clarify.

Most of the optimization should be doable by just reading my comments, I hope. I don't want to bog down the task by adding in details of the convoluted math problem.

import java.io.*;
import java.util.*;
import java.lang.*;

public class Concat{
    static String[] designs = new String[720]; //6! permutations of 6 unique characters
    static int index = 0; //index used to iterate through designs[]

    public static void main(String[] args){
        Concat concat = new Concat();
        genDesigns("", "123456"); //123456 will be the unique characters

        String[][] interleavedData = new String[720][720]; 
        for(int i = 0; i < 720; i++)
            interleavedData[i] = //remap using design[i]

        String[][] interleavedSubsets = new String[720][90];
        for(int interleaveIndex = 0; interleaveIndex < 720; interleaveIndex++)
        {
            for(int j = 0; j < 720; j++)
                interleavedSubsets[j] = gen8String(genDelPatterns(designs[j]), genDelPatterns(interleavedData[interleaveIndex][j]));

            System.out.println(checkSubsets(interleavedSubsets));
        }

    }

    //generate all permutations 
    public static void genDesigns(String prefix, String data){
        int n = data.length();
        if (n == 0) designs[index++] = prefix;
        else {
            for (int i = 0; i < n; i++)
                genDesigns(prefix + data.charAt(i), data.substring(0, i) + data.substring(i+1, n));
        }
    }

    public static String[] genDelPatterns(String design){
        //stimulating 6choos4 operation
    }

    //generating a subset of 90 eight character strings (unique deletion patterns)
    public static String[] gen8String(String[] pattern1, String[] pattern2){
        String[] combinedSubset = new String[90]; //emty array for the subset of 90 strings
        String  combinedString = ""; //string holder for each combined string
        int index = 0; //used for combinedSubset array
        int present = 0; //used to check if all 6 characters are present

        for(int i = 0; i < 15; i++){

            for(int j = 0; j < 15; j++){
                combinedString = pattern1[i] + pattern2[j]; //combine both 4 letter strings into 8 char length string
                char[] parsedString = combinedString.toCharArray(); //parse into array

                //check if all 6 characters are present
                for(int k = 1; k <= 6; k++)
                {
                    if(new String(parsedString).contains(k+"")) {
                        present++;
                    }
                    else
                        break;
                    //if all 6 are present, then add it to combined subset
                    if(present == 6)
                        combinedSubset[index++] = combinedString;
                }
                present = 0;
            }
        }
        return combinedSubset;
    }

    //check all the subsets of the interleaved data
    public static int checkSubsets(String[][] subsets){
        List subset = new ArrayList();
        int numOfUnique = 0;
        for(int i = 0; i< 720; i++){
            for(int j = 0; j < 90; j++)
                subset.add(subsets[i][j]);
        }
        Object duplicate; 
        Iterator itr = subset.iterator();
        while(itr.hasNext()){
            duplicate = itr.next();
            while(itr.hasNext()){
                subset.remove(duplicate);
                itr=subset.iterator(); //to avoid concurrent modification
                itr.next();
            }
        }
        return subset.size();
    }
}

Answer 1

Use integers instead of strings

I don't really understand the problem you are trying to solve, so I don't know if your algorithm can be improved. But I can see that your program spends a lot of time creating and modifying strings that are between 4 and 8 characters long, containing the letters '1' .. '6'.

Instead of using strings, you could use an integer to represent your string. Simply use the hex representation as your integer value. For example, instead of the string "123456", use the int 0x123456.

Integers are more compact than strings, and operations on integers are faster than string operations. As an example of how to build an integer as opposed to a string, this:

 sb.append(String.valueOf(data[k]));

would become this:

// Assumes k loop goes from 5 to 0 instead of 0 to 5:
val = (val << 4) | ((data >> k) & 0xf);

More efficient check for all characters present

One function that appears to be where much of the time is spent is gen8string(), and within that function the inner loop does this:

    for(int i = 0; i < 15; i++){

        for(int j = 0; j < 15; j++){
            combinedString = pattern1[i] + pattern2[j]; //combine both 4 letter strings into 8 char length string
            char[] parsedString = combinedString.toCharArray(); //parse into array

            //check if all 6 characters are present
            for(int k = 1; k <= 6; k++)
            {
                if(new String(parsedString).contains(k+"")) {
                    present++;
                }
                else
                    break;
                //if all 6 are present, then add it to combined subset
                if(present == 6)
                    combinedSubset[index++] = combinedString;
            }
            present = 0;
        }
    }

There are several inefficiencies, such as concatenating pattern1[i] and rechecking its characters when they could be checked in the outer loop only. If you converted to integers, you could do this check like this:

// Returns bitmask of numbers present in a 4 digit value
public static int presentBits(int val)
{
    int presentMask = 0;
    for (int i=0; i<16; i+=4) {
        int digit = (val >> i) & 0xf;
        presentMask |= 1 << digit;
    }
    return presentMask;
}

    // Within get8string()...
    for (int i = 0; i < 15; i++) {
        int present1 = presentBits(pattern1[i]);
        for (int j = 0; j < 15; j++) {
            int presentMask = present1 | presentBits(pattern2[j]);

            if (presentMask == 0x7e) {
                // 0x7e is binary 01111110, which means each of
                // the digits 1 through 6 was seen at least once.
                combinedSubset[index++] = (pattern1[i] << 16) |
                                           pattern2[j]
            }
        }
    }

Checking subsets

Another heavily called function is checkSubsets(), which appears to just count the number of unique strings among an array of 720x90 strings. It does so with an \$O(n^2)\$ duplicate removal algorithm. You could do better by sorting the strings (or integers preferably) and then counting uniques in one pass. Even faster would be to add all the strings to a HashSet, which naturally removes duplicates. The sorting method takes \$O(n \log n)\$ time, and the HashSet method takes \$O(n)\$ time.