# Using brute force to do large scale permutations and combinations

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++)
}
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();
}
}

• This mathematics problem sound complicated. Not that there's anything wrong with that. However, for complicated problems it can be good to explain them well. As an example, see a previous question of mine. You might also be interested in reading my recommendations for how to ask a good question – Simon Forsberg Sep 25 '16 at 11:33

### 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)
{
for (int i=0; i<16; i+=4) {
int digit = (val >> i) & 0xf;
}
}

// 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]);


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.