Partition (Mengenlehre)

[chris9205]

Hallo liebe java community,

Ich hab folgende Frage und zwar, hab ich in 2 Wochen einen Mathematik Test und wir dürfen in diesem Test unseren PC benutzen. Daher wollte ich mir ein Programm schreiben das mir die Partitionen der Mengenlehre selber zusammenstellt, da dies nur Zeit aufreibend ist und ich diese Zeit besser nützen könnte im Test.

So jetzt meine Frage wie schaff ich es dies zu programmieren? Beispiel:
Meine Partition besteht aus : P={a,b,c,d}.
Diese Partition entspricht 15 verschiedenen Aufteilungen. Doch ich hab im Moment keine Ahnung wie ich dies mit einem Programm lösen sollte, hab auch schon gegoogelt, jedoch nichts hilfreiches gefunden.

Im Moment hab ich mir zwar schon ein Programm zusammen gebastelt was mir die Partitionen zusammen stellt bis Maximal 4 Werte, jedoch ist dies fest einprogrammiert, damit will ich sagen dass ich z.b 15. verschiedene Kombinationen mit [Java]System.out.format("%s%s%s%s",tab[0],tab[1],tab[2],tab[3]);[/Java] fest einprogrammiert habe. Doch dies genügt mir jedoch nicht, ich will es dynamisch erstellen, einfach zum Interesse halber.

Ich hoffe jemand kann mir dabei helfen, wenn es jedoch nicht möglich ist, ist es auch nicht schlimm, denn ich glaube nicht, dass ich nicht mehr als 15 Partitionen aufschreiben muss, da 51 ein wenig übertrieben wäre^^.

MFG

chris9205

 

[langhaar!]

Willst du alle möglichen Teilmengen ermitteln?

Das geht z.B. über Rekursion.
Du fängst bei Element a an und ermittelst alle Teilmengen mit a.
Dazu wiederum müssen alle Teilmenge ohne a bestimmt werden.
=> Rekursion

Das Programm müsste also ungefähr aus einer for Schleife und einem rekursiven Aufruf bestehen.

 

[langhaar!]

Die doppelten Teilergebnisse müssen noch entfernt werden, ansonsten tut es fogendes Programm:

    public void rekSet(String set) {
		
		if (set.length() > 0)
			System.out.println(set);
		for (int i = 0; i < set.length(); i++) {
			
			String s = set.substring(i, i+1);
			rekSet(set.replace(s, ""));
		}
       }

       public static void main(String[] args) {
		
		Test test = new Test();
		test.rekSet("abcd");
		
	}

 

[Marco13]

Eine Partition ist nicht eine Teilmenge, sondern eine Menge von Teilmengen, die jeweils paarweise disjunkt sind und alle vereinigt die Gesamtmenge ergeben. Wenn's nicht effizient sein muss geht das vom Aufand her: Im Prinzip nochmal eine "meta-Rekursion" über die schon angedeutete: Man bestimmt alle Teilmengen, und bei jeder für die restliche Menge wieder rekursiv alle Teilmengen - bis man bei der leeren Menge ist. Da sind dann etliche doppelt dabei, aber notfalls fügt man die in ein Set ein...

 

[chris9205]

Euch schon mal vielen Dank für die schnellen Antworten, ich hab dein Programm mal benutzt "langhaar!" und ja dies bekomme ich heraus bei dem string "123"
123
23
3
2
13
3
1
12
2
1

Ok, dass da noch doppelte drin sind weiß ich doch wie weiß ich jetzt welche Mengen eine Partition bilden?

Denn wenn ich die Partiton {1,2,3} aufteile, kommen diese Resultate heraus:

{{1,2,3}}
{{1},{2},{3}}
{{1},{2,3}}
{{3},{1,2}}
{{2},{1,3}}

 

[langhaar!]

Lies mal den Kommentar von marco13 zu meinem Programm.