Algorithm to calculate values based on linear equations

Question

I am working to calculate values of various Paycodes in a PayStructure based on linear equations using java. My different equations are as below:

CTC = Fixed Value
Basic = CTC * 0.4
HRA = Basic/2
ConveyanceAllowance = Fixed Value
ProvidentFund = Basic * 0.12
Gratuity = Basic * .0481
OtherAllowance = (CTC - (Basic + HRA + ConveyanceAllowance + ProvidentFund + Gratuity))

I have tried using the solution given here. But this solution will only work in case all the calculated values are integers and in my case, the values could contain decimal figures as well. My modified code as per the above conditions is as below:

public class PayStructure {

    public static void main(String[] args) {
        findAndprintSolutions(1, 1000000);
    }

    private static void findAndprintSolutions(int from, int to) {
        for (int a = from; a < to; a++) {
            for (int b = from; b < to; b++) {
                for (int c = from; c < to; c++) {
                    for (int d = from; d < to; d++) {
                        for (int e = from; e < to; e++) {
                            for (int f = from; f < to; f++) {
                                for (int g = from; g < to; g++) {
                                    if (isSolution(a, b, c, d, e, f, g))
                                        printSolution(new int[] { a, b, c, d, e, f, g });
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    private static boolean isSolution(int a, int b, int c, int d, int e, int f, int g) {
        if (a != 100000)
            return false;
        if (b != a * (.4))
            return false;
        if (c != b / 2)
            return false;
        if (d != 10000)
            return false;
        if (e != b * (.12))
            return false;
        if (f != b * (.0481))
            return false;
        if (g != (a - (b + c + d + e + f)))
            return false;
        return true;
    }

    private static void printSolution(int[] variables) {
        StringBuilder output = new StringBuilder();
        for (int variable : variables) {
            output.append(variable + ", ");
        }
        output.deleteCharAt(output.length() - 1);
        output.deleteCharAt(output.length() - 1);
        System.out.println(output.toString());
    }

}

Moreover the above mentioned code will be terminated as the maximum value of CTC could be millions and depending on the number of variables, time complexity will end up to be millions^NumberOfVariables. Is there any other possibility to calculate the values based on the given equations? The number of equations and variables could vary but there will be a solution to calculate value of each variable, so any inputs for a generic solution would be better.

E.g.: If CTC = 100000 and ConveyanceAllowance = 10000, the code should return the output as:
Basic = 40000
HRA = 20000
ProvidentFund = 4800
Gratuity = 1924
OtherAllowance = 23276

Answer 1

Maybe your best bet would be to figure out how to get this into the form of a system of linear equations of the form c[1]x[1] + c[2]x[2] … + c[n]x[n] = 0. From there, you can solve the system using widely established techniques for linear systems. See the Wikipedia page for lots of information. You could either have the users provide input to your method in this form, or you could do a small amount of processing on each equation to transform it (e.g., if all the equations have one variable on the LHS as in your example, flip the sign and put it on the end of the RHS).

Explaining the theory of solving a system of linear equations is beyond the scope of this answer but, basically, your system will either be uniquely determined if there is one valid assignment, overdetermined if no valid assignment exists, or underdetermined if infinitely many assignments are possible. If there is a unique assignment you will get numbers; if the system is underdetermined you'll at least get a set of constraints that must hold of any of the infinitely many solutions; if underdetermined, you'll get nothing and know why.

Answer 2

Use the some linear algebra library for Java. Solve the system of linear equations using matrix operations as documented here, for instance. Your deeply nested loop is too slow, there are much better algorithms available.

Answer 3

This is how I solved this. Firstly I created equations by taking all the variables to the left side and values & 0 to the right side:

CTC = 1000000
(0.4)CTC - Basic = 0
(0.5)Basic-HRA = 0
ConvAll = 10000
(0.12)Basic-PF = 0
(0.0481)Basic - Gratuity = 0
CTC - (Basic + HRA + ConvAll + PF+ Gratuity + OtherAll) = 0

Then I created a matrix like this:

|1          0     0    0   0   0   0| |CTC     | = |1000000|
|0.4       -1     0    0   0   0   0| |Basic   | = |0      |
|0         0.5   -1    0   0   0   0| |HRA     | = |0
|0          0     0    1   0   0   0| |ConvAll | = |10000  |
|0         0.12   0    0  -1   0   0| |PF      | = |0      |
|0        0.0481  0    0   0  -1   0| |Gratuity| = |10000  |
|1         -1    -1   -1  -1  -1  -1| |OtherAll| = |0      |

After this, I calculated the product of (inverse of above 1st matrix) and (right most matrix) and got the corresponding values of each component using the below code:

public class Matrix

{
    static int n = 0;

    public static void main(String argv[]) {
        Scanner input = new Scanner(System.in);
        System.out.println("Enter the dimension of square matrix: ");

        n = input.nextInt();
        double a[][] = new double[n][n];
        System.out.println("Enter the elements of matrix: ");
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                a[i][j] = input.nextDouble();
        double d[][] = invert(a);
        System.out.println();
        System.out.println("Enter the equation values: ");
        System.out.println();
        double b[][] = new double[n][1];
        for (int i = 0; i < n; i++) {
            b[i][0] = input.nextDouble();
        }

        double e[][] = multiplyMatrix(d, b);
        System.out.println();
        System.out.println("The final solution is: ");
        System.out.println();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 1; j++) {
                System.out.printf(e[i][j] + " ");
            }
            System.out.println();
        }
        input.close();
    }

    public static double[][] invert(double a[][]) {
        int n = a.length;
        double x[][] = new double[n][n];
        double b[][] = new double[n][n];
        int index[] = new int[n];
        for (int i = 0; i < n; ++i)
            b[i][i] = 1;

        // Transform the matrix into an upper triangle
        gaussian(a, index);

        // Update the matrix b[i][j] with the ratios stored
        for (int i = 0; i < n - 1; ++i)
            for (int j = i + 1; j < n; ++j)
                for (int k = 0; k < n; ++k)
                    b[index[j]][k] -= a[index[j]][i] * b[index[i]][k];

        // Perform backward substitutions
        for (int i = 0; i < n; ++i) {
            x[n - 1][i] = b[index[n - 1]][i] / a[index[n - 1]][n - 1];
            for (int j = n - 2; j >= 0; --j) {
                x[j][i] = b[index[j]][i];
                for (int k = j + 1; k < n; ++k) {
                    x[j][i] -= a[index[j]][k] * x[k][i];
                }
                x[j][i] /= a[index[j]][j];
            }
        }
        return x;
    }

    // Method to carry out the partial-pivoting Gaussian

    // elimination. Here index[] stores pivoting order.

    public static void gaussian(double a[][], int index[]) {
        int n = index.length;
        double c[] = new double[n];

        // Initialize the index
        for (int i = 0; i < n; ++i)
            index[i] = i;

        // Find the rescaling factors, one from each row
        for (int i = 0; i < n; ++i) {
            double c1 = 0;
            for (int j = 0; j < n; ++j) {
                double c0 = Math.abs(a[i][j]);
                if (c0 > c1)
                    c1 = c0;
            }
            c[i] = c1;
        }

        // Search the pivoting element from each column
        int k = 0;

        for (int j = 0; j < n - 1; ++j) {
            double pi1 = 0;
            for (int i = j; i < n; ++i) {
                double pi0 = Math.abs(a[index[i]][j]);
                pi0 /= c[index[i]];
                if (pi0 > pi1) {
                    pi1 = pi0;
                    k = i;
                }
            }

            // Interchange rows according to the pivoting order
            int itmp = index[j];
            index[j] = index[k];
            index[k] = itmp;
            for (int i = j + 1; i < n; ++i) {
                double pj = a[index[i]][j] / a[index[j]][j];
                // Record pivoting ratios below the diagonal
                a[index[i]][j] = pj;
                // Modify other elements accordingly
                for (int l = j + 1; l < n; ++l)
                    a[index[i]][l] -= pj * a[index[j]][l];
            }
        }
    }

    public static double[][] multiplyMatrix(double a[][], double b[][]) {
        double c[][] = new double[n][1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 1; j++) {
                for (int k = 0; k < n; k++) {
                    c[i][j] = c[i][j] + a[i][k] * b[k][j];
                }
            }
        }
        return c;
    }
}

Thank you all for the leads.