Kombinatorik-Algorithmus < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:58 Mi 15.03.2006 | | Autor: | mickpf |
| Aufgabe | Hallo Leute,
ich suche einen Algorithmus zur Lösung des Standardproblems der Kombinatorik, den ich in irgend einer Programmiersprache umsetzen kann.
Das Standardproblem besteht im folgenden:
a) Gegeben: z. B. 3 Farben - rot geld blau
b) Gesucht der Algorithmus, der mir alle möglichen Kombinationen dieser
Farben ausgibt:
rot - gelb - blau, rot - blau - gelb, gelb - rot - blau, u.s.w.
Wenn möglich, bitte per Email antworten.
mit freundlichen Grüßen
Michael
P.S.: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
Hallo Leute,
ich suche einen Algorithmus zur Lösung des Standardproblems der Kombinatorik, den ich in irgend einer Programmiersprache umsetzen kann.
Das Standardproblem besteht im folgenden:
a) Gegeben: z. B. 3 Farben - rot geld blau
b) Gesucht der Algorithmus, der mir alle möglichen Kombinationen dieser
Farben ausgibt:
rot - gelb - blau, rot - blau - gelb, gelb - rot - blau, u.s.w.
Wenn möglich, bitte per Email antworten.
mit freundlichen Grüßen
Michael
P.S.: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und einen guten Nachmittag,
also nehmen wir an, wir haben eine Menge [mm] F=\{f_1,\ldots , f_k\}
[/mm]
von Farben und wollen alle Farbkombinationen generieren.
Wenn die Zahl k der Farben fix ist, können wir das durch k ineinander geschachtelte
for-Schleifen tun:
for [mm] i_1:= [/mm] 1 to k
for [mm] i_2:=1 [/mm] to k
[mm] \ldots [/mm]
for [mm] i_k:=1 [/mm] to k
print [mm] (f_{i_1},\ldots [/mm] , [mm] f_{i_k})
[/mm]
Falls nun die Zahl der Farben nicht konstant ist, so
koennen wir es wie folgt machen:
prozedur finde-nachfolger [mm] ((i_1,\ldots [/mm] , [mm] i_k) [/mm] als Array/Liste variabler Länge, int k (Angabe der Länge))
begin
int j,h
for (j=1; j<=k && [mm] i_j==k [/mm] ; j++);
if (j==k+1)
(entweder:) return [mm] (1,1,\ldots [/mm] , 1) (fang vorne an)
(oder:) print(letzte Kombination, fertig)
exit
else
//Erhoehe [mm] i_j [/mm] um 1 und setze [mm] i_1=...=i_{j-1}=1
[/mm]
for (h=0; h<j; h++) [mm] i_h:=1
[/mm]
[mm] i_j:= i_j+1
[/mm]
end
und das dann in ein Hauptprogramm einbauen !
Ist das Prinzip klar geworden ?
Gruss,
Mathias
|
|
|
|
