Non-recursive creation of all possible permutations of elements from two arrays

Since you say this is not homework and I am a trusting person ...

• Create a new array of operator variable combinations by running each variable into an operator array => ["a +", "a-", "a *", "a /", "b +" ... "d /"]. We will call this BuiltArray1

• Run this array against operators, outputting each one, and also store them in a new array => ["a + a", "a + b", "a + c", "a + d" "aa" ... "d / d"]. We will call this BuiltArray2. We can delete the original array of variables ["a," b "," c "," d "] now if we want - we won't use it anymore.

• Now things are getting more fun ... now we are building BuiltArray3. Run each item in BuiltArray1 on each item in BuiltArray2, unload each and store each in BuiltArray3 => ["a + a + a", "aa + a", "a * a + a", "a / a + a" , "b + a + a" ... "d / d / d"]. We can now remove BuiltArray2 to save some memory (this will quickly start to consume memory!)

• For BuiltArray4, until our computer screams at the last BuiltArray_n it can handle, we fire each item in BuiltArray1 against the previously created array, outputting and storing each result in a new array, then deleting the previous array.

It will swallow memory and processing power, but I can't think of anything more graceful from the top of my head.

Hope it helps.

Here's the 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

      

        
        
        
      

    

This is not in Java, but in recursive, but an interesting 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. a list of variables) and then runs up to n variables, then this 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]

      

        
        
        
      

    

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

In fact, thanks to lazy evaluation, you can get rid of the nth term and create an infinite list that 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]

      

        
        
        
      

    

The execution time is exponential with the number of variables. Here's 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]);
        }
    }
}

      

        
        
        
      

    

Javascript given to the sets, the first for the operands is applied to the second set of numbers, then we evaluate the generated expression with the target value.

var targetValue=10;
var set=[2,4,8,16,64];
//var ops=['+','-', '/', '*'];

var retArray=new Array();

function permutateSigns(operand, numbers, pos, epx){

        var sum = 0;
        if (pos == numbers.length-1) {
            epx += numbers[pos];
            //console.log(epx);
            retArray.push(epx);
        } else {
            epx += (numbers[pos]) + operand;
            permutateSigns('+', numbers, pos + 1, epx);
            permutateSigns('-', numbers, pos + 1, epx);
            permutateSigns('*', numbers, pos + 1, epx);
            permutateSigns('/', numbers, pos + 1, epx);
        }
    }
permutateSigns('+',set,0,"");
var per=retArray;
console.log(per);

var validExpr;
for (var i = 0; i < retArray.length; i++) {
    var result=eval(retArray[i]);

    if(result===targetValue)
        validExpr= retArray[i];
    else
     console.log(retArray[i] + ":" + eval(retArray[i]));
}
console.log("valid expression is:" + validExpr + "; value:"+ eval(validExpr) + "number of permutations is:"+ retArray.length);