0 Daumen
32,2k Aufrufe

Android Locksreen

 Meine Frage ist bezüglich des Android Locksreens: Wieviele Möglichkeiten für verschiedene Muster gibt es?

Bedingungen sind: Man muss mindestens 3 Punkte und höchstens 9 Punkte  miteinander verbinden & zweimal den gleichen Punkt zu wählen ist nicht möglich! 

von
Ich hab ein kurzes Java-Programm geschrieben um die Möglichkeiten auszuzählen.

Dabei komme ich auf 100 877 mögliche Kombinationen.

Es gelten folgende Einschränkungen:
* Kein Punkt kann zweimal ausgewählt werden in einem Linienzug
* Minimale Zuglänge ist 3
* Maximale Zuglänge ist 9
* Linien dürfen sich überkreuzen
* Punkte dürfen nicht übersprungen werden

Beispiel:
P1---P2---P3

P4---P5---P6

P7---P8---P9

Startpunkt P1, nächste erlaubte Punkte:
P2, P4, P5, P6, P8

 

Ich geb aber keine Garantie auf die Richtigkeit des Ergebnisses.

So, ich hab mein Programm nochmal überarbeitet und noch ein paar Fehler entdeckt und behoben. Ich komme insgesamt auf eine Anzahl von 140184 möglichen Kombinationen.
 

Die Zahl stimmt ziemlich sicher. Ich habe zwei Referenzwerte unabhängig vom Programm bestimmt.
Dafür habe ich die Punkte kategorisiert:
* Eckpunkte: P1, P3, P7, P9
* Seitenpunkte: P2, P4, P6, P8
* mittlerer Punkt: P5
(s. vorheriger Kommentar)

Einmal für die Zuglänge 2: Da gibt es insgesamt 56 Möglichkeiten
* von den Eckpunkten aus kann man auf 5 andere Punkte zugreifen, es gibt 4 Eckpunkte -> 20
* von den Seitenpunkten aus kann man auf 7 andere Punkte zugreifen, es gibt 4 Seitenpunkte -> 28
* vom mittleren Punkt aus kann man auf die übrigen 8 Punkte zugreifen -> 8
= in der Summe 56 Möglichkeiten.

Außerdem noch für die Zuglänge 3: Da gibt es 304 Möglichkeiten
* von den 4 Eckpunkten aus hat man jeweils Zugriff auf alle 4 Seitenpunkte, von dort aus hat man wiederum Zugriff auf die 7 anderen Punkte, jedoch mit der Einschränkung, dass der erste Punkt nicht mehr ausgewählt werden kann; damit bleiben 6. Außerdem erreicht man den Mittelpunkt; von diesem aus kann man nun auch wieder alle Punkte bis auf den Ausgangspunkt auswählen, also 7.
In Zahlen ergibt sich somit: 4 * (4 * 6 + 1 * 7) = 124
* von den 4 Seitenpunkten aus kann man die 4 Eckpunkte erreichen; von diesen aus hat man wiederum 4 Möglichkeiten, also die ursprünglichen 5 minus 1 da ja der Ausgangspunkt nicht mehr ausgewählt werden kann. Weiterhin kann man von den Seitenpunkten auch immer 2 andere Seitenpunkte auswählen und von diesen ausgehend wiederum 6. Dann bleibt noch der mittlere Punkt, von diesem aus bleiben noch 7 Möglichkeiten.
In Zahlen: 4 * (4 * 4 + 2 * 6 + 1 * 7) = 140
* vom verbliebenen mittleren Punkt aus kann man die Eckpunkte auswählen und hat von dort aus noch 4 weitere Punkte zur Auswahl. Man kann auch die Seitenpunkte auswählen und hat von dort aus dann noch 6 Wahlmöglichkeiten.
In Zahlen: 1 * (4 * 4 + 4 * 6) = 40
= in der Summe 304 Möglichkeiten

Mit dem Programm konnte ich eben diese Werte bestimmen. Stichproben der Punktauswahl haben mit den geforderten Einschränkungen bei der Punktauswahl übereingestimmt.
Auszug aus einer Liste aller 4er Kombinationen (Kombination 446 - 457 von insgesamt 1400):
...
P3---P8---P7---P4 446
P3---P8---P7---P5 447
P3---P8---P7---P6 448
P3---P8---P9---P2 449
P3---P8---P9---P4 450
P3---P8---P9---P5 451
P3---P8---P9---P6 452
P4---P1---P2---P3 453
P4---P1---P2---P5 454
P4---P1---P2---P6 455
P4---P1---P2---P7 456
P4---P1---P2---P9 457
....

Ich gehe daher davon aus, dass es sich um ein zuverlässiges Ergebnis handelt.
(Sollte jemand einen Fehler entdecken, Interesse an dem Programm haben etc. -> Kommentar)

Ich habe auch ein Programm geschrieben um das auszurechnen und kam auf folgendes Ergebnis: 140184

Hier die Aufschlüsselung auf die einzelnen Zuglängen:

1: 9
2: 56
3: 304
4: 1400
5: 5328
6: 16032
7: 35328
8: 49536
9: 32256

Addiert man nun die Zuglängen 3 bis 9 zusammen, erhält man obiges Ergebnis.

Interessant ist auch, dass es weniger Möglichkeiten für die Zuglänge 9 als für die Zuglänge 8 gibt. Aber das ist leicht zu erklären. Angenommen wir haben jetzt alle möglichen Züge der Länge 8 aufgelistet, dann kann man nur bei einer bestimmten Teilmenge davon auch noch die letzte freie Ziffer erreichen.

Leider habe ich aber, während ich diesen Beitrag geschrieben habe, festgestellt, dass das nicht alles so richtig ist. Man kann man nämlich durchaus eine direkte Linie von der 1 zur 3 ziehen, wenn die 2 schon in einem vorherigen Linienzug benutzt wurde. Im anderen Fall würde eine Bewegung von der 1 zur 3 zusätzlich auch noch die 2 mitgenommen werden. Man kann also keine statische Tabelle verwenden, die eine Ziffer auf die nächst mögliche Ziffer mapt. Man muss das Programm dynamischer angehen, ihm sozusagen einfach nur die Ausnahmeregeln einprogrammieren. Das werde ich dann vielleicht mal machen, wenn mir wieder langweilig wird. ;)

könnten Sie mir vielleicht das Programm zuschicken ?

Kann ich gerne tun. Allerdings wurde es in Purebasic geschrieben und mehr als nur die Basic Syntax verwandt. Aber wenn es hilft, ist der Code im Anhang.

Ich habe mich schließlich vor kurzem hier angemeldet. Daher finde ich den Anhang leider nicht. Es wäre sehr nett, wenn Sie mir den Anhang per E- Mail zuschicken.

*E-Mails nicht erlaubt*

Wo kann ich den Anhang finden?

Offenbar funktioniert das mit den Anhängen hier nicht so, wie das gedacht ist. Ist ja bescheuert. Kann mal jemand die Software reparieren?

Egal, hier ist der Code erneut als Link: https://freakscorner.de/owncloud/index.php/s/P3PAzWSRby6jtoG

2 Antworten

+2 Daumen

Naja, mit Wahrscheinlichkeit hat das noch nichts zu tun. Das ist eher Kombinatorik.

 

Anzahl der Möglichkeiten...

für 3 Punkte: 9*8*7
für 4 Punkte: 9*8*7*6
für 5 Punkte: 9*8*7*6*5
für 6 Punkte: 9*8*7*6*5*4
für 7 Punkte: 9*8*7*6*5*4*3
für 8 Punkte: 9*8*7*6*5*4*3*2
für 9 Punkte: 9*8*7*6*5*4*3*2*1

Man kann auch schreiben (9!) / (6!) usw.  //in Worten neun Fakultät geteilt durch sechs Fakultät

Alles Aufsummieren =  986 328 Möglichkeiten.

 

Kurze Erklärung für den Ansatz:

Zuerst stehen alle 9 Punkte zur Auswahl. Hat man einen Punkt ausgewählt sind es nur noch 8 usw. Die Anzahl der Möglichkeiten erhält man durch Multiplikation.

Wenn nicht bekannt ist aus wie vielen Punkten das Muster besteht, dann muss die Anzahl der Möglichkeiten für alle Muster addiert werden, da man das Muster genau treffen muss und es nicht ausreicht, wenn es teil eines größeren ist.

von 3,7 k
In der Realität müssten das aber weniger Möglichkeiten sein, oder nicht?
Kenn mich mit Kombinatorik mal gar nicht aus, aber wenn ich meinen Punkt oben rechts wähle, so habe ich keine Chance die anderen Eckpunkte als zweiten Punkt zu wählen?
Zumindest gehe ich mal davon aus, dass man Geraden legen muss (hab kein so tolles Handy).

Wenn ich aber nicht einen Eckpunkt nehmen, sondern den mittleren, stehen mir in der Tat 8 Möglichkeiten zu.

etc. etc.

Ist also wohl ein etwas komplizierteres Problem^^.

 

Grüße
Das bezieht sich allerdings nur auf Deine Vorgaben. Ich denke aber mal, dass das Überspringen von Punkten nicht möglich ist, also wenn ich in der linken unteren Ecke anfange, dann kann ich nicht direkt in die linke obere Ecke springen(?). Das reduziert natürlich die Anzahl der Möglichkeiten. Meine Lösung ist also nur ein Richtwert, mehr Möglichkeiten gibt es bei Deinen Vorgaben nicht.
Ja, ist mir auch grad eingefallen. :D Hab selber auch kein solches Telefon. Deshalb mein Kommentar.

Könnte man aber vielleicht mit einem Programm herausfinden ...
0 Daumen

Hi,

Die Frage ist zwar schon länge her, aber jetzt habe ich ein Programm in Java geschrieben, das auch die Verbindungen über bisher gewählte Punkte beachtet.


Modelliert man das Muster folgendermaßen

0 1 2
3 4 5
6 7 8

sind auch Verbindungen wie 1 -> 0 -> 2 korrekt.


Und damit komme ich zu folgender Lösung:

Ein Punkt: 9 Möglichkeiten
2 Punkte: 56 Möglichkeiten
3 Punkte: 320 Möglichkeiten
4 Punkte: 1.624 Möglichkeiten
5 Punkte: 7.152 Möglichkeiten
6 Punkte: 26.016 Möglichkeiten
7 Punkte: 72.912 Möglichkeiten
8 Punkte: 140.704 Möglichkeiten
9 Punkte: 140.704 Möglichkeiten
Insgesamt sind das 389.497 Möglichkeiten.
Also sind das für Muster ab 4 Punkten 389.112 Möglichkeiten.

von

habe auch ein Programm geschrieben

komme auf exakt 3857762 Möglichkeiten.

PS: ihr müsst den Flankenwinkel beachten

Hallo bh, an unserem Institut für Verfahrensanwendung haben wir den Zentralrechner auch mit der Fragestellung rechnen lassen.

DAS ERGEBNIS STIMMT !

Gratulation, Alumi "Simulation"

Habt ihr für den Flankenwinkel 120 oder 130 Grad angenommen??

Ich bin am verzweifeln. ..

Ich habe anhand der Wahrscheinlichkeiten mit 120,5 Grad gerechnet. Auf den ersten Blick mag es logisch erscheinen, 120 Grad zu wählen, jedoch unterschlägt diese Variante 7 Möglichkeiten.

Viel Erfolg bei Ihren weiteren Versuchen,

Dr. Hacke-Schmidt

Flankenwinkel? Was hat das ganze mit Winkeln zu tun? Ich nutze nirgendwo irgendwelche Winkel und komme auf das selbe Ergebnis. Möglicherweise habe ich diese Winkel-Sache aber auch schon in meinen Regeln festgehalten, die in einer einfachen 9x9 Matrix liegen.Die ganze Simulation dauert 4,5 Millisekunden auf einem handelsüblichen Laptop mit 2,7 GHz. Multithreading wird nicht verwandt, weswegen ich die Erwähnung des Zentralcomputers auch nicht verstehe.Aber sei's drum. Ich wollte auch nur noch mal das Ergebnis bestätigen. :)

Hallo,

Ich (9. Klasse) habe das Problem unter anderem zum erklären als HA bekommen.

Ich möchte jetzt nicht falsches der Klasse vortragen und habe desswegen eine Frage: sind es bei 4 Punkten verbinden 1276 (4*1*3*5+4*1*4*6+4*4*3*4+4*4*2*4+4*4*1*6+4*1*4*5+4*1*4*4+4*1*3*6+4*2*2*5+4*2*1*6+4*2*1*6+4*2*1*4+4*2*3*5+4*2*1*6+1*4*4*6+1*4*1*4) Möglichkeiten? Ich habe das im Kopf aufgestellt und bin mir desswegen nicht sicher.

Und falls möglich bitte noch die Zahl der Kombinationsmöglichkeiten von 5,6,7,8 und 9 Punkten schreiben.

Danke für Rückmeldungen. ( Falls ihr 4 Jahre später überhaupt noch wisst, wovon Ich rede)

-Moritz-

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community