Teilmengensummen-Problem

[HBC]

Guten Tag,

meine Aufgabe lautet es ein Programm zu schreiben, dass alle Teilmengen aus einer Menge bestimmt, deren Elemente die Summe s besitzen. Die Menge und s sollen vom Benutzer angegeben werden.
Beispiel: Es seien A = {3, 1, 6, 8, 12, 4, 5, 9} und s = 15. Die Mengen {1, 3, 5, 6},
{1, 5, 9}, {1, 6, 8}, {3, 4, 8}, {3, 12}, {4, 5, 6} und {6, 9} sind die gesuchten Teilmengen.
Das ganze soll mithilfe einer rekursiven Methode gelöst werden.

Ich habe schon versucht, dass Problem mit einer Menge for-Schleifen zu lösen, das hat auch einigermaßen geklappt, aber dieser Weg ist nur iterativ und deshalb nicht für eine beliebig große Menge und ein beliebig großes s möglich.

Ich hätte eine Idee, wie man es rekursiv lösen könnte, man nimmt ein zweites leeres Array hinzu und nimmt einfach nach und nach jedes Element aus dem ersten Array und tut es in das zweite. Nur hab ich keine Ahnung, ob das sinnvoll ist und ich hab keine Ahnung wie ich das in ein Programm umsetzen soll
Könnte ihr mir vielleicht helfen ?

MfG

 

[Marco13]

Je nachdem, wie konkret der Ansatz schon sein soll:

Für M={3,5,1,2,4} und s=5 listet man auf
alle Lösungen für M={5,1,2,4} und s=2, jeweils vereinigt mit {3}
alle Lösungen für M={3,1,2,4} und s=0, jeweils vereinigt mit {5}
alle Lösungen für M={3,5,2,4} und s=4, jeweils vereinigt mit {1}
alle Lösungen für M={3,5,1,4} und s=3, jeweils vereinigt mit {2}
alle Lösungen für M={3,5,1,2} und s=1, jeweils vereinigt mit {4}

 

[HBC]

So meinte ich das nicht, dass Programm muss ja ertsmal eine ganze Menge Kombinationen testen und dann gucken welche Kombination die Summe s hat, sodass wenn man M={3,5,1,2,4} und s=5 hat, die Teilmengen {5}, {3,2}, {1,4} rauskommen.

 

[Morpe]

In welcher Form liegen denn die Ausgangs Mengen vor? In einem Array, einer Liste oder einem Vector?

 

[HBC]

In einem Array

 

[Morpe]

Ich nehme mal als Beispiel die Ausgansmenge {5, 3, 2, 1, 4} und s = 8

Y - die Verwendeten Elemente bilden eine Teilmenge
X- die verwendeten Elemente bilden keine Teilmenge
Fettgedruckt sind alle Elemente.

8-5 = 3
_3-3=0 Y
_3-2=1
__1-1=0 Y
__1-4=-3 X
_3-1=2
__2-4=-2 X
_3-4=-1 X
8-3 = 5
_5-2=3
__3-1=2
___2-4=-2 X
__3-4=-1 X
_5-1=4
__4-4=0 Y
_5-4=1 X Da keine Elemente mehr vorhanden
8-2=6
.
.
.
.

Ich hoffe du verstehst mein Beispiel. Ob das wirklich Rekursiv implementierbar ist musst du selber herausfinden.

 

[Tobse]

Dafür müssten zwei for-schleifen und eine rekursive funktion reichen.

ArrayList<Integer[]> validCombis=new ArrayList<Integer[]>();
void goThrough(int[] menge, int focusedIndex, int maxTeilmengenGroesse) {
    // ...
    // gefunden!
    validCombis.add(/* das gefundene array */);
}
// menge ist ein int[]
// s ist ein int
// Durchlaufe alle einträge der Menge
for (int i=0;i<menge.length;i++) {
    // Für jedes probiere alle kombination mit größe 0 bis menge.length aus
    for (int n=0;i<menge.length;n++) {
        goThrough(menge, i, n);
    }
}
// Falls validCombis leer ist wurde ncihts gefunden
// Falls nicht kannst du die ergebnisse ja präsentieren.

Die Funktion goThrough musst du dann selbst implementieren, sollte aber nichmehr ganz so schwer sein.

 

[XHelp]

@Tobse a) ich sehe keine Rekursion b) das sind nicht alle Kombinationen

 

[Tobse]

Ja, ist mir auch aufgefallen. Wenn man das 2. Argument von goThrough durch [c]int[] focusedIndex[/c] ersetzt, kann sich die Funktion serwohl rekursiv aufrufen und auch alle kombinationen prüfen.

 

[XHelp]

Naja, aber wozu ist dann die andere? Und was soll die da im Parameter verändern?
An TO's Stelle würde ich die Lösung von Marco weiter verfolgen, da muss man auch nicht die gesamte Potenzmenge aufbauen.

 

[HBC]

Da ich mir ziemlich unsicher bin, ob ich dass mit einer rekursiven Methode noch lösen werde, möchte ich sicher gehen und meinen ersten unrekursiven Lösungsweg als letzten Ausweg benutzen.
Bloß das Problem ist, dass mein Programm manche Teilmengen doppelt ausgibt und manche Teilmengen doppelte Elemente enthalten. Ich habe gelesen, dass man das ganz einfach mit HashSet ausbügeln kann. Bloß da ich ziemlicher Anfänger bin, weiß ich nicht genau wie ich das implementieren muss, könntest du mir da bitte weiterhelfen?

So sieht mein Programm aus:

class TeilMengenSumme {
  static void einermengen(int[] b, int s) {
    for (int i = 0; i < b.length; i++) {
      if (b[i] == s) {
        System.out.println(b[i])
        System.out.println("  ");
      }
    }
  }
  static void zweiermengen(int[] b, int s) {
    for (int i = 0; i < b.length; i++) {
      for (int j = 1; j < b.length; j++) {
        if (b[i]+b[j] == s) {
          System.out.println("  " + b[i] + "  " + b[j]);
          System.out.println(" ");
        }
      }
    }
  }
  static void dreiermengen(int[] b, int s) {
    for (int i = 0; i < b.length; i++) {
      for (int j = 1; j < b.length; j++) {
        for (int k = 2; k < b.length; k++) {
          if (b[i]+b[j]+b[k] == s) {
            System.out.println("  " + b[i] + "  " + b[j] + "  " + b[k]);
            System.out.println(" ");
          }
        }
      }
    }
  }
  static void vierermengen(int[] b, int s) {
    for (int i = 0; i < b.length; i++) {
      for (int j = 1; j < b.length; j++) {
        for (int k = 2; k < b.length; k++) {
          for (int l = 3; l < b.length; l++) {
            if (b[i]+b[j]+b[k]+b[l] == s) {
              System.out.println("  " + b[i] + "  " + b[j] + "  " + b[k] + "  " + b[l]);
              System.out.println(" ");
            }  
          }
        }
      }
    }
  }     
  public static void main(String[] a) {
    int s = Integer.parseInt(a[0]);
    System.out.print(" Zahlen: ");
    int[] feld = new int[a.length];
    for (int i=1; i < a.length; i++) {
      feld[i] = Integer.parseInt(a[i]);
      System.out.printf(" " + "%1d ", feld[i]);      
    }
    System.out.println();
    System.out.println(" Summe:   " + s);
    System.out.println(" ");

    einermengen(feld,s);
    zweiermengen(feld,s);
    dreiermengen(feld,s);
    vierermengen(feld,s);
  }
}

 

[XHelp]

Es kann vorkommen, dass deine Indices gleich sind, du müsstest also in den Schleifen auf Gleichheit prüfen.
Aber das ist keine Rekursion und bringt dich ohnehin nicht weiter. Was ist denn, wenn bei der Eingabe 6er Mengen gebildet werden müssen? Oder 200er Mengen?

 

[HBC]

