Opened by ariser at 2013-10-05 21:31
User since
2012-05-04
1054 Artikel
BenutzerIn
2012-05-04
1054 Artikel
BenutzerIn
Dazu drei Kommentare:
1. von deiner Beschreibung mit den Mengen ist nicht klar geworden, was du tun willst. Wohl aber hat das Beispiel klar gemacht, was zu tun ist.
2. Rekursive Algorithmen sind nicht immer schlecht. Bei Endrekursion muss der Stack auch nicht überlaufen (hängt von den Optimierungen eines Compilers ab)
3. Zur Lösung musst du dir erst einmal überlegen, dass du eh alle 4 Elemente einmal brauchst. Es bleiben also nur noch 6 Wagen übrig, die frei vergeben werden können.
Die Anzahl der Möglichkeiten ist binomial(anzahl_wagentypen + anzahl_verbleibende_wagen - 1, anzahl_verbleibende_wagen) = binomial(4+6-1, 6) = 9!/(6! * 3!) = 84
Stichwort ist vielleicht "Ziehen mit Zurücklegen".
Edit: ich sehe gerade, dass du gar nicht die Anzahl haben wolltest, sondern wirklich alle Ergebnisse. Das würde ich immer rekursiv lösen. Vielleicht so:
Last edited: 2013-10-06 01:21:03 +0200 (CEST)
1. von deiner Beschreibung mit den Mengen ist nicht klar geworden, was du tun willst. Wohl aber hat das Beispiel klar gemacht, was zu tun ist.
2. Rekursive Algorithmen sind nicht immer schlecht. Bei Endrekursion muss der Stack auch nicht überlaufen (hängt von den Optimierungen eines Compilers ab)
3. Zur Lösung musst du dir erst einmal überlegen, dass du eh alle 4 Elemente einmal brauchst. Es bleiben also nur noch 6 Wagen übrig, die frei vergeben werden können.
Die Anzahl der Möglichkeiten ist binomial(anzahl_wagentypen + anzahl_verbleibende_wagen - 1, anzahl_verbleibende_wagen) = binomial(4+6-1, 6) = 9!/(6! * 3!) = 84
Stichwort ist vielleicht "Ziehen mit Zurücklegen".
Edit: ich sehe gerade, dass du gar nicht die Anzahl haben wolltest, sondern wirklich alle Ergebnisse. Das würde ich immer rekursiv lösen. Vielleicht so:
Code (perl): (dl
)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
my @typeset = qw(P K L G); my $length = 10; strangemultiset($length, \@typeset, 0, ''); sub strangemultiset { my ($len, $set, $start, $string) = @_; if ($len == 0) { print "$string\n"; return; } my $max = $len - @$set + $start + 1; my $min = $start == @$set - 1 ? $max : 1; for my $currentLen ($min..$max) { strangemultiset($len-$currentLen, $set, $start + 1, $string . ($set->[$start] x $currentLen)); } }
Last edited: 2013-10-06 01:21:03 +0200 (CEST)