Computing angestrebte Anzahl von zahlen in einem set

Dies ist nicht dazu gedacht, um die Schnellste Lösung, sondern eher ein lehrreiches ein.

• Es rekursiv erzeugt alle Gleichungen in postfix-notation
• Es bietet auch eine übersetzung von postfix infix-notation
• Es gibt keine eigentlichen Rechenoperationen durchgeführt, so dass Sie haben zu implementieren, die auf Ihre eigenen
  • Vorsichtig sein, über die die division durch null

Mit 4 Operanden, 4 mögliche Operatoren, die es erzeugt alle 7680 = 5 * 4! * 4^3
möglich Ausdrücken.

• 5 ist Katalanisch(3). Katalanisch(N) ist die Anzahl der Möglichkeiten für paranthesize N+1 Operanden.
• 4! da die 4 Operanden permutable
• 4^3, weil die 3 Betreiber haben jeweils 4 Wahl

Dies ist definitiv nicht gut skalieren, da die Anzahl der Ausdrücke für N Operanden [1, 8, 192, 7680, 430080, 30965760, 2724986880, ...].

Im Allgemeinen, wenn Sie haben n+1 Operanden und fügen n Betreiber ausgewählt aus k Möglichkeiten, dann gibt es (2n)!/n! k^n möglich Gleichungen.

Glück!

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

Generell, wenn Sie etwas tun müssen rekursiv hilft es zu Beginn von "unten" und denken Sie Ihren Weg nach oben.
Bedenken Sie: Sie haben eine Reihe S von n zahlen {a,b,c,...}, und ein Satz von vier Operationen {+,-,*,/}. Nennen wir Ihre rekursive Funktion, die arbeitet auf der eingestellten F(S)

• Wenn n 1 ist, dann F(S) wird nur sein, dass Nummer.
• Wenn n 2 F(S) acht Dinge:
  • wählen Sie Ihre linke Zahl von S (2 Entscheidungen)
  • und wähle dann einen Betrieb zu übernehmen (4 Optionen)
  • Ihre Rechte-hand-Zahl wird das sein, was übrig ist, in der set -
• Jetzt können Sie verallgemeinern von der n=2 Fall:
  • Wählen Sie eine Zahl x aus S zu den linken Operanden (n Entscheidungen)
  • Wählen, eine operation zu gelten
  • Ihrer rechten hand Nummer F(S-x)

Ich lasse Sie es nehmen von hier aus. 🙂

Bearbeiten: Markieren, stellt eine gültige Kritik, die oben genannten Methode nicht absolut alles. Um dieses problem zu beheben, müssen Sie darüber nachdenken, es in einer etwas anderen Weise:

• Bei jedem Schritt, den Sie zuerst wählen Sie eine operation (4 Optionen), und dann
• partition S in zwei sets, für die linken und rechten Operanden,
• und rekursiv anwenden F auf beiden Partitionen

Finden Sie alle Partitionen einer Menge in 2 Teile ist nicht trivial, selbst, wenn.

Hier einige Python-code, um Ihnen den Einstieg: es ist einfach Drucke alle möglichen Ausdrücke, ohne sich sorgen zu viel über Redundanz. Sie müssten, um es zu ändern, um Ausdrücke auszuwerten und zu vergleichen, um die Ziel-Zahl, anstatt Sie zu drucken.

Die Grundidee ist: gegeben eine Menge S von zahlen, partition von S in zwei Teilmengen left und right in alle möglichen Richtungen (wo wir kümmern uns nicht um die Reihenfolge oder die Elemente in left und right), so dass left und right sind beide nicht leer. Nun für jede dieser Partitionen, finden Sie alle Möglichkeiten der Kombination der Elemente in left (rekursiv!), und ähnlich für right, und kombinieren Sie die beiden resultierenden Werte mit allen möglichen Operatoren. Die Rekursion Höschen aus, wenn ein Satz hat nur ein element, in dem Fall gibt es nur ein Wert möglich.

Selbst wenn Sie nicht wissen, Python, der expressions - Funktion sollte relativ einfach zu Folgen; die splittings Funktion enthält einige Python Merkwürdigkeiten, aber alle es tut, ist, finden Sie alle Partitionen in der Liste l in Links und rechts Stücke.

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