Bildung von Potenzmenge (Teilmengen)

s_boeckmann

Hallo zusammen,

für folgende Problemstellung bräuchte ich Eure Hilfe:

Ich habe ein 2-dimensionale Array in dem hinterlegt ist, ob ein Student (s) in einem Kurs (k) eine Klausur schreiben will [true/false]. Da nicht jeder Student in allen Kursen eine Klausur schreibt, besteht die Möglichkeit, Klausuren parallel schreiben zu lassen - unter der Voraussetzung, daß bei den zusammengelegten Klausurterminen jeder Student nur eine Klausur schreibt.
Ich habe also eine Menge von Kurse, ich nehme also den ersten Kurs und untersuche, mit welchem weiteren Kurs der erste Kurs parallel geprüft werden kann. Im Prinzip müßte ich also alle Teilmenge bilden, um zu überprüfen bei welcher Teilmenge - in der jeder Student nur eine Klausur schreiben würde - sich im ersten Durchgang die meisten Studenten prüfen lassen wollen. Diese Kurse werden dann als terminlich erste Klausur angesetzt, gleichzeitig werden diese Kurse aus der ursprünglichen Liste entfernt und die obige Prozedur wiederholt, bis alle Kurse einen Klausrtermin haben bzw. die Menge leer ist.

Im ersten Schritt bräuchte ich also einen Algorithmus, der aus einer Menge die Potenzmengen (Teilmengen) ausgibt:

Menge={1,2,3}
Ausgabe
1
1,2
1,2,3
1,3
2
2,3
3

Umsetzten wollte ich das Programm in Java.
Für Eure Hilfe möchte ich mich schon jetzt bedanken.

Gruß

Sebastian

jeuneS2

Die Potenzmenge bekäme man ca. so:

Code

P(A) {
  if (A == {}) {
    return {};
  } else {
    B = P(A\A[0]);
    C = B;
    for-each e in C {
       e = e union A[0];
    }
    return B union C;
  }
}

Alles anzeigen

bzw. in Scheme

Code

(define (P A)
  (if (eqv? A '()) '(())
      (let ((B (P (cdr A))))
	(let ((C (tree-copy B)))
	  (append B (map (lambda (e) (cons (car A) e)) C))))))

Allerdings würde ich nicht die Potenzmenge bilden (Aufwand 2^n), sondern der ersten Klausur einen vorläufigen Termin zuweisen, so viele Kurse dazunehmen wie möglich und am Ende nach der Anzahl der Studenten sortieren. Das ist zwar nicht optimal, aber dafür bleibt der Aufwand auch bei einer größeren Anzahl von Klausuren vertretbar.

Bildung von Potenzmenge (Teilmengen)

Jetzt mitmachen!

Benutzer online in diesem Thema