algorithm - prim - Cálculo del número objetivo a partir de números en un conjunto

prim''s algorithm

Question

Estoy trabajando en un problema de tarea que me pregunta esto:

Para obtener un conjunto finito de números y un número objetivo, busque si el conjunto se puede usar para calcular el número objetivo mediante operaciones matemáticas básicas (sumar, sub, mult, div) y usar cada número en el conjunto exactamente una vez (así que necesito para agotar el conjunto). Esto tiene que hacerse con recursión.

Así, por ejemplo, si tengo el set

{1, 2, 3, 4}

y el objetivo 10, entonces podría llegar usando

((3 * 4) - 2)/1 = 10. 

Estoy tratando de expresar el algoritmo en pseudocódigo, pero hasta ahora no he llegado demasiado lejos. Estoy pensando que las gráficas son el camino a seguir, pero definitivamente agradecería ayuda en esto. Gracias.

Answer 1

Antes de pensar en cómo resolver el problema (como con los gráficos), realmente ayuda simplemente a mirar el problema. Si te encuentras atrapado y no puedes encontrar ningún pseudocódigo, lo más probable es que haya algo que te esté frenando; Alguna otra pregunta o inquietud que aún no se ha abordado. Una pregunta ''pegajosa'' de ejemplo en este caso podría ser: "¿Qué es exactamente lo recursivo de este problema?"

Antes de leer el siguiente párrafo, trate de responder esta pregunta primero. Si sabía qué era recursivo sobre el problema, escribir un método recursivo para resolverlo podría no ser muy difícil.

Desea saber si alguna expresión que usa un conjunto de números (cada número usado solo una vez) le da un valor objetivo. Hay cuatro operaciones binarias, cada una con un inverso . Entonces, en otras palabras, desea saber si el primer número operado con alguna expresión de los otros números le da el objetivo. Bueno, en otras palabras, quiere saber si alguna expresión de los "otros" números es [...]. De lo contrario, usar la primera operación con el primer número realmente no le da lo que necesita, así que intente con las otras operaciones. Si no funcionan, entonces tal vez no estaba destinado a serlo.

Edit: pensé en esto para una expresión de infix de cuatro operadores sin paréntesis, ya que un comentario en la pregunta original decía que los paréntesis se agregaron por el bien de un ejemplo (¿para claridad?) Y el uso de paréntesis no se declaró explícitamente.

Answer 2

Aquí hay algunos códigos Python para comenzar: solo imprime todas las expresiones posibles, sin preocuparse demasiado por la redundancia. Necesitaría modificarlo para evaluar expresiones y comparar con el número objetivo, en lugar de simplemente imprimirlas.

La idea básica es: dado un conjunto S de números, la partición S en dos subconjuntos left y right en todas las formas posibles (donde no nos importa el orden o los elementos de left y right ), de modo que la left y la right son ambas no vacío Ahora, para cada una de estas particiones, encuentre todas las formas de combinar los elementos en la left (¡recursivamente!), Y de manera similar para la right , y combine los dos valores resultantes con todos los operadores posibles. La recursión llega al límite cuando un conjunto tiene solo un elemento, en cuyo caso solo hay un valor posible.

Incluso si no conoces Python, la función de expressions debe ser razonablemente fácil de seguir; La función de splittings contiene algunas rarezas de Python, pero todo lo que hace es encontrar todas las particiones de la lista l en partes izquierda y derecha.

def splittings(l):
    n = len(l)
    for i in xrange(2**n):
        left = [e for b, e in enumerate(l) if i & 2**b]
        right = [e for b, e in enumerate(l) if not i & 2**b]
        yield left, right

def expressions(l):
    if len(l) == 1:
        yield l[0]
    else:    
        for left, right in splittings(l):
            if not left or not right:
                continue
            for el in expressions(left):
                for er in expressions(right):
                    for operator in ''+-*/'':
                        yield ''('' + el + operator + er + '')''

for x in expressions(''1234''):
    print x

Answer 3

Bueno, no mencionaste la eficiencia, por lo que publicaré una solución de fuerza bruta y te permitiré optimizarla si lo deseas. Ya que puede tener paréntesis, es fácil forzarlo con fuerza usando la notación polaca inversa :

En primer lugar, si su conjunto tiene n números, debe usar exactamente n - 1 operadores. Así que su solución estará dada por una secuencia de 2n - 1 símbolos de {{su conjunto dado}, {*, /, +, -}}

st = a stack of length 2n - 1
n = numbers in your set
a = your set, to which you add *, /, +, -
v[i] = 1 if the NUMBER i has been used before, 0 otherwise

void go(int k)
{
  if ( k > 2n - 1 ) 
  {
    // eval st as described on Wikipedia. 
    // Careful though, it might not be valid, so you''ll have to check that it is   
    // if it evals to your target value great, you can build your target from the given numbers. Otherwise, go on.

    return;
  }

  for ( each symbol x in a )
    if ( x isn''t a number or x is a number but v[x] isn''t 1 )
    {
      st[k] = x;
      if ( x is a number )
        v[x] = 1;

      go(k + 1);
    }
}

Answer 4

En términos generales, cuando necesitas hacer algo recursivamente, te ayuda a comenzar desde el "fondo" y pensar cómo ascender. Considere: Tiene un conjunto S de n números {a,b,c,...} , y un conjunto de cuatro operaciones {+,-,*,/} . Llamemos a su función recursiva que opera en el conjunto F(S)

• Si n es 1, entonces F(S) solo será ese número.
• Si n es 2, F(S) puede ser ocho cosas:
  • elija su número de la izquierda de S (2 opciones)
  • luego elija una operación para aplicar (4 opciones)
  • Tu número de la derecha será lo que quede en el set.
• Ahora, puedes generalizar desde el caso n = 2:
  • Elija un número x de S para que sea el operando de la izquierda ( n opciones)
  • Elija una operación para aplicar
  • su número de la mano derecha será F(Sx)

Te dejaré tomarlo desde aquí. :)

Edición: Marcos plantea una crítica válida; El método anterior no obtendrá absolutamente todo. Para solucionar ese problema, debe pensarlo de una manera ligeramente diferente:

• En cada paso, primero selecciona una operación (4 opciones), y luego
• Partición S en dos conjuntos, para los operandos de la mano izquierda y derecha,
• y recursivamente aplicar F a ambas particiones

Sin embargo, encontrar todas las particiones de un conjunto en 2 partes no es trivial en sí mismo.

Answer 5

Esta no pretende ser la solución más rápida, sino una solución instructiva.

• Genera recursivamente todas las ecuaciones en notación postfix
• También proporciona una traducción de postfix a notación infijo.
• No hay un cálculo aritmético real hecho, por lo que debe implementarlo por su cuenta
  • Ten cuidado con la división por cero

¡Con 4 operandos, 4 operadores posibles, genera todos los 7680 = 5 * 4! * 4 ^ 3 expresiones posibles.

• 5 es catalán (3). Catalán (N) es el número de formas de paréntesis de operandos N + 1.
• 4! Porque los 4 operandos son permutables.
• 4 ^ 3 porque los 3 operadores tienen 4 opciones cada uno

Esto definitivamente no se escala bien, ya que el número de expresiones para N operandos es [1, 8, 192, 7680, 430080, 30965760, 2724986880, ...].

En general, si tiene n+1 operandos, y debe insertar n operadores elegidos de k posibilidades, entonces hay (2n)!/n! k^n (2n)!/n! k^n posibles ecuaciones.

¡Buena suerte!

import java.util.*;

public class Expressions {
    static String operators = "+-/*";

    static String translate(String postfix) {
        Stack<String> expr = new Stack<String>();
        Scanner sc = new Scanner(postfix);
        while (sc.hasNext()) {
            String t = sc.next();
            if (operators.indexOf(t) == -1) {
                expr.push(t);
            } else {
                expr.push("(" + expr.pop() + t + expr.pop() + ")");
            }
        }
        return expr.pop();
    }

    static void brute(Integer[] numbers, int stackHeight, String eq) {
        if (stackHeight >= 2) {
            for (char op : operators.toCharArray()) {
                brute(numbers, stackHeight - 1, eq + " " + op);
            }
        }
        boolean allUsedUp = true;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != null) {
                allUsedUp = false;
                Integer n = numbers[i];
                numbers[i] = null;
                brute(numbers, stackHeight + 1, eq + " " + n);
                numbers[i] = n;
            }
        }
        if (allUsedUp && stackHeight == 1) {
            System.out.println(eq + " === " + translate(eq));
        }
    }
    static void expression(Integer... numbers) {
        brute(numbers, 0, "");
    }

    public static void main(String args[]) {
        expression(1, 2, 3, 4);
    }
}

Answer 6

Su mejor pista sobre cómo abordar este problema es el hecho de que su maestro / profesor quiere que use la recursión. Es decir, esto no es un problema de matemáticas , es un problema de búsqueda.

No regalar demasiado (después de todo, es tarea), pero debe generar una llamada a la función recursiva utilizando un operador, un número y una lista que contenga los números restantes. La función recursiva extraerá un número de la lista y, utilizando la operación aprobada, lo combinará con el número pasado (que es su total acumulado). Tome el total acumulado y llámese nuevamente con los elementos restantes de la lista (tendrá que recorrer la lista dentro de la llamada, pero la secuencia de las llamadas es primero la profundidad). Haga esto una vez para cada uno de los cuatro operadores, a menos que el éxito se haya logrado mediante un tramo anterior de la búsqueda.

Actualicé esto para usar una lista en lugar de una pila

Cuando el resultado de la operación es su número de destino y su lista está vacía, entonces ha encontrado con éxito el conjunto de operaciones (aquellas que rastrearon la ruta hacia la hoja exitosa): establezca la marca de éxito y desenrolle. Tenga en cuenta que los operadores no están en una lista ni están en la llamada: la función en sí misma siempre se repite en los cuatro. Su mecanismo para "desenrollar" la secuencia del operador de la hoja exitosa para obtener la secuencia es devolver el operador actual y el número prepagado al valor devuelto por la llamada recursiva (solo uno de los cuales será exitoso ya que se detiene en el éxito, eso, obviamente , es la de usar). Si ninguno tiene éxito, entonces lo que devuelva no es importante de todos modos.

Actualizar Esto es mucho más difícil cuando tienes que considerar expresiones como la que Daniel publicó. Usted tiene combinatoria en los números y las agrupaciones (los números debido al hecho de que / y - son sensibles al orden, incluso sin agrupar y agrupar porque cambia la prioridad). Entonces, por supuesto, también tienes la combinatoria de las operaciones. Es más difícil manejar las diferencias entre (4 + 3) * 2 y 4 + (3 * 2) porque la agrupación no se repite como operadores o números (lo que puede repetir en una amplitud en primer lugar mientras hace su ( profundidad-primero) llamadas recursivas).

Answer 7

codigo de pusedo:

Works(list, target)
for n in list
tmp=list.remove(n)
return Works(tmp,target+n) or Works(tmp,target-n) or Works(tmp, n-target) or ...

entonces solo tienes que poner el caso base. Creo que he regalado mucho.