Formel für max. Möglichkeiten einer Feldbelegung

Übersicht

BlitzBasic

Allgemein

	Jamagin Betreff: Formel für max. Möglichkeiten einer Feldbelegung	Fr, Aug 30, 2013 9:16 Antworten mit Zitat
An alle Mathematiker hier! Ich suche für mein Jewelspiel eine Formel bzw. Funktion mit der ich alle möglichen Feldbelegungen berechnen kann! Grundsatz: Ich habe eine Grafik mit 12 Einzelbildern, das Spielfeld ist 5x5. Das ergibt in Summe 12x12x12x12x12 = 248832 Möglichkeiten das jedes Einzelbild auf einer Position ist. Beispiel Felddarstellung bei Initialisierung: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Beispiel Felddarstellung erste Möglichkeit: 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 Beispiel Felddarstellung zweite Möglichkeit: 1 2 1 2 1 2 1 2 1 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 Also, es gibt die Zahlen für die Einzelbilder von 1-12 und es darf keine Zahl 2x oder mehrmals in der Y-Reihe auftreten! Wer hat sich mit so ähnlichen Berechnungen schon herumgeschlagen, weil diese Möglichkeiten von Hand aus in die Felderbelegungen zu schreiben wäre ja fast aussichtslos!!! Ich wäre echt erfreut, wenn da jemand (sehr) gute Ansätze für so eine Funktion bzw. Rekursion hätte!!! lg. Jamagin
Bevor du etwas neues beginnst, erledige das alte

Jamagin

Betreff: Formel für max. Möglichkeiten einer Feldbelegung

Fr, Aug 30, 2013 9:16
Antworten mit Zitat

An alle Mathematiker hier!

Ich suche für mein Jewelspiel eine Formel bzw. Funktion mit der ich alle möglichen Feldbelegungen berechnen kann!

Grundsatz:
Ich habe eine Grafik mit 12 Einzelbildern, das Spielfeld ist 5x5.
Das ergibt in Summe 12x12x12x12x12 = 248832 Möglichkeiten das jedes Einzelbild auf einer Position ist.

Beispiel Felddarstellung bei Initialisierung:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Beispiel Felddarstellung erste Möglichkeit:
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5

Beispiel Felddarstellung zweite Möglichkeit:
1 2 1 2 1
2 1 2 1 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5

Also, es gibt die Zahlen für die Einzelbilder von 1-12 und es darf keine Zahl 2x oder mehrmals in der Y-Reihe auftreten!
Wer hat sich mit so ähnlichen Berechnungen schon herumgeschlagen, weil diese Möglichkeiten von Hand aus in die Felderbelegungen zu schreiben wäre ja fast aussichtslos!!!

Ich wäre echt erfreut, wenn da jemand (sehr) gute Ansätze für so eine Funktion bzw. Rekursion hätte!!!

lg. Jamagin

Bevor du etwas neues beginnst, erledige das alte

	Midimaster	Fr, Aug 30, 2013 11:06 Antworten mit Zitat
Was ist den das (praktische) Ziel Deiner Berechnung? Also ich meine den Nutzen im "Spielverlauf"... Ich bin ziemlich überzeugt, dass man die von Dir gesuchte Information im Spiel nicht benötigen wird, weil es sicher anders auch geht.... Es hört sich an, als ob Du eine "Vorbelegung" suchts, die sich an die Regeln hält. Ich rate mir: machs per purem Zufall, dann prüfe das Resultat und verwerfe einfach so lange ungültige Spielfelder bis Du ein gültiges hast. Zu Deiner Berechnung für eine Y-Spalte: 1.Feld hat 12 Möglichkeiten 2.Feld hat nur noch 11 Möglichkeiten 3.Feld hat nur noch 10 Möglichkeiten 4.Feld hat nur noch 9 Möglichkeiten 5.Feld hat nur noch 8 Möglichkeiten Also 12*111098 Möglichkeiten pro Spalte jetzt sind es aber 5 Spalten, also das ganze noch mal hoch 5. Das ist ganz schön viel!!!
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe

Midimaster

Fr, Aug 30, 2013 11:06
Antworten mit Zitat

Was ist den das (praktische) Ziel Deiner Berechnung? Also ich meine den Nutzen im "Spielverlauf"...

Ich bin ziemlich überzeugt, dass man die von Dir gesuchte Information im Spiel nicht benötigen wird, weil es sicher anders auch geht....

Es hört sich an, als ob Du eine "Vorbelegung" suchts, die sich an die Regeln hält. Ich rate mir: machs per purem Zufall, dann prüfe das Resultat und verwerfe einfach so lange ungültige Spielfelder bis Du ein gültiges hast.

Zu Deiner Berechnung für eine Y-Spalte:

1.Feld hat 12 Möglichkeiten
2.Feld hat nur noch 11 Möglichkeiten
3.Feld hat nur noch 10 Möglichkeiten
4.Feld hat nur noch 9 Möglichkeiten
5.Feld hat nur noch 8 Möglichkeiten

Also 12**11*10*9*8 Möglichkeiten pro Spalte

jetzt sind es aber 5 Spalten, also das ganze noch mal hoch 5. Das ist ganz schön viel!!!

Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe

	mpreu	Fr, Aug 30, 2013 12:40 Antworten mit Zitat
genau, ich hab sowas auch mal gemacht... eigentlich sind "alle möglichen" belegungen recht unsinnig, sondern du solltest nach feldbelegung nach relevanten strukturen suchen lassen... ein paar mehr infos brauchen wir dazu schon

mpreu

Fr, Aug 30, 2013 12:40
Antworten mit Zitat

genau, ich hab sowas auch mal gemacht...
eigentlich sind "alle möglichen" belegungen recht unsinnig, sondern du solltest nach feldbelegung nach relevanten strukturen suchen lassen...

ein paar mehr infos brauchen wir dazu schon

	DAK	Fr, Aug 30, 2013 13:05 Antworten mit Zitat
Dafür verwende den Binomialkoeffizient. Die Formel die du brauchst wäre: (12 über 5) * 5 = 792 * 5 = 3960 Das 12 über 5 gibt dir die Anzahl der verschiedenen Möglichkeiten 5 Objekte aus 12 zu ziehen. Da du fünf von einander unabhängige Spalten hast, musst du dann noch mal 5 multiplizieren. Diese "über"-Funktion kann jeder wissenschaftliche Taschenrechner und heißt dort meist ncr (nicht zu verwechseln mit npr, das ist was anderes). Findet sich hin und wieder unter dem Menüpunkt PRB oder Probability wie in Wahrscheinlichkeitsrechnung.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Fr, Aug 30, 2013 13:05
Antworten mit Zitat

Dafür verwende den Binomialkoeffizient.

Die Formel die du brauchst wäre:

(12 über 5) * 5 = 792 * 5 = 3960

Das 12 über 5 gibt dir die Anzahl der verschiedenen Möglichkeiten 5 Objekte aus 12 zu ziehen. Da du fünf von einander unabhängige Spalten hast, musst du dann noch mal 5 multiplizieren.

Diese "über"-Funktion kann jeder wissenschaftliche Taschenrechner und heißt dort meist ncr (nicht zu verwechseln mit npr, das ist was anderes). Findet sich hin und wieder unter dem Menüpunkt PRB oder Probability wie in Wahrscheinlichkeitsrechnung.

Gewinner der 6. und der 68. BlitzCodeCompo

	Kruemelator	Fr, Aug 30, 2013 15:20 Antworten mit Zitat
Man kann auch die Möglichekeiten bestimmen die nicht erlaubt sind. Dürfte eine wesendlich kleinere Zahl sein. Vielleicht hilft dir das weiter. @Midimaster: Zitat: machs per purem Zufall, dann prüfe das Resultat und verwerfe einfach so lange ungültige Spielfelder bis Du ein gültiges hast Scheint sinnvoll, ist es aber nicht. Zufall bedeutet ja das der neue Zufallswert nix mit dem Vorherigen zutun hat. Könnte sein das du 1000mal immer wieder auf einer falschen Kombination landest. Ist bei 5 Spalten nicht wirklich schlimm da man das praktisch ohne Zeitaufwand neu belegen lassen kann, dennoch ist es extrem unsauber. Dann lieber eine Liste mit 12 Einträgen erschaffen und zufällig einen auswählen, ihn aus der Liste entfernen und dann in der Spalte eintragen. Solange wieder holen bis die Spalte voll ist.

Kruemelator

Fr, Aug 30, 2013 15:20
Antworten mit Zitat

Man kann auch die Möglichekeiten bestimmen die nicht erlaubt sind. Dürfte eine wesendlich kleinere Zahl sein. Vielleicht hilft dir das weiter.

@Midimaster:
Zitat:

machs per purem Zufall, dann prüfe das Resultat und verwerfe einfach so lange ungültige Spielfelder bis Du ein gültiges hast

Scheint sinnvoll, ist es aber nicht. Zufall bedeutet ja das der neue Zufallswert nix mit dem Vorherigen zutun hat. Könnte sein das du 1000mal immer wieder auf einer falschen Kombination landest. Ist bei 5 Spalten nicht wirklich schlimm da man das praktisch ohne Zeitaufwand neu belegen lassen kann, dennoch ist es extrem unsauber. Dann lieber eine Liste mit 12 Einträgen erschaffen und zufällig einen auswählen, ihn aus der Liste entfernen und dann in der Spalte eintragen. Solange wieder holen bis die Spalte voll ist.

	DAK	Fr, Aug 30, 2013 16:59 Antworten mit Zitat
In dem Fall ist die Menge der nicht erlaubten Kombinationen deutlich höher als die der Erlaubten. Sind nämlich 1240200 nicht erlaubte gegen 3960 erlaubte. Ist meistens so, wenn Elemente nur ein mal vorkommen dürfen.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Fr, Aug 30, 2013 16:59
Antworten mit Zitat

In dem Fall ist die Menge der nicht erlaubten Kombinationen deutlich höher als die der Erlaubten.
Sind nämlich 1240200 nicht erlaubte gegen 3960 erlaubte. Ist meistens so, wenn Elemente nur ein mal vorkommen dürfen.

Gewinner der 6. und der 68. BlitzCodeCompo

	Kruemelator	Fr, Aug 30, 2013 17:48 Antworten mit Zitat
Stimmt hatte einen Denkfehler, dennoch ist mit Ansatz zum Spalte füllen korrekt. Hier mal als Code. BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Dim spalte(4) SpalteFuellen() For i=0 To 4 Print spalte(i) Next Print "Beliebige Taste zum beenden." WaitKey() End Function SpalteFuellen() Local liste[11] Local element;zufaellige stelle in der Liste Local elementanzahl = 11;12 unterschiedliche Zahlen (0-11) ;Liste vorbereiten For i=0 To elementanzahl liste[i] = i+1 Next ;Fuellen For i=0 To 4 ;Fuellt eine Zelle element = Rand(0,elementanzahl) spalte(i) = liste[element] ;Passt die Liste an, dass Elemente nicht mehrmals gewählt werden können If element <> elementanzahl Then liste[element] = liste[elementanzahl] elemtanzahl = elemtanzahl - 1 Next End Function

Kruemelator

Fr, Aug 30, 2013 17:48
Antworten mit Zitat

Stimmt hatte einen Denkfehler, dennoch ist mit Ansatz zum Spalte füllen korrekt. Very Happy

Hier mal als Code.
BlitzBasic: [AUSKLAPPEN]

Dim spalte(4)
SpalteFuellen()

For i=0 To 4
	Print spalte(i)
Next
Print "Beliebige Taste zum beenden."
WaitKey()
End

Function SpalteFuellen()
	Local liste[11]
	Local element;zufaellige stelle in der Liste
	Local elementanzahl = 11;12 unterschiedliche Zahlen (0-11)
	;Liste vorbereiten
	For i=0 To elementanzahl
		liste[i] = i+1
	Next
	;Fuellen
	For i=0 To 4
		;Fuellt eine Zelle
		element = Rand(0,elementanzahl)
		spalte(i) = liste[element]
		;Passt die Liste an, dass Elemente nicht mehrmals gewählt werden können
		If element <> elementanzahl Then liste[element] = liste[elementanzahl]
		elemtanzahl = elemtanzahl - 1
	Next
End Function

	Midimaster	Sa, Aug 31, 2013 7:45 Antworten mit Zitat
@DAK Ich habs nicht so mit Statistik, aber bei mir kommen in einer Spalte 12111098 Möglichkeiten raus. Das sind 95040! Wie kommts Du auf die 792? Die ergäben sich wenn man (12111098) / (12345) rechnen würde. Dies darsft Du nur anwenden, wenn die Reihenfolge der 5 Zahlen unrelevant wäre. Wie z.b. bei den Lottozahlen... So wie ich das Spielfeld verstehe ist dort aber z.B. ein Resultat [1, 12, 6, 7, 2] was anderes als das Resultat [1, 2, 6, 7, 12]. Somit wären es 95040 Lösungen in einer Spalte. Un wenn die jede Spalte x Resulte hat, dann sind doch insgesamt nicht x+x+x+x+x Resultate möglich, sondern xxxxx, oder? Also in unserem Fall ~ 7.7 * 10^24...

Midimaster

Sa, Aug 31, 2013 7:45
Antworten mit Zitat

@DAK

Ich habs nicht so mit Statistik, aber bei mir kommen in einer Spalte

12*11*10*9*8 Möglichkeiten raus. Das sind 95040! Wie kommts Du auf die 792?

Die ergäben sich wenn man (12*11*10*9*8) / (1*2*3*4*5) rechnen würde. Dies darsft Du nur anwenden, wenn die Reihenfolge der 5 Zahlen unrelevant wäre. Wie z.b. bei den Lottozahlen...

So wie ich das Spielfeld verstehe ist dort aber z.B. ein Resultat [1, 12, 6, 7, 2] was anderes als das Resultat [1, 2, 6, 7, 12]. Somit wären es 95040 Lösungen in einer Spalte.

Un wenn die jede Spalte x Resulte hat, dann sind doch insgesamt nicht x+x+x+x+x Resultate möglich, sondern x*x*x*x*x, oder? Also in unserem Fall ~ 7.7 * 10^24...

Zuletzt bearbeitet von Midimaster am Sa, Aug 31, 2013 18:39, insgesamt einmal bearbeitet

	Kruemelator	Sa, Aug 31, 2013 10:16 Antworten mit Zitat
Die Anzahl aller möglichen Kombinationen in dem 5x5 Feld mit Zahlen von 1 bis 12 ist 12^25. 25 weil es 55 Zellen sind und 12 weil es die Zahlen 1-12 sind. Wären all die Zahlen im Zahlensystem mit der Basis 12 und 25 Stellen. Windowsrechner sagt: 953.962.166.440.690.129.601.298.432 oder auch ~ 1 Quadrilliarde. Für eine Spalte wäre es dann entsprechend 12^5, was 248.832 ist. @Midimaster: Ich habe auch so verstanden dass eine unterschiedliche Anordnung extra gezählt wird. 1211109*8 = 95.040 dürfte richtig sein. Es gibt also ~2,62 mal soviele falsche Kombinationen wie es richtige gibt, pro Spalte.

Kruemelator

Sa, Aug 31, 2013 10:16
Antworten mit Zitat

Die Anzahl aller möglichen Kombinationen in dem 5x5 Feld mit Zahlen von 1 bis 12 ist 12^25.
25 weil es 5*5 Zellen sind und 12 weil es die Zahlen 1-12 sind. Wären all die
Zahlen im Zahlensystem mit der Basis 12 und 25 Stellen. Windowsrechner sagt:
953.962.166.440.690.129.601.298.432 oder auch ~ 1 Quadrilliarde.
Für eine Spalte wäre es dann entsprechend 12^5, was 248.832 ist.

@Midimaster:
Ich habe auch so verstanden dass eine unterschiedliche Anordnung extra gezählt wird.
12*11*10*9*8 = 95.040 dürfte richtig sein.

Es gibt also ~2,62 mal soviele falsche Kombinationen wie es richtige gibt, pro Spalte.

	Jamagin	Sa, Aug 31, 2013 19:06 Antworten mit Zitat
Oh, soviele Tipps, danke! Ich werde den Vorschlag von Midimaster vorziehen und die Felderbelegung mit Zufallszahlen belegen. Natürlich kann ich nun auch aufgrund der anderen Tipps, gewisse Feldbelegungen statisch anlegen und verwenden. Es müssen ja nicht 95040 sein.....! Das zu schreiben und selbst auszurechnen wäre viel zu viel Arbeit! Danke! lg. Jamagin
Bevor du etwas neues beginnst, erledige das alte

Jamagin

Sa, Aug 31, 2013 19:06
Antworten mit Zitat

Oh, soviele Tipps, danke!

Ich werde den Vorschlag von Midimaster vorziehen und die Felderbelegung mit Zufallszahlen belegen.
Natürlich kann ich nun auch aufgrund der anderen Tipps, gewisse Feldbelegungen statisch anlegen und verwenden. Es müssen ja nicht 95040 sein.....! Das zu schreiben und selbst auszurechnen wäre viel zu viel Arbeit!

Danke!

lg. Jamagin

Bevor du etwas neues beginnst, erledige das alte

	DAK	Sa, Aug 31, 2013 20:58 Antworten mit Zitat
An deiner Stelle würde ich Kruemelators letzten Code verwenden. Damit hast du ohne viel Aufwand eine deterministische Lösung, die auf jeden Fall immer eine korrekte Lösung liefert. Ist wohl sogar weniger Aufwand als eine Zufallsbelegung zu machen, und die dann zu überprüfen.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Sa, Aug 31, 2013 20:58
Antworten mit Zitat

An deiner Stelle würde ich Kruemelators letzten Code verwenden. Damit hast du ohne viel Aufwand eine deterministische Lösung, die auf jeden Fall immer eine korrekte Lösung liefert. Ist wohl sogar weniger Aufwand als eine Zufallsbelegung zu machen, und die dann zu überprüfen.

Gewinner der 6. und der 68. BlitzCodeCompo

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Formel für max. Möglichkeiten einer Feldbelegung

Betreff: Formel für max. Möglichkeiten einer Feldbelegung