Finden Sie alle Untergruppen eines int-Arrays, deren Summen einem angegebenen Ziel entsprechen

77588
MouseLearnJava

Ich versuche unten eine Funktion zu implementieren:

Bestimmen Sie bei einer Zielsumme alle Teilmengen aus einem intArray, deren Summe der Zielsumme entspricht .

Zum Beispiel:

Zielsumme ist 15.

Ein intArray ist { 1, 3, 4, 5, 6, 15 }.

Dann sind alle erfüllten Teilmengen mit der Summe 15 wie folgt:

15 = 1+3+5+6
15 = 4+5+6
15 = 15

Ich verwende java.util.StackKlasse, um diese Funktion zusammen mit Rekursion zu implementieren.

GetAllSubsetByStack- Klasse

import java.util.Stack;

public class GetAllSubsetByStack {

    /** Set a value for target sum */
    public static final int TARGET_SUM = 15;

    private Stack<Integer> stack = new Stack<Integer>();

    /** Store the sum of current elements stored in stack */
    private int sumInStack = 0;

    public void populateSubset(int[] data, int fromIndex, int endIndex) {

        /*
        * Check if sum of elements stored in Stack is equal to the expected
        * target sum.
        * 
        * If so, call print method to print the candidate satisfied result.
        */
        if (sumInStack == TARGET_SUM) {
            print(stack);
        }

        for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {

            if (sumInStack + data[currentIndex] <= TARGET_SUM) {
                stack.push(data[currentIndex]);
                sumInStack += data[currentIndex];

                /*
                * Make the currentIndex +1, and then use recursion to proceed
                * further.
                */
                populateSubset(data, currentIndex + 1, endIndex);
                sumInStack -= (Integer) stack.pop();
            }
        }
    }

    /**
    * Print satisfied result. i.e. 15 = 4+6+5
    */

    private void print(Stack<Integer> stack) {
        StringBuilder sb = new StringBuilder();
        sb.append(TARGET_SUM).append(" = ");
        for (Integer i : stack) {
            sb.append(i).append("+");
        }
        System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
    }
}

Hauptklasse

public class Main {

    private static final int[] DATA = { 1, 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, 13,
        14, 15 };

    public static void main(String[] args) {
        GetAllSubsetByStack get = new GetAllSubsetByStack();
        get.populateSubset(DATA, 0, DATA.length);
    }
}

Ausgabe in Console ist wie folgt:

15 = 1+3+4+5+2
15 = 1+3+4+7
15 = 1+3+5+6
15 = 1+3+2+9
15 = 1+3+11
15 = 1+4+2+8
15 = 1+4+10
15 = 1+5+2+7
15 = 1+5+9
15 = 1+6+8
15 = 1+14
15 = 3+4+6+2
15 = 3+4+8
15 = 3+5+7
15 = 3+2+10
15 = 4+5+6
15 = 4+2+9
15 = 4+11
15 = 5+2+8
15 = 5+10
15 = 6+2+7
15 = 6+9
15 = 2+13
15 = 7+8
15 = 15

Bitte helfen Sie mir mit den folgenden zwei Dingen:

  1. Wie kann ich diesen Code verbessern, um die Rekursionszeiten zu reduzieren? Ist das Sortieren des intArrays (von hoch nach niedrig) vor der Rekursion ein besserer Weg?

  2. Gibt es eine Möglichkeit, den Code ohne Rekursion zu verbessern?

Antworten
28

3 Antworten auf die Frage

18
rolfl

There are three reasonable responses here:

  • yes, your recursion code can be improved for performance.
  • yes, part of that improvement can come from sorting the data.
  • yes, there's a way to refactor the code to not use recursion, and it may even be faster.

Bearing that in mind, this answer becomes 'complicated'.

Basic performance improvements for current code:

if (sumInStack == TARGET_SUM) {
    print(stack);
}

can easily be:

if (sumInStack >= TARGET_SUM) {
    if (sumInStack == TARGET_SUM) {
        print(stack);
    }
    // there is no need to continue when we have an answer
    // because nothing we add from here on in will make it
    // add to anything less than what we have...
    return;
}

I dislike any recursive function which rely on external (outside-the-method) values. In your case, the sumInStack is external. This makes the target hard to 'see'.

Additionally, if we do sort the data, there are some benefits we can have, and a way to restructure the recursion to make it do less work (since we can guarantee that all values after a point have certain properties...):

consider the method (assuming sorted data):

public void populateSubset(final int[] data, int fromIndex, 
                           final int[] stack, final int stacklen,
                           final int target) {
    if (target == 0) {
        // exact match of our target. Success!
        printResult(Arrays.copyOf(stack, stacklen));
        return;
    }

    while (fromIndex < data.length && data[fromIndex] > target) {
        // take advantage of sorted data.
        // we can skip all values that are too large.
        fromIndex++;
    }

    while (fromIndex < data.length && data[fromIndex] <= target) {
        // stop looping when we run out of data, or when we overflow our target.
        stack[stacklen] = data[fromIndex];
        populateSubset(data, fromIndex + 1, stack, stacklen + 1, target - data[fromIndex]);
        fromIndex++;
    }
}

You would call this function with:

Arrays.sort(data); 
populateSubSet(data, 0, new int[data.length], 0, 15);

So, that is 'can the code be improved?' and 'will sorting help'

As for the 'unrolled' (no recursion) version of the system, it can be done. It would require three int[] arrays:

int[] data = {....}
int[] sum = new int[data.length];
int[] indices = new int[data.length];
int depth = 0;
int lastindex = -1;

The sum gives and indices act like a stack, and the depth is how deep the stack is (again, assume sorted data):

Arrays.sort(data);
while (depth >= 0) {
    lastindex++;
    if (lastindex == data.length) {
        // we have run out of data.
        do {
            // walk up the stack till we find some data.
            depth--;
        while (depth >= 0 && (lastindex = indices[depth] + 1) < data.length);
    }
    if (depth >= 0) {
         .....
         you then add your code in here to check the target,
         keep it updated in your 'stack'.
         go down a level and move on....
    }

}
Ich kann mir so viele tolle Dinge vorstellen, die ich mit Memoization machen kann! Wir können alle Lösungen in ArrayList speichern> für ein bestimmtes Paar (fromIndex, target) Vikrant Goel vor 5 Jahren 0
-1
Pointy

Eine andere Möglichkeit, Probleme wie die Untersuchung der Eigenschaften aller Untergruppen (dh der Mitglieder der "Leistungsgruppe") zu lösen, besteht darin, die Hauptsammlung als eine Liste von Zellen und jede Zelle als binäre Ziffernposition zu betrachten. Ein Mitglied des Leistungssatzes kann daher durch eine Binärzahl beschrieben werden, so dass der Teilsatz nur diejenigen Elemente des Satzes enthält, die einer 1 im Binärwert entsprechen.

Auf diese Weise können Sie die eingestellte Leistung einfach durch Zählen erzeugen. Natürlich wird dies etwas komplizierter, wenn der ursprüngliche Satz mehr Werte enthält, die vom nativen Integer-Typ in einer bestimmten Programmiersprache bequem behandelt werden können, in Java dagegen BigInteger. (Das Aufzählen eines Power-Sets zu einem beliebigen Zweck wird für Original-Sets, die sowieso groß sind, etwas schmerzhaft.)

-1
toto2

Ich habe es nicht vollständig ausgearbeitet, aber der beste Algorithmus hier ist wahrscheinlich die dynamische Programmierung . Grundsätzlich würde ich die Werte ordnen und bei allen möglichen Beträgen behalten, wenn man frühere Beträge berücksichtigt.

Zum Beispiel für die Eingabe {1, 2, 3, 4, 6}:

Value : possible sums considering earlier sums and current value
1     : 0, 1
2     : 0, 1, 2, 3     (that is: 1 + 0 * 2, 0 * 1 + 2, 1 + 2)
3     : 0, 1, 2, 3, 4, 5, 6
4     : 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11
6     : 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 8, 12, 13, 15, 16

Beachten Sie, dass oben einige Effizienz erzielt wurde, da einige Kombinationen mehrmals wiederholt werden. Zum Beispiel kann bei Position 3 der Ausgabewert 3 entweder von (1 * 3_von_previous_sum + 0 * 3) oder (0 * 3_von_previous_sum + 1 * 3) erhalten werden. Je weiter Sie gehen, desto mehr redundante Werte treten auf.

Ich habe nicht herausgefunden, ob dies eindeutig effizienter wäre als die Verwendung der Brute-Force-Suche, aber ich bin mir ziemlich sicher. Dynamische Programmierung sollte den Speicherbedarf des Algorithmus erhöhen, die Rechenzeit jedoch verringern.

Die Beispieltabelle, die ich erstellt habe, wäre nützlich, um zu beantworten, ob eine bestimmte Summe erzielt werden kann oder nicht, aber nicht alle Kombinationen anzugeben, die eine Summe ergeben können, falls vorhanden. Um diese zweite Frage zu beantworten, müsste die Tabelle modifiziert werden, um jedem Ausgangssummenwert alle Kombinationen zuzuordnen, die ihn erzeugen können.