Kakuro - Mögliche Anordnungen < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:25 So 23.01.2011 | | Autor: | Piezke |
Ich habe vor einen Algorithmus zum Erstellen von Kakuros (Logikrätsel) zu programmieren und mache mir grade ein paar Gedanken dazu.
Da ich nicht recht sicher bin wohin mit dieser Frage dachte ich mir: "Logik hört sich gut an".
Ich habe eine Menge M:={1,2,3,4,5,6,7,8,9}.
1)
Wieviele Kombinationsmöglichkeiten habe ich wenn ich 1 Element der Menge wähle, wieviele wenn ich 2 Elemente der Menge wähle usw.
Hierbei ist die Anordnung der Elemente egal und es darf kein Element zweinmal gewählt werden.
Also lösbar per Binominalkoeffizienten. z.B.
[mm] \vektor{9 \\ 3} [/mm] = 84
2)
Wie bei 1) mit dem Unterschied, dass nun auch alle möglichen Anordnungen betrachtet werde sollen.
z.B. 3 Elemente aus M führen zu 84 Kombinationen und hierzu noch die Permutationen !3
=> 84 * 6 = 504 Kombinationen (inkl. Anordnungen)
Vollständige Tabelle:
Anzahl - Kombinationen - Kombinationen
Elemente ohne Anordnung mit Anordnung
1 9 9
2 36 72
3 84 504
4 126 3024
5 126 15120
6 84 60480
7 36 181440
8 9 362880
9 1 362880
Nun würde ich gerne Erfahren ob meine Überlegungen bis hierhin richtig sind bevor ich weitermache. Daher würde ich mich sehr über eine Antwort freuen.
MFG
Malte
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Do 27.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
> Ich habe vor einen Algorithmus zum Erstellen von Kakuros
> (Logikrätsel) zu programmieren und mache mir grade ein
> paar Gedanken dazu.
>
> Da ich nicht recht sicher bin wohin mit dieser Frage dachte
> ich mir: "Logik hört sich gut an".
>
> Ich habe eine Menge M:={1,2,3,4,5,6,7,8,9}.
>
> 1)
> Wieviele Kombinationsmöglichkeiten habe ich wenn ich 1
> Element der Menge wähle, wieviele wenn ich 2 Elemente der
> Menge wähle usw.
>
> Hierbei ist die Anordnung der Elemente egal und es darf
> kein Element zweinmal gewählt werden.
>
> Also lösbar per Binominalkoeffizienten. z.B.
> [mm]\vektor{9 \\ 3}[/mm] = 84
>
> 2)
> Wie bei 1) mit dem Unterschied, dass nun auch alle
> möglichen Anordnungen betrachtet werde sollen.
>
> z.B. 3 Elemente aus M führen zu 84 Kombinationen und
> hierzu noch die Permutationen !3
>
> => 84 * 6 = 504 Kombinationen (inkl. Anordnungen)
>
> Vollständige Tabelle:
>
> Anzahl - Kombinationen - Kombinationen
> Elemente ohne Anordnung mit Anordnung
>
> 1 9 9
> 2 36 72
> 3 84 504
> 4 126 3024
> 5 126 15120
> 6 84 60480
> 7 36 181440
> 8 9 362880
> 9 1 362880
>
>
> Nun würde ich gerne Erfahren ob meine Überlegungen bis
> hierhin richtig sind bevor ich weitermache. Daher würde
> ich mich sehr über eine Antwort freuen.
>
> MFG
>
> Malte
>
Hallo Malte,
mit den obigen Rechnungen hast du dich offenbar damit
beschäftigt, auf wie viele Arten man eine Zeile oder
Spalte eines Kakuro-Spiels (oder einen Teilabschnitt
davon) der Länge r mit Zahlen belegen kann, die aus r ver-
schiedenen der insgesamt möglichen n=9 Ziffern bestehen.
Deine Rechnungen sind richtig. Die Bezeichnungen der
kombinatorischen Funktionen, die du hier benutzt,
sind
C(n,r) = Anzahl Möglichkeiten, aus einer vorgegebenen
Menge von n Elementen eine (ungeordnete!) Teilmenge
von genau r (verschiedenen!) Elementen auszuwählen
P(n,r) = Anzahl Möglichkeiten, aus Elementen aus einer
vorgegebenen Menge von n Elementen eine aus lauter
verschiedenen Gliedern bestehende (geordnete!) Folge
der Länge r zu bilden
Es gilt $\ P(n,r)\ =\ [mm] \frac{n!}{(n-r)!}$ [/mm] und $\ C(n,r)\ =\ [mm] \frac{n!}{r!*(n-r)!}$
[/mm]
Die Arbeit an einem Programm, das Kakuros erstellt,
wird dich wohl noch vor viele Herausforderungen stellen.
Eine Hauptschwierigkeit vermute ich dabei darin, zu
garantieren, dass nur Kakuros mit einer eindeutigen
Lösung produziert werden. In den in Zeitschriften etc.
veröffentlichten Kakuros ist dies jedenfalls eine zentrale
Voraussetzung. Vielleicht verzichtest du aber (wenigstens
vorerst) darauf, diese Super-Knacknuss zu knacken ...
LG Al-Chw.
|
|
|
|