Ist mir schon klar, dass das keine Rekursion ist und nicht für beliebig große Mengen geeignet ist.
Aber da ich das abgeben muss und ich nicht weiß ob ich dass noch mit einer rekursiven Methode hinbekomme, wollte ich nur auf Nummer sicher gehen, damit ich irgendetwas abgeben kann wenn ich es nicht hinbekomme.

 

[Tobse]

Also, ich wollte das auch genauer wissen und hab das jetzt zusammengeschustert, leider in PHP. Folgende funktionen werden benutzt (von PHP in Java übersetzt):

boolean check(int[] menge, int targetSize) {
}
// focusedIndices soll verhindern, dass die Gleiche zahl mehrfach verwendet wird und eine endlosschleife entsteht.
void goThrough(int[] menge, int[] focusedIndices, int size, int targetSize) {
     // Probiert alles möglich durch
     // Rekursion mit gleichem menge, erweitertem focusedIndices und size-1
}
for (int i=0;i<j;i++) 
	for (n=1;n<=j;n++)
		goThrough(menge, new int[] { i }, n, targetSize);

Und 3 Weitere, um mehrfach gefundene Kombinationen auszusortieren, da der code z.B. bei deinem Beispiel 104 Möglichkeiten findet. Einzigartig sind aber nur 7.

[EDIT]check() vergessen[/EDIT]

 

[Marco13]

So meinte ich das nicht, dass Programm muss ja ertsmal eine ganze Menge Kombinationen testen und dann gucken welche Kombination die Summe s hat

Sicher. Man würde die Rekursion abbrechen, wenn die Summe der bisher gefundenen Zahlen größer als s ist:

Für M={3,5,1,2,4} und s=5 listet man auf
   alle Lösungen für M={5,1,2,4} und s=2, jeweils vereinigt mit {3}, also
       alle Lösungen für M={1,2,4} und s=-3, jeweils vereinigt mit {3, 5}, also --- !!! KEINE MEHR
   alle Lösungen für M={3,1,2,4} und s=0, jeweils vereinigt mit {5}, also genau {5} !!!
   alle Lösungen für M={3,5,2,4} und s=4, jeweils vereinigt mit {1}, also 
       alle Lösungen für M={5,2,4} und s=1, jeweils vereinigt mit {1, 3} ...
...

Und nur die Lösungen ausgeben, die auch Stimmen. Es wurden ja jetzt schon ein paar rekursive Ansätze gepostet, hast du davon einen ausprobiert? (Wenn du eine iterative Lösung abgibst, musst du im schlechtesten Fall mit 0 Punkten rechnen :bahnhof: )

 

[Tobse]

Ich weiss jetzt nicht so recht, ob das noch was bringt, aber die teilmengen-Datei lungert hier bei mir rum und ich dachte ich poste die dann einfach hier, bevor ich sie lösche. Vllt. bringt sie dem TS oder jmd. anders noch was.

<?php
error_reporting(E_ALL);
$matches=array();
function sortOut(array &$ar) {
	$j=count($ar);
	if ($j==0) return;
	for ($i=0;$i<$j;$i++) {
		if (!isset($ar[$i])) continue;
		$pivot=$ar[$i];
		foreach ($ar as $key=>$n) {
			if ($key==$i) continue;
			if (equals($pivot, $n)) unset($ar[$key]);
		}
	}
	$ar=array_merge(array(), $ar);
}
function equals(array $one, array $two) {;
	foreach ($two as $n) {
		if (!in_array($n, $one)) return false;
	}
	foreach ($one as $n) {
		if (!in_array($n, $two)) return false;
	}
	return true;
}
function createSub(array $indices) {
	global $menge;
	$subMenge=array();
	foreach ($indices as $index) $subMenge[]=$menge[$index];
	return $subMenge;
}
function sumOf(array $menge) {
	$sum=0;
	foreach ($menge as $n) $sum+=$n;
	return $sum;
}
function check(array $indices) {
	global $targetSize;
	$sub=createSub($indices);
	if (sumOf($sub)==$targetSize) $matches[]=$sub;
}
function goThrough(array $menge, $fIndices, $size) {
	global $matches, $targetSize;
	$j=count($menge);
	$k=count($fIndices);
	if ($size==1) check($fIndices);
	$fIndices[]=-1;
	if ($size==1) {
		for ($i=0;$i<$j;$i++) {
			if (in_array($i, $fIndices)) continue;
			$fIndices[$k]=$i;
			$sub=createSub($fIndices);
			if (sumOf($sub)==$targetSize) $matches[]=$sub;
		}
	} else {
		for ($i=0;$i<$j;$i++) {
			if (in_array($i, $fIndices)) continue;
			$fIndices[$k]=$i;
			$sub=createSub($fIndices);
			if (sumOf($sub)>$targetSize) break;
			goThrough($menge, $fIndices, $size-1);
		}
	}
}
if (!defined("STDOUT")) exit("Über Konsole aufrufen!");
fwrite(STDOUT, "Geben sie die Menge ein. Mit kommas getrennt und ohne { }\n");
$menge=explode(",", fread(STDIN, 10000));
fwrite(STDOUT, "Geben sie die Summe der Teilmengen ein\n");
$targetSize=intVal(fread(STDIN, 12));
$j=count($menge);
for ($i=0;$i<$j;$i++) $menge[$i]=intVal(trim($menge[$i]));
for ($i=0;$i<$j;$i++) 
	for ($n=1;$n<=$j;$n++)
		goThrough($menge, array($i), $n);
sortOut($matches);
if (count($matches)==0) {
	fwrite(STDOUT, "Es wurde keine Teilmenge gefunden.\n");
} else {
	fwrite(STDOUT, "Folgende Teilmengen wurden gefunden:\n");
	$j=count($matches);
	for ($i=0;$i<$j;$i++) {
		fwrite(STDOUT, "{".implode(", ", $matches[$i])."}\n");
	}
}
exit();
?>

 

[Landei]

Ich glaube, ihr denkt hier zu kompliziert. Wenn man die Werte in einem Array der Länge n gegeben hat, ist jede Teilmenge eindeutig einer Zahl k zwischen 0 und (2^n)-1 zugeordnet. Zum k-ten Set gehören diejenigen Array-Elemente, bei denen das entsprechende Bit in k gesetzt ist:

Set [1,5,8]

n = 3
k = 0 .. (2^3)-1 = 0 .. 7

0 = 000 -> []
1 = 001 -> [8]
2 = 010 -> [5]
3 = 011 -> [5,8]
4 = 100 -> [1]
5 = 101 -> [1,8]
6 = 110 -> [1,5]
7 = 111 -> [1,5,8]

Also lässt sich die Aufgabe ganz einfach lösen, indem man eine einzige Schleife über k laufen lässt. Wenn man k statt einer Zahl mit noch mit einem BitSet repräsentiert, wird die Abfrage der Bits trivial.

 

[XHelp]

Das ist auch eine Möglichkeit. Aber bei der musst du ja immer alle Möglichkeiten durchprobieren. Was hier aber wichtiger ist: die ist nicht rekursiv.

 

[Landei]

Auch das geht einfacher:

public class SubsetSum {

    public static void main(String... args) {
        findSubsetsWithSum(15, 3, 1, 6, 8, 12, 4, 5, 9);
    }

    public static void findSubsetsWithSum(int sum, int ... values) {
        find(sum, "", 0, values);
    }

    private static void find(int sum, String subset, int index, int[] values) {
        if (sum == 0) {
           System.out.println(subset); 
        } else if (sum > 0 && index < values.length) {
           find(sum, subset, index + 1, values);
           find(sum - values[index], subset + values[index] + " ", index + 1, values);
        }
    }
}

Man beachte, dass der Algorithmus nicht alle Möglichkeiten durchgeht, sondern Teilmengen überspringt, die sowieso zu groß geworden wären. Natürlich muss man dann voraussetzen, dass die Elemente des Sets alle positiv sind.