Hallo,
ich würde gern wissen wieviel Kombinationsmöglichkeiten es bei einen Pattern-Lockscreen von Smartphones gibt? Ich bin jedoch an der Berechnung gescheitert. Solch ein Pattern-Lockscreen besteht aus 9 Segmenten die man mit dem Finger verbindet. Jedes Segment kann nur einmal besetzt werden.
Wieviel Kombinationsmöglichkeiten gibt es?
Tut mir leid, aber ich kann dir leider nicht weiterhelfen!
Gruß letzter.richter
Hallo,
auch ich kann dir da nur indirekt weiterhelfen. Prinzipiell fehlen mir noch ein paar Infos. Die Anzahl der Möglichkeiten hängt wie du bestimmt selbst bereits weißt vom Startpunkt ab und wie ich mich danach verhalte. Also ist zunächst zu fragen, wie lang das PW werden soll bzw.wo der Startpunkt liegt. (vereinfachte Rechenweise).
Wenn du generell alle Möglichkeiten haben willst, sollte dir die Graphentheorie weiterhelfen. Auch ich müsste mich da erst wieder einlesen, aber es gibt Algorithmen die die günstigsten Wege bzw. alle Wege oder zumindest deren Anzahl zurück liefern. Das war gar nicht sooo schwer. Mit diesem Tipp solltest du etwas finden können.
Dijkstra-und Hamilton- Algorithmus sind zwar beide nicht die Richtigen Algos, hilft aber vielleicht bei der Suche.
Vielen lieben Dank. ich werde mich danach mal erkundigen. wenn ich etwas neues herrausgefunden habe, werde ich es hier veröffentlichen.
bestimmt hast Du schon Antworten!? (Seh leider hier den Fragebaum nicht, nur die Frage und meine Antwort):
Heuristik: n = Anzahl der Felder die man als Pattern benutzt. m = m(n) Anzahl der unterschiedlichen(!) Kombinationen M(n)=„Menge der Kombinationen als n-Tupel“
n=1 => m(1)=9
n=2 => m(2)=?
M(2)={(1,2);(1,4);(1,5);(2,1);(2,3);(2,5);(3…);(4…);(6…);(7…);(8…);(9…) UND
(5;1};(5;2);(5;3);(5;4);(5;6);(5;7);(5;8);(5;9)}
m(2)=8x3+1x8=8x4=32
n=3…
bis
n=9 M(9)={(1236 54789);
(1236 98 547);(1236 98 745);(1236 98 547); …
(123654789);();();();();();()}
Mit vollständiger Induktion oder Mustererkennung
Und/oder Kombinatorik-Model „9 Kugeln aus 9 ohne zurücklegen“ + Einschränkungen: N=9! (minus/geteilt etc)
(Frage: darf man „kreuzen“? z.B. 6->8 in (123596 847)
"wie Diagonal darf man ziehen: ist z.B (186) erlaubt?
N
hab mir mal so ein Lockscreen App mit „Leih-Handy“ geholt: offenbar is alles möglich von 1-9 außer „überspringen“:
offenbar is alles möglich von 1-9 außer „überspringen“:
also kein 1->3 „ohne 2“ … (aber die sind abzählbar [NICHT unendlich oder Überabzählbar endlich]):
also bis bald (kurz Frühstücken …):
n=1: N1=9
n=2: N2_all=9x8=9!/7!=72 =>N2=72-16=56
usw.
…
CU
Ich vermute die Lösung ist ganz simpel:
Theoretisch muss man nur die verbleibenden Möglichkeiten addieren.
Also
9*8*7*6*5*4*3*2*1=362880 Möglichkeiten
Also 9(Man kann mit einem von neun Feldern anfangen)
8(Es bleiben noch 8 Felder übrig von denen man 1 wählt zum verbinden)
und so weiter
mfg
#1# „addieren“??? => 9!=9*8*7…*1 ???
#2# was wenn ich z.B. mit der Taste „3“ anfange (EINE Taste von 9) und dann zur „7“ (2te von 8 verbliebenen!) „SPRINGEN“ will?
Geht nicht: siehe Beitrag davor!
(Aber wenn ich schon nicht schlafen kann, dann probier ich es mal. Denn bei einer Bemerkung hast Du Recht: schwer ist es glaub ich dann wirklich nicht mehr!???)
Tippe auf 9+(9*8-16)+[(9*8-x)*7-y]+…+9!-z=?
mit x=16,y,z=??? (kann doch ganz schön schwer werden, wenn’s „auf den Punkt“ genau werden soll!?
(Dann doch evtl. Benni fragen mit seinem Wissen über Dijkstra, Hamilton und Graphentheorie und hoffentlich auch genügend grundlegender Wahrscheinlichkeitsrechnung!-)
„Größenordnungsmäßig“ evtl. doch genau Deine 9!
Oh Gott ist mein TeX eingestaubt:
\sum_{k=1}^9 \frac{9!}{(9-k)!} - 16\pi
n=3: (9*8-x)*7-y mit x=16 (s. „n=2“: z.B. (19) o. (28))
UND y=224 + 56 + 45 =328 (SPRunGfehler:=„sprg“)
^^ „er“ „re“ „mx“
„er“=EckeRand-SPRunGfehler sind z.B. (128) o. (164)…
„re“=… zB.(219)
„Mx“=„Me u Mr“=„Mitte-Eck_o_Rand-Sprg“-Fehler (M=5!):
zB. Me: (513) VORSICHT: (519) „KEIN Sprg-Fehler“
Bitte nachprüfen und weitermachen bis n=9 (komm heut nicht mehr dazu)!
PS: bin mir sicher, dass man, wenn man sich gut anstellt, für n=4,5,… den „Schwierigkeitsgrad“ gleich weit unten halten kann (x=16, y=328, …
PS2: oder ohnehin viel einfacher
Viel Spaß
@Evil Verbesserung von meinem
„SprungFehler“ y=328 falsch! (Sondern: N3=328!)
richtig y=64 =>N3=(9*8-x)*7-y=328
Ecke->Rand->dannSprungfehler „ERx“=16; z.B. (128)
bzw. „REx“=32 „RRx“=8 und alles „mit Mitte“: „xMx“=8*1*0=0 (gut nachvollziehbares Rechenbeispiel!?)
(da von M=5 aus KEINE Sprungfehler passieren können!)
"MEx"1*4*2=8 und "MRx"1*4*0=0: z.B. (528) KEIN Fehler!
n=4: …=> N4=1664 =[(9*8-x)*7-y]*6-z (mit z=304)
Klassifikation der Fehlerklassen für n=5 bis 9:
(leider hab ich nach x,y,z KEINE Idee mehr. Also Evil selber machen #Grins:wink:#
Die Anzahl der Fehler wird weniger also leichter
z.B. 1234x: einziger Fehler (1234->6)
ABER Die Klassifikation an sich schwerer (Isomorphien:
(1234x)~=(3698x) UND
Große Mächtigkeit der Zugrundeliegenden (n=4)-Klassen
und mir v.a. IN MEINEM GRENZENLOSEN CHAOS zu kompliziert (SELBER MACHEN)!
Hallo,
die Lösung weiß ich leider nicht, aber:
einige Anregungen, Notizen:
Das Problem besteht ja darin, dass du:
Die einzige Lösung die mir jetzt einfällt, wäre ausprobieren, aber ich habe leider nur 6 Wochen Sommerferien und auch nur (grob geschätzt) 75 Jahre zu leben, also hoffe ich mal auf bessere Antworten, ich hoffe ´, ich konnte anderen Betrachtern helfen.
Guten Tag,
Ich würde gern wissen wieviel Kombinationsmöglichkeiten es bei
einen Pattern-Lockscreen von Smartphones gibt?
Solch ein Pattern-Lockscreen besteht aus 9 Segmenten,
die man mit dem Finger verbindet.
Jedes Segment kann nur einmal besetzt werden.
Ich sach ma die Einschränkungen sind unvollständig. Oder anders formuliert: Wenn die einzige Forderung ist, dass jeder Punkt nur einmal besetzt werden darf, dann ist die Berechnung einfach. Sei n die Anzahl der Punkte, dann ergibt sich die Anzahl der Möglichkeiten zu n! = n*(n-1)*(n-2)* … * 2 * 1.
Soweit ich weiß ist aber nicht jede Kombination möglich; z.B. das Überspringen von Punkten ist wahrscheinlich nicht erlaubt.
Bei folgender Anordnung soll nun gelten:
(P1)-(P2)-(P3)
(P4)-(P5)-(P6)
(P7)-(P8)-(P9)
* Punkte, die auf einer direkten Verbindung zwischen zwei Punkten liegen, dürfen nicht übersprungen werden.
(Bsp.: Der Zug von (P7) nach (P1) ist nicht erlaubt, da sonst (P4) übersprungen wird; ebenso: (P7) nach (P3) ist nicht erlaubt; dagegen: (P7) nach (P2) ist erlaubt.)
* Linien dürfen sich kreuzen.
(Bsp.: Der Zug (P4)-(P2)-(P5)-(P1) ist erlaubt.)
* Jeder Punkt darf nur einmal ausgewählt werden. Auch bereits ausgewählte Punkte dürfen nicht übersprungen werden.
(Bsp.: (P1)-(P2)-(P1) ist nicht erlaubt.)
Mit diesen Regeln ergeben sich dann für die Zuglänge z p Kombinationen:
z=1 --> p= 9
z=2 --> p= 56
z=3 --> p= 304
Bis hierher ist das mit relativ wenig Aufwand von Hand zu berechnen. Für die Ergebnisse danach schreibt man besser ein Programm und lässt den Rechner das auszählen.
(Keine Garantie für die Richtigkeit!)
z=4 --> p= 1400
z=5 --> p= 5328
z=6 --> p=16032
z=7 --> p=35328
z=8 --> p=49536
z=9 --> p=32256
(Keine Garantie für die Richtigkeit!)
Die Kombinationsmöglichkeiten kann man nun nach Bedarf addieren. Wenn z.B. eine Mindestzuglänge von 4 und die Höchstzuglänge von 8 vorgegeben ist, dann addiert man die p für z von 4 bis 8.
Noch eine Anmerkung zu dem etwas paradox erscheinenden Ergebnis von p für z=9: Zuerst ist man versucht (zumindest ging es mir so) zu glauben, das könne nicht stimmen, man hat ja einen Punkt mehr zur Auswahl als bei z=8. Allerdings verbietet die Forderung, dass kein Punkt übersprungen werden darf, Zugfolgen, die bei z=8 noch möglich sind. Der vorletzte Zug muss jetzt nämlich so enden, dass noch der 9. Punkt erreicht werden kann (ohne zu springen). Zudem hat man bei z=9, wenn man die Einschränkungen beiseite lässt, genauso viele Kombinationsmöglichkeiten wie bei z=8 (der Punkt der bei z=8 übrig bleibt, wird bei z=9 nur einfach mit ausgewählt). Damit sieht dieses Ergebnis plausibel aus.
Bei anderen Regeln ändert sich natürlich auch das Ergebnis.