Nonrecursively generating all possible permutations of elements from two arrays

Question

I'm trying to generate all possible equations given an String array of operators (+,-,*,/) and an String array of variables (a,b,c ...). Each equation will be composed of pairs of variables and numbers (a+ b- c/ b), except the last variable, which has no operator following it. The algorithm must generate equations of variable lengths (2 terms, 6 terms, etc). What would be the most efficient way to generate this list in Java?

Please, don't do it recursively. :)

Um, no this is not homework. Its a personal project where I'm trying to utilize genetic algorithms to find optimal equations to fit data. A description of an algorithm in general terms would suffice if you believe so.

Answer 1

I think this is pretty language-agnostic. Is this homework? It sounds like homework, so I won't give you an example, but I would use 3 while loops (although you could just as easily use for loops, I simply prefer using whiles).

Answer 2

Since i also think this might be homework, I'm not giving you the code in any language but...

You can have two nested loops, one to loop through array one and the other to loop through array two.

You will see that every index combined will pass through the inner loop, and you can do your math there.

Answer 3

Since you say its not homework, and I'm a trusting fellow...

1. Build a new array of variable-operator combinations by running each variable against the operator array => ["a+", "a-", "a*", "a/", "b+" ... "d/"]. We'll call this BuiltArray1

2. Run this array against the operators, outputing each and also storing each in a new array => ["a+a", "a+b", "a+c", "a+d", "a-a" ..."d/d"]. We'll call this BuiltArray2. We can delete the original variable array ["a, "b", "c", "d"] now if we care to - we won't use it again.

3. Now things get more fun... now we are building BuiltArray3. Run each item in BuiltArray1 against each item in BuiltArray2, outputting each and storing each in BuiltArray3 => ["a+a+a", "a-a+a", "a*a+a", "a/a+a", "b+a+a" ... "d/d/d"]. We can now delete BuiltArray2 to save some memory (this will start to consume memory quickly!)

4. For BuiltArray4 until our computer dies screaming on the last BuiltArray_n it can handle, we run each item in BuiltArray1 against the previously built array, outputting and also storing each result in a new array, then deleting the previous array.

This will chew through memory and processing power, but I can't think of anything more graceful off of the top of my head.

Hope it helps.

---

Here's Ruby codez:

@arr1 = ["a", "b", "c", "d"]
arr2 = ["+", "-", "*", "/"]
@base = []
@arr1.each do |char|
  arr2.each do |op|
    @base << char + op
  end
end
@right_vals = @arr1
loop do
  @new_values = []
  @base.each do |left|
    @right_vals.each do |right|
      val = left + right
      puts val
      @new_values << val
    end
  end
  @right_vals = @new_values
end

Answer 4

So here is the code I've come up with. I'm using a single LinkedList to store the equations that I've generated. I generate all possible pairs of operators and variables, and then append them to the solutions that I've already generated to come up with new solutions. Is there a better/faster way of doing this?

LinkedList<String> solutions = new LinkedList<String>();
//String[] vars and operators are initialized elsewhere.
int start = 0, end = solutions.size()-1;

//creating the first solutions
for(String s : vars)
    solutions.add(s);


//precompute pairs of operators and variables
String[] pairs = new String[operators.length * vars.length];
for(int i=0, j=0; j<operators.length; j++)
for(int k=0; k<vars.length; k++)
{
 pairs[i++]= operators[j]+vars[k];
}

//while the the terms in equations is under maximum
while(solutions.get(solutions.size()-1).split("[+/*-]").length<4)
{
    for(int i=start; i<end; i++)
    {
     String soln = solutions.get(i);
     for(int j=0; j<pairs.length; j++)
     {
      solutions.add(soln+pairs[j]);
     } 
    }
    start = end +1;
    end = solutions.size()-1;
}

Answer 5

This isn't in Java, and its recursive, but as a matter of interest the Haskell solution looks like this:

permuteEquations :: Int -> [String] -> [String] -> [String]
permuteEquations 1 vars _ = vars
permuteEquations n vars ops = 
    [v ++ t1 | t1 <- [o ++ t2 | t2 <- permuteEquations (n-1) vars ops, o <- ops],
               v  <- vars]

This generates all possible equations containing n variables.

Alternatively if you want a version that starts with equations of one variable (i.e. the list of variables) and then works its way up to n variables then it is:

permuteEquations1 :: Int -> [String] -> [String] -> [String]
permuteEquations1 0 _ _ = []
permuteEquations1 n vars ops = 
    [v ++ t1 | t1 <- "" : [o ++ t2 | t2 <- permuteEquations1 (n-1) vars ops, 
                                     o  <- ops], 
               v  <- vars]

Thanks to lazy evaluation these functions run in constant space, which is handy if you are generating billions of equations. Does anyone know how would you do that in Java? (I'm sure its possible, I'm just curious to see what it looks like).

Actually, thanks to lazy evaluation you can get rid of the n term and generate an infinite list which the client truncates to whatever length it needs.

permuteEquations2 :: [String] -> [String] -> [String]
permuteEquations2 vars ops = 
    [v ++ t1 | t1 <- "" : [o ++ t2 | t2 <- permuteEquations2 vars ops, o <- ops], 
               v  <- vars]

Answer 6

The run time grown exponentially with the number of variables. Here is another approach.

import java.util.List;
import java.util.ArrayList;

public class Equations {
    public static void main(String[] args) {
        String[] operators = "+ - * / %".split(" ");
        String[] variables = "a b c d e f g".split(" ");
        printAllPermutations(operators, variables);
    }

    private static void printAllPermutations(String[] operators, String[] variables) {
        if (variables.length >= 31)
            throw new IllegalArgumentException("Need to use BigInteger to support such a large number variables.length="+variables.length);

        int permuations = 1 << variables.length;
        for(int p=1;p<permuations;p++) {
            List<String> variableList = new ArrayList<String>();
            int p2 = p;
            for (String variable : variables) {
                if ((p2 & 1) != 0)
                    variableList.add(variable);
                p2 /= 2;
            }
            printPermutations(operators, variableList.toArray(new String[variableList.size()]));
        }
    }

    private static void printPermutations(String[] operators, String[] variables) {
        long permutations = 1;
        // more accurate than Math.pow.
        for (int i = 0; i < variables.length-1; i++) {
            String variable = variables[i];
            permutations *= operators.length;
        }
        for(long p = 0; p < permutations;p++) {
            long p2  = p;
            for (int i = 0; i < variables.length-1; i++) {
                System.out.print(variables[i]);
                int oper = (int) (p2 % operators.length);
                System.out.print(operators[oper]);
                p2 /= operators.length;
            }
            System.out.println(variables[variables.length-1]);
        }
    }
}