Is there a way to allow for the number of for loops and array elements to be variable in algorithm? - java

Question

Currently writing a program that finds the optimal ratio of 3 given numbers in an array. However the code I have currently only takes 3 numbers and arranges them to find the closest 3 number arrangement to 100. I need the code to be adaptable so that it takes the 3 numbers and gives the n number arrangement closest to 100.

public static int[] mmru(int[] array) {
    int result = 1000;
    int[] ideal = new int[0];
    int closestResult = 100;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                result = 100 - array[i] - array[j] - array[k];
                if (result == 0) {
                    ideal = new int[]{array[i], array[j], array[k]};
                    return ideal;
                } else {
                    if (result < closestResult && result > 0) {
                        ideal = new int[]{array[i], array[j], array[k]};
                        closestResult = result;
                    }
                }

            }
        }
    }
    return ideal;
}

the solution I have right now is to manually add more for loops and array elements.

Example - an array of 3 numbers, outputs arrangement of 8 numbers using the 3 numbers to get closest to 100. eg. [8,13,15] gives output of [8,8,13,13,13,15,15,15]

public static int[] mmrh8(int[] array) {
    int result = 1000;
    int[] ideal = new int[0];
    int closestResult = 100;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                for (int l = 0; l < 3; l++) {
                    for (int m = 0; m < 3; m++) {
                        for (int n = 0; n < 3; n++) {
                            for (int o = 0; o < 3; o++) {
                                for (int p = 0; p < 3; p++) {
                                    result = 100 - array[i] - array[j] - array[k] - array[l] - array[m] - array[n] - array[o] - array[p];
                                    if (result == 0) {
                                        ideal = new int[]{array[i], array[j], array[k], array[l], array[m], array[n], array[o], array[p]};
                                        return ideal;
                                    } else {
                                        if (result < closestResult && result > 0) {
                                            ideal = new int[]{array[i], array[j], array[k], array[l], array[m], array[n], array[o], array[p]};
                                            closestResult = result;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return ideal;
}

Is there a way to allow for the number of for loops and array elements to be variable?

Any help appreciated thanks!

Answer 1

As pointed out in the comments there might be a far more efficient solution to this problem, but if you want to keep your brute force approach of trying all possible combinations, heres how it can be done:

What your for-loops do is effectively giving all possible combinations of all 8 digit numbers with only digits 0, 1 and 2, which are then used as indices in your given number array. So you need to calculate those. This can be done by enumerating them:

0: 00000000
1: 00000001
2: 00000002
3: 00000010
4: 00000011
5: 00000012
6: 00000020
...
6561 (3^8): 22222222

which is the equivalent of interpreting the counter as a number in the ternary system (or any different number system, depending on the amount of given numbers). The digits of that number can then be calculated using this answer, swapping out the 10 for the 3 for the ternary system.

This results in the following code to get all possible index combinations:

// the length of the input array
int base = 3;
// must have same length as desired result length
int[] indexArray = new int[8];

// there are base to the power of length possible combinations
for (int counter = 0; counter < Math.pow(base, indexArray.length); counter++) {
  // retrieve digits as in linked answer
  int counterCopy = counter;
  for (int i = 0; i < indexArray.length; i++) {
    indexArray[i] = counterCopy % base;
    counterCopy /= base;
  }
  
  // insert your code, indexArray[0] is your "i", indexArray[1] is your "j" and so on
  System.out.println(Arrays.toString(indexArray));
}

Answer 2

Here is one way.

The idea is to generate a series of indices that will reference the candidates that make up the sum. For example:

• Give the number of elements in the final array is 8 - called maxElements
• the list of candidates for filling the array is {8,13,15}

Then generate an array of indices from 0,0,0 to 7,7,7. So [1,3,4] would say use one 8, three 13's and four 15's. Notice that it is important for the count sum to equal the maxElements. So 1 + 3 + 4 = 8. The creation of the indices array and maintaining a count is taken care of in the update method which returns the current count of indices. If that count does not match the maxElement value, it is not used to populate the resultArray.

The result array is updated and is saved based on the whether or not the current computed array is closer to the targetSum.

A record is used to house and return the final values. A regular class could also be used.

record Results(int sum, int[] array) {
    @Override
    public String toString() {
        return String.format("sum = %d : %s", sum,
                Arrays.toString(array));
    }
}

A sample run.

int[] candidates = { 8, 13, 15};
for (int maxElements = 1; maxElements < 10; maxElements++) {
    Results result = bestSum(100, maxElements, candidates);
    System.out.println(result);
}

prints

sum = 15 : [15]
sum = 30 : [15, 15]
sum = 45 : [15, 15, 15]
sum = 60 : [15, 15, 15, 15]
sum = 75 : [15, 15, 15, 15, 15]
sum = 90 : [15, 15, 15, 15, 15, 15]
sum = 101 : [13, 13, 15, 15, 15, 15, 15]
sum = 100 : [8, 8, 13, 13, 13, 15, 15, 15]
sum = 100 : [8, 8, 8, 8, 8, 15, 15, 15, 15]

The update method to build the indices array and maintain and return the sum of the indices.

public static int update(int[] indices, int prevSum,
        int maxElements) {
    maxElements++;
    for (int i = indices.length - 1; i >= 0; i--) {
        indices[i]++;
        prevSum++;
        if (indices[i] < maxElements) {
            return prevSum;
        }
        prevSum -= indices[i];
        indices[i] = 0;
    }
    return prevSum;
}

The main method to compute the best sum

public static Results bestSum(int targetSum, int maxElements,
        int[] candidates) {
    
    int delta = Integer.MAX_VALUE;
    int[] saveResultArray = new int[maxElements];
    int[] indicesArray = new int[candidates.length];
    int i = maxElements;
    int totalIndices = 0;
    for (int v = 1;
            v < Math.pow(maxElements+1,candidates.length); v++) {

        totalIndices = update(indicesArray, totalIndices, maxElements);
    
        // is the indices array usable, if not, ignore.
        if (totalIndices != maxElements) {
            continue;
        }
        
        int[] resultArray = new int[maxElements];
        int nn = 0;
        int tempSum = 0;
        // iterate over the indices Array.  For each value
        // add that many of the candidates array to the result array.
        
        for (int k = 0; k < indicesArray.length; k++) {
            for (int j = 0; j < indicesArray[k]; j++) {
                resultArray[nn++] = candidates[k];
                tempSum += candidates[k];
            }
        }
        // based on differences of previous computations,
        // update the differences and save the result array accordingly.
        
        if (tempSum == targetSum) {
            delta = 0;
            saveResultArray = resultArray;
            break;
        }
        int diff = tempSum - targetSum;
        if (Math.abs(diff) < Math.abs(delta)) {
            saveResultArray = resultArray;
            delta = diff;
        }
    }
    return new Results(targetSum + delta, saveResultArray);
}

This is a brute force algorithm where many values are computed only to be ignored. And the algorithm slows considerably as the candidate's list grows since that will increase the loop iterations.

Answer 3

From your example, it appears that your solution should represent three multiplication factors, to be applied to three values given in an array. You want the sum of the products of those three factors against the given array values to be closest to 100.

So, if you're given three values v[0], v[1], and v[2], you wish to solve for a, b, and c such that result of the following formula is closest to 100:

a * v[0] + b * v[1] + c * v[2]

Rather than build your entire array, just solve for those three values.

int maxUnder100=0;
int minOver100=99999;
for (int a=0; a<=100/v[0]+1; a++) {
    for (int b=0; b<=100/v[1]+1; b++) {
        for (int c=0; c<=100/v[2]+1; c++) {
            int calc=a*v[0]+b*v[1]+c*v[2];
            if (calc>=100 && calc<maxUnder100) {
                maxUnder100=calc;
                // store your best max solution somehow
            }
            if (calc<=100 && calc>minOver100) {
                minOver100=calc;
                // store your best min solution somehow
            }
        }
    }
}

Once you have those multiplication factors, it should be trivial to represent your final array of values.

Note: I got a little fancy in the max values of each for loop, but there's certainly room for improvement.