Java SubSum bestimmen

[rosima26]

Hey zusammen,
ich habe ne Methode entwickelt, die checken soll ob ein übergebenes Array Subsets enthält die in Summe 0 ergeben. Das Funktioniert auch soweit und printet "Subset" gefunden, allerdings mit return false. Das verstehe ich nicht, ich möchte ja ein true wenn etwas gefunden wird. Es macht mich verrückt dass immer false ausgegeben wird, die Methode soll ja vorbei sein wenn ich returne. Sieht vielleicht jemand den Fehler?

public boolean subsetSum(int[] liste, int index, int aktuelleSumme) {

        // Base-Case
        if (liste.length == 1) {
            if (liste[0] == 0)
                return true;
            else
                return false;
        }
        for (int i = index; i < liste.length; i++) {

            aktuelleSumme += liste[i];
            System.out.println(liste[i]);

            if (aktuelleSumme == 0) {
                System.out.println("Subset gefunden !");
                return true;
            }
        }

        if (index < liste.length)
            subsetSum(liste, index += 1, 0);

        return false;

    }

}

 

[KonradN]

Du hast einen rekursiven Aufruf von subsetSum aber du beachtest die Rückgabe nicht.

Du musst die Rückgabe auswerten und entsprechend reagieren.

Und ganz nebenbei: So Konstrukte:

            if (liste[0] == 0)
                return true;
            else
                return false;

kannst Du abkürzen zu return liste[0] == 0;

 

[yfons123]

subsetSum(liste, index += 1, 0);

dir ist es egal was die unter aufrufe ergeben... somit entscheidet der unteraufruf nichts

nur der erste aufruf entscheidet
entweder ist es ein subset am anfang und true zurück gegeben
oder es wird weiter gesucht und false zurück gegeben

 

[rosima26]

Habs verbessert, danke euch

public boolean subsetSum(int[] liste, int index, int aktuelleSumme) {

        for (int i = index; i < liste.length; i++) {

            aktuelleSumme += liste[i];

            if (aktuelleSumme == 0) {
                System.out.println("Subset gefunden !");
                return true;
            }
        }

        if (index == liste.length)
            return false;

        return subsetSum(liste, index += 1, 0);

    }

 

[rosima26]

Hätte jemand eine Idee wie sich daraus anhand der Vergleiche eine Rekursionsgleichung aufstellen ließe?

 

[KonradN]

Habs verbessert, danke euch

Ja, sehr gut. noch ein paar Punkte, die auffallen:

• Der Parameter aktuelleSumme - was wird da herein gegeben? Macht das Sinn? Was für Parameter gibst Du bei Aufrufen denn da an?
• Bei Rekursion finde ich es immer gut, wenn die Abbruchbedingung zuerst geprüft wird. Verändert nicht wirklich was, weil die Schleife ja nicht durchlaufen wird, aber dann wird es deutlicher.

 

[rosima26]

Ja, sehr gut. noch ein paar Punkte, die auffallen:

• Der Parameter aktuelleSumme - was wird da herein gegeben? Macht das Sinn? Was für Parameter gibst Du bei Aufrufen denn da an?
• Bei Rekursion finde ich es immer gut, wenn die Abbruchbedingung zuerst geprüft wird. Verändert nicht wirklich was, weil die Schleife ja nicht durchlaufen wird, aber dann wird es deutlicher.

Die aktuelle Summe soll je Methodendurchlauf wieder auf 0 zurückgesetzt werden. Gefragt ist ob eine Reihe an Elementen im Array die Summe 0 ergibt und daher dachte ich sollte das wieder 0 betragen wenn die Methode wieder durchlaufen wird. Klappt soweit auch gut !

 

[KonradN]

Die aktuelle Summe soll je Methodendurchlauf wieder auf 0 zurückgesetzt werden. Gefragt ist ob eine Reihe an Elementen im Array die Summe 0 ergibt und daher dachte ich sollte das wieder 0 betragen wenn die Methode wieder durchlaufen wird. Klappt soweit auch gut !

Wenn es am Anfang der Methode 0 sein soll (oder besser muss), dann wäre es ja ein Fehler, da einen anderen Wert anzugeben beim Aufruf. Daher macht es doch Sinn, auf den Parameter zu verzichten. Alles, was notwendig ist, ist dann eine lokale Variable.

 

[rosima26]

Wenn es am Anfang der Methode 0 sein soll (oder besser muss), dann wäre es ja ein Fehler, da einen anderen Wert anzugeben beim Aufruf. Daher macht es doch Sinn, auf den Parameter zu verzichten. Alles, was notwendig ist, ist dann eine lokale Variable.

Der Methodenkopf ist in dieser Aufgabe vorgegeben

 

[KonradN]

Der Methodenkopf ist in dieser Aufgabe vorgegeben

Ok, dann kann man es natürlich nicht verändern.

 

[rosima26]

Hätte jemand eine Idee wie sich daraus anhand der Vergleiche eine Rekursionsgleichung aufstellen ließe?

Hätte da jemand noch eine Idee?

 

[MarvinsDepression]

Der Parameter aktuelleSumme - was wird da herein gegeben? Macht das Sinn? Was für Parameter gibst Du bei Aufrufen denn da an?

In der Rekursion wird aktuelleSumme stets mit 0 übergeben. Kann also auch am Methodenanfang mit 0 initialisiert werden.

Zeile 16:

return subsetSum(liste, index += 1, 0);

das 'index += 1' -> 'index + 1'? Müsste doch reichen?

 

[MarvinsDepression]

Das mit dem vorgegbenen Methodenkopf habe ich zu spät gelesen. Wenn der so sein soll, stellt sich mir ja die Frage nach dem Sinn dahinter.
Evtl. ist es ja möglich, auf die for-Schleife zu verzichten und das von der Rekursion machen lassen.
Ich stehe zwar selber mit Rekusionen auf Kriegsfuß, aber ich glaube, das geht.

 

[KonradN]

Ja, auf die for Schleife kann man verzichten und das wird hier dann auch vermutlich verlangt sein.

Dazu braucht man dann halt zwei rekursive Aufrufe: Einmal mit Weitergabe der bisherigen Summe und zum anderen mit dem Aufruf von 0.

 

[rosima26]

Hätte da jemand noch eine Idee?

Könnten wir das Diskussionsthema eventuell wieder hierher verschieben ? Wäre wirklich dankbar wenn dazu jemand eine Idee hätte..

 

[KonradN]

Könnten wir das Diskussionsthema eventuell wieder hierher verschieben ? Wäre wirklich dankbar wenn dazu jemand eine Idee hätte..

Dir sollte aber bewusst sein, dass Du mit der Schleife keine reine rekursive Lösung hast sondern immer noch einen nicht unerheblichen iterativen Teil. Daher wird das vermutlich nicht die gesuchte Lösung sein.

Und was die Rekursionsgleichung angeht: Da Du derzeit auch einen iterativen Anteil hast, ist der nicht so leicht zu formulieren finde ich. Daher wäre es vermutlich besser, erst einmal eine rein rekursive Lösung zu bekommen.

Aber um das zu erarbeiten: Wie sieht denn eine Rekursionsgleichung aus?

 

[rosima26]

Wüsste gar nicht wie ich das mit reiner rekursion machen würde. Ich muss ja irgendwie vom Index aus durch das Array iterieren

 

[MarvinsDepression]

Na ja, eigentlich steht es in #14 schon gut beschrieben drin. Habe es jetzt mal selber probiert und es funzt (wenn auch fantastisch ineffektiv, da die im Worstcase benötigten Rekursionen bei 2^n statt er erwarteten n^2 liegen).
Fange mit der Abbruchbedingung an, dann bilde die Summe, dann vergleiche..., dann der eine Rekursionsaufruf, wenn der false liefert, den anderen Rekursionsaufruf. Probiere mal rum.

 

[rosima26]

Bin dabei. Aber ich brauche doch eine Laufvariable bzw Schleife oder?

 

[yfons123]

der sinn für eine rekursions übung ist es keine schleifen zu haben am ende

als "beispiel" wo man es braucht:

Türme von hanoi als rekursion:

    static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
    {
        if (n == 1)
        {
            System.out.println("Move disk 1 from rod " +  from_rod + " to rod " + to_rod);
            return;
        }
        towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
        System.out.println("Move disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
        towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
    }

türme von hanoi iterativ:

// A structure to represent a stack
class Stack
{
    int capacity;
    int top;
    int array[];
}
 
// Function to create a stack of given capacity.
Stack createStack(int capacity)
{
    Stack stack = new Stack();
    stack.capacity = capacity;
    stack.top = -1;
    stack.array = new int[capacity];
    return stack;
}
 
// Stack is full when the top is equal
// to the last index
boolean isFull(Stack stack)
{
    return (stack.top == stack.capacity - 1);
}
 
// Stack is empty when top is equal to -1
boolean isEmpty(Stack stack)
{
    return (stack.top == -1);
}
 
// Function to add an item to stack.It
// increases top by 1
void push(Stack stack, int item)
{
    if (isFull(stack))
        return;
        
    stack.array[++stack.top] = item;
}
 
// Function to remove an item from stack.It
// decreases top by 1
int pop(Stack stack)
{
    if (isEmpty(stack))
        return Integer.MIN_VALUE;
        
    return stack.array[stack.top--];
}
 
// Function to implement legal movement between
// two poles
void moveDisksBetweenTwoPoles(Stack src, Stack dest,
                              char s, char d)
{
    int pole1TopDisk = pop(src);
    int pole2TopDisk = pop(dest);
 
    // When pole 1 is empty
    if (pole1TopDisk == Integer.MIN_VALUE)
    {
        push(src, pole2TopDisk);
        moveDisk(d, s, pole2TopDisk);
    }
    
    // When pole2 pole is empty
    else if (pole2TopDisk == Integer.MIN_VALUE)
    {
        push(dest, pole1TopDisk);
        moveDisk(s, d, pole1TopDisk);
    }
    
    // When top disk of pole1 > top disk of pole2
    else if (pole1TopDisk > pole2TopDisk)
    {
        push(src, pole1TopDisk);
        push(src, pole2TopDisk);
        moveDisk(d, s, pole2TopDisk);
    }
    // When top disk of pole1 < top disk of pole2
    else
    {
        push(dest, pole2TopDisk);
        push(dest, pole1TopDisk);
        moveDisk(s, d, pole1TopDisk);
    }
}
 
// Function to show the movement of disks
void moveDisk(char fromPeg, char toPeg, int disk)
{
    System.out.println("Move the disk " + disk +
                            " from " + fromPeg +
                              " to " + toPeg);
}
 
// Function to implement TOH puzzle
void tohIterative(int num_of_disks, Stack
                  src, Stack aux, Stack dest)
{
    int i, total_num_of_moves;
    char s = 'S', d = 'D', a = 'A';
 
    // If number of disks is even, then
    // interchange destination pole and
    // auxiliary pole
    if (num_of_disks % 2 == 0)
    {
        char temp = d;
        d = a;
        a  = temp;
    }
    total_num_of_moves = (int)(Math.pow(
                         2, num_of_disks) - 1);
 
    // Larger disks will be pushed first
    for(i = num_of_disks; i >= 1; i--)
        push(src, i);
 
    for(i = 1; i <= total_num_of_moves; i++)
    {
        if (i % 3 == 1)
          moveDisksBetweenTwoPoles(src, dest, s, d);
 
        else if (i % 3 == 2)
          moveDisksBetweenTwoPoles(src, aux, s, a);
 
        else if (i % 3 == 0)
          moveDisksBetweenTwoPoles(aux, dest, a, d);
    }
}

beides von geeks for geeks... der eindruck sollte gezeigt werden

 

[KonradN]

Bin dabei. Aber ich brauche doch eine Laufvariable bzw Schleife oder?

Eine Möglichkeit, wie man an sowas heran gehen kann, ist immer wenn man klein anfängt um dann zu formulieren, was man denn dann hat.

Gegeben ist ja die Schnittstelle, also das:
boolean subsetSum(int[] liste, int index, int aktuelleSumme)

Und von mir aus auch der erste Aufruf bei einer Liste. Da wird die Liste übergeben und was als index und aktuelle Summe?

Und dann kann man das einfach etwas durchspielen:

1. Was ist, wenn die Liste leer ist und die zwei Parameter so, wie eben beantwortet gesetzt sind: Was ist dann das Ergebnis? Im Idealen Fall beschreibst Du es möglichst allgemein.

2. Dann hast Du eine Liste mit nur einem Element. Was ist dann das Ergebnis?

3. Dann hast Du eine Liste mit zwei Elementen und Du hast den Aufruf mit den Startparametern. Was ist dann das Ergebnis?

Wenn Du sowas formulieren kannst und das dann jeweils etwas verallgemeinerst, dann hast Du
a) die Implementation
b) die Rekursionsgleichung.

 

[rosima26]

Verstehe ich leider nicht wirklich. Meine Überlegung ist es, vom index im array bis hinten durchzugehen und zu schauen ob die summe 0 ist, und wenn das so ist abzubrechen. Wenns nicht so ist dann wir der index erhöht und wir spielen das ganze ohne das erste element durch.... und so weiter und so weiter. Aber ich kann den index ja nicht gleichzeitig als startpunkt und als laufvariable nutzen

 

[KonradN]

Verstehe ich leider nicht wirklich. Meine Überlegung ist es, vom index im array bis hinten durchzugehen und zu schauen ob die summe 0 ist, und wenn das so ist abzubrechen. Wenns nicht so ist dann wir der index erhöht und wir spielen das ganze ohne das erste element durch.... und so weiter und so weiter. Aber ich kann den index ja nicht gleichzeitig als startpunkt und als laufvariable nutzen

Also prinzipiell stimmt die grobe Beschreibung. Aber ich verstehe Deine Problematik nicht. Woran scheiterst Du?

Kannst Du das denn einmal im Detail für kleine Arrays durchspielen? Bei jedem (aber auch wirklich jedem!) Problem ist vor jeder Implementation das genaue Verständnis, was überhaupt gefordert ist und wie man das manuell durchspielen kann.

Und ich habe da einen Ansatz gegeben:

1. Was ist, wenn die Liste leer ist und die zwei Parameter so, wie eben beantwortet gesetzt sind: Was ist dann das Ergebnis? Im Idealen Fall beschreibst Du es möglichst allgemein.

2. Dann hast Du eine Liste mit nur einem Element. Was ist dann das Ergebnis?

3. Dann hast Du eine Liste mit zwei Elementen und Du hast den Aufruf mit den Startparametern. Was ist dann das Ergebnis?

Was ist denn bei der leeren Liste? Wie sähe der Aufruf aus? Und was wäre die Rückgabe?

 

[KonradN]

Oder evtl. ein anderer Ansatz - der ist aber aus meiner Sicht etwas abstrakter.

Was ist denn die Aufgabe? Du hast ein Array, welches Du durchgehst. Du hast also immer den Fall:
[ bearbeitete Elemente ] [ aktuelles Element ] [ Folgende Elemente ]

Was für bereits bearbeitete Elemente es schon gibt, interessiert Dich nicht. Was Du von den bearbeiteten Elementen aber hast ist die bisherige Summe.
Welches das aktuelle Element ist, hast Du über den index

Nun kannst Du das aktuelle Element bearbeiten. Dabei ist wichtig:

• Gibt es das Element?
• Wenn es das Element gibt, wäre die nächste Frage: Hast Du ein finales Ergebnis? (Was wäre ein finales Ergebnis? Wann kannst Du aufhören zu suchen?)
• Wenn Du noch kein Ergebnis hast: Was kannst Du nun weiter prüfen? Welche Fälle gibt es da?

 

[rosima26]

Naja die Summe wäre wohl 0 also wäre die Rückgabe true

Das sähe dann so ungefähr aus: if( list.length == 0 ) return true;
oder steh ich jetzt völlig auf dem Schlauch?

 

[KonradN]

Naja die Summe wäre wohl 0 also wäre die Rückgabe true

Das sähe dann so ungefähr aus: if( list.length == 0 ) return true;
oder steh ich jetzt völlig auf dem Schlauch?

Was hast Du denn summiert? Gab es ein Subset, dessen Summe 0 ergeben hat? Wenn das leere Subset auch zählen würde, dann wäre ja immer true zurück zu geben, denn das leere Subset könnte man dann ja immer nehmen.

 

[rosima26]

Das stimmt 🤔

Also gibt es das Element würde ich mit solange sich der Index in liste befindet beantworten
Hab ich ein Finales Ergebnis? Ja bei Summe == 0
Und schlussendlich würde ich weiterprüfen indem ich diesesmal nicht ganz vorne anfange zu summieren sondern eben ganz vorne + 1

 

[KonradN]

Also gibt es das Element würde ich mit solange sich der Index in liste befindet beantworten

Also der index muss < länge des Arrays sein. Ok. Was ist das Ergebnis, wenn das nicht mehr der Fall ist? (Denk an den Fall "leeres Array" von eben. Das ist vergleichbar, nur eben dass wir jetzt Elemente davor hatten.

Und schlussendlich würde ich weiterprüfen indem ich diesesmal nicht ganz vorne anfange zu summieren sondern eben ganz vorne + 1

Das ist mir noch zu ungenau. Dazu kommen wir aber später.

 

[rosima26]

Das Ergebnis wäre dann ja definitiv false nur dass wir quasi eben wieder neustarten nur bei index + 1 würde ich sagen

 

[rosima26]

Also das Verständnisproblem liegt grade einfach da, dass wir ja zwei völlig unterschiedliche Fälle betrachten. Also erstmal möchte ich mit dem index ja durch das Array iterieren um zu summieren bis Summe = 0. Wenn das nicht der Fall ist möchte ich aber ja bei index + 1 beginnen und so das Array durchgehen. Wie soll das denn zu bewerkstelligen sein mit einer Variablen

 

[rosima26]

In meinem Kopf ist einfach dieses Schleifenkonstrukt und ich krieg das quasi nicht in rekursion "übersetzt"

 

[rosima26]

Ich verstehe auch nicht wie ich den Algorithmus dann terminieren soll. Der wüsste ja nichtmal ob jetzt alle Kombinationen durchprobiert sind weil Index durchläuft das Array ja prinzipiell immer auf 2 Arten: Einmal um den Startpunkt zu bestimmen und einmal um zu Summieren also quasi als Laufvariable. Mir erscheint das grade irgendwie unmöglich 😂

 

[KonradN]

Ja, du hast keine Schleife.

Alles, was Du hast, ist die Betrachtung einer Momentaufnahme. Du hast eine Summe, Du hast (ggf) ein aktuelles Element und Du hast einen Rest.

Wenn es kein aktuelles Element gibt, dann gibt es (in diesem Ablauf) keine Summe 0 und da es natürlich auch keine weiteren Elemente gibt, ist da auch nichts weiter machbar. Es wird also false zurück gegeben.

Wenn es das Element gibt, dann kann man prüfen, ob wir jetzt ein Teilarray haben mit Summe 0. Wie können wir zu einer Summe 0 kommen?
(Hier sind zwei Fälle zu betrachten!). Wenn wir auf Summe 0 kommen, dann ist die Frage, ob es so ein Teilarray ja klar beantwortet und man kann true zurück geben.

Wenn das nicht der Fall ist, dann ist die Frage: Mit welchen Aufrufen können wir nun weiter rekursiv arbeiten?

 

[rosima26]

Man könnte vielleicht den Index dazu benutzen das Array in kleine Teile aufzuteilen und dann zu prüfen ob die jeweils 0 ergeben?

 

[KonradN]

Man könnte vielleicht den Index dazu benutzen das Array in kleine Teile aufzuteilen und dann zu prüfen ob die jeweils 0 ergeben?

Wie sollte dann dieser rekursive Algorithmus aussehen? Was willst Du da wie machen?

Wir haben doch eigentlich einen Algorithmus skizziert - da müsste man nur die jeweiligen Punkte noch final mit Leben füllen.

 

[rosima26]

Ja das klappt nicht, bin nur völlig überfragt und frage mich ob der Ansatz so überhaupt durchführbar wäre

 

[KonradN]

Also den rekursiven Algorithmus habe ich skizziert, die Abbruchbedingung haben wir bereits mit index >= length des arrays.

Uns fehlt eine Prüfung, ob wir eine Teilsumme 0 haben. Dazu haben wir:
a) den Wert des aktuellen Feldes
b) die Summe von Feldern vor unserem Feld.
Wie kommen wir aus diesen Angaben ggf. zu einem Teilarray mit Summe 0?

 

[rosima26]

Wie haben wir die Summe der Felder die vor uns liegen ? Wir haben den Wert des aktuellen Feldes mit liste[index]. Das verstehe ich

 

[KonradN]

Wie haben wir die Summe der Felder die vor uns liegen ?

public boolean subsetSum(int[] liste, int index, int aktuelleSumme)

 

[rosima26]

Achso ja, die vorherige Summe.
Wir könnten schauen ob der jeweilige Wert im Feld die Summe zu 0 werden lässt. Aber das wäre ja naiv weil wenn im einen Feld 5 steht, die Summe schon 5 ist und im nächsten -10 steht würde das nicht funktionieren

 

[KonradN]

Wir betrachten nur die aktuelle Situation … was mit den folgenden Feldern ist, ist jetzt egal. Das kommt erst später. Nicht mehrere Dinge auf einmal machen!

Also noch einmal: was für Möglichkeiten haben wir, um auf 0 zu kommen?

 

[rosima26]

na entweder ja oder nein ? Also entweder ist summe + aktuelles Feld halt 0 oder nicht ?!

 

[KonradN]

Das ist ein Fall. Es gibt aber noch einen Fall. Die Länge eines Subarrays kann ja auch 1 sein. Was wäre der zweite Fall?

 

[KonradN]

Und was ist Dein Vorschlag, wie man da helfen kann? Nur so ein Zitat hilft nicht weiter.

na entweder ja oder nein ? Also entweder ist summe + aktuelles Feld halt 0 oder nicht ?!

Von mir aus können wir das dabei auch belassen. Dann ist das der Check des aktuellen Elements.

Dann müssen wir jetzt nur einmal schauen, was für Fälle wir dann im Anschluss klären müssen. Das können wir ja einmal an paar Beispielen ausführen.

Wir hatten eine Summe von 5, aktuelles Element 5. Was für Fälle kann es geben, damit mit dem nächsten Element ein SubArray mit Summe 0 vorhanden ist?

 

[mihe7]

Wir betrachten nur die aktuelle Situation … was mit den folgenden Feldern ist, ist jetzt egal. Das kommt erst später.

Das sollte man nochmal klar hervorheben, denn das ist in meinen Augen die Essenz der Rekursion und der dazugehörigen Denkweise: kann das Problem im aktuellen Schritt gelöst werden? Ja, dann ist man fertig, ansonsten kann die Lösung des Problems nur im Rest liegen - der einfach rekursiv behandelt wird.

Deutlich wird das z. B. beim Suchen in einer Liste: ist das aktuelle Element das gesuchte? Ja, dann ist man fertig. Ansonsten kann sich das gesuchte Element nur im Rest der Liste befinden, also durchsucht man eben diesen. Wenn die Liste leer ist, ist die Suche erfolglos:

public <T> boolean contains(List<T> elements, T elem) {
    if (elements.isEmpty()) return false; // leere Liste enthält elem betimmt nicht
    if (elements.get(0).equals(elem)) return true; // Element wurde gefunden
    return contains(elements.subList(1, elements.size()), elem); // Lösung kann sich nur im Rest befinden.
}

 

[mihe7]

NB: den Google-Joke gibts tatsächlich noch

 

[KonradN]

NB: den Google-Joke gibts tatsächlich noch

Anhang anzeigen 18741

Auf sowas muss man aber auch erst einmal kommen ... Das sind schon lustige Dinge. ... So habe ich neulich gefunden, dass man bei Siri die Taschenlampe mit "Lumos" anmachen kann. Meine Frau war dann aber ganz enttäuscht: Nox kannte Siri dann nicht.

 

[yfons123]

"Lumos"

aha also warst du derejenige welche ... der statt expecto patronum einfach expensive petrolium raus gehauen hat...

 

[mihe7]

aha also warst du derejenige welche ... der statt expecto patronum einfach expensive petrolium raus gehauen hat...

Das haben wir jetzt von dieser Siri, dieser dummen Nuss.

 

[KonradN]

aha also warst du derejenige welche ... der statt expecto patronum einfach expensive petrolium raus gehauen hat...

Nee, das war Putin mit seinem Elderstab ...