Нерекурсивное генерирование всех возможных перестановок элементов из двух массивов

Question

Я пытаюсь сгенерировать все возможные уравнения с помощью массива String операторов (+, -, *, /) и массива String переменных (a, b, c. ..). Каждое уравнение будет состоять из пар переменных и чисел (a + b-c/b), за исключением последней переменной, которая не имеет оператора, следующего за ней. Алгоритм должен генерировать уравнения переменной длины (2 члена, 6 членов и т. Д.). Каким будет наиболее эффективный способ создания этого списка на Java?

Пожалуйста, не делайте это рекурсивно. :)

Ум, нет, это не домашнее задание. Это личный проект, в котором я пытаюсь использовать генетические алгоритмы, чтобы найти оптимальные уравнения для соответствия данным. Описание алгоритма в общих терминах было бы достаточно, если вы так считаете.

Answer 1

Я думаю, что это довольно язык-агностик. Это домашнее задание? Это звучит как домашнее задание, поэтому я не буду приводить вам пример, но я бы использовал три петли while (хотя вы могли бы так же легко использовать петли for, я просто предпочитаю использовать while s).

Answer 2

Поскольку я также думаю, что это может быть домашнее задание, я не даю вам код на любом языке, но ...

Вы можете иметь два вложенных цикла, один цикл по массиву один, а другой петли через массив два.

Вы увидите, что каждый объединенный индекс пройдет через внутренний цикл, и вы сможете выполнять свою математику там.

Answer 3

Так вы говорите, его не домашнее задание, и я доверчивый парень ...

1. Построить новый массив комбинаций переменного оператора, запустив каждый переменный от массива оператора => [ "а + "," a "," a * "," a/"," b + "..." d/"]. Мы будем называть это BuiltArray1

2. Запустите этот массив против операторов, выводя каждый из них, а также сохраняя каждый в новом массиве => ["a + a", "a + b", "a + c", " a + d "," aa "..." d/d "]. Мы будем называть это BuiltArray2. Мы можем удалить исходный массив переменных [«a», «b», «c», «d»], если мы позаботимся - мы больше не будем его использовать.

3. Теперь все становится веселее ... теперь мы строим BuiltArray 3. Запускаем каждый элемент в BuiltArray1 по каждому элементу в BuiltArray2, выводя каждый и сохраняя каждый в BuiltArray3 => ["a + a + a", "a-a + a", "a * a + a" , "a/a + a", "b + a + a" ... "d/d/d"]. Теперь мы можем удалить BuiltArray2 для сохранения некоторой памяти (это быстро начнет потреблять память!)

4. Для BuiltArray4, пока наш компьютер не закричит на последнем BuiltArray_n, который может обрабатывать, мы запускаем каждый элемент в BuiltArray1 против ранее построенного массива, выводя и сохраняя каждый результат в новом массиве, а затем удаляя предыдущий массив.

Это проглотит память и вычислительную мощность, но я не могу придумать ничего более изящного от верхней части головы.

Надеюсь, это поможет.

---

Вот Рубин 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

Так вот код, который я придумал.Я использую единственный LinkedList для хранения уравнений, которые я создал. Я генерирую все возможные пары операторов и переменных, а затем добавляю их к решениям, которые я уже создал, чтобы придумывать новые решения. Есть ли лучший/более быстрый способ сделать это?

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

Это не в Java, и его рекурсивный, но для интереса решение Haskell выглядит следующим образом:

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] 

Это порождает все возможные уравнения, содержащие п переменных.

В качестве альтернативы, если вы хотите версию, которая начинается с уравнений одной переменной (т.е. список переменных), а затем работает свой путь до п переменных, то это:

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] 

Благодаря ленивым вычислениям эти функции выполняются в постоянном пространстве, что удобно, если вы генерируете миллиарды уравнений. Кто-нибудь знает, как вы это сделаете на Java? (Я уверен, что это возможно, мне просто интересно посмотреть, как это выглядит).

На самом деле, благодаря ленивой оценке, вы можете избавиться от термина «n» и создать бесконечный список, который клиент усекает до любой требуемой длины.

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

Answer 6

Время выполнения выращено экспоненциально с количеством переменных. Вот еще один подход.

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

Answer 7

Java- дано наборов, первый для операндов, должны быть применены на втором наборе номера, то мы оцениваем генерироваться выражение с заданным значением.

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