Wie hoch ist die Entropie des Dot-Passwort-Systems von Android?

Question

Wie viele Permutationen des androids dot login system möglich sind? Ich bin mir sicher, dass die Lösung dieses Problems in der Diskreten Mathematik liegt, und zwar Permutationen ohne Wiederholung Wenn Ihre Antwort keine Permutationen oder Kombinationen enthält, sind Sie falsch.

Die Länge von Passwörtern liegt zwischen 4 und 9 Punkten, insgesamt gibt es aber 9 Punkte zu permutieren, so dass meine ursprüngliche Gleichung lautet:

9P4+9P5+9P6+9P7+9P8+9P9

Ich weiß jedoch, dass diese Gleichung unvollständig ist, weil sie nicht alle Regeln berücksichtigt. Jeder Punkt unterscheidet sich durch seine Position. Wenn man also jedem Punkt eine Zahl zuordnet, sieht das wie folgt aus:

123
456
789

Das Passwort "1397" ist nicht möglich. Wenn Sie versuchen, dieses Passwort zu verwenden, haben Sie in Wirklichkeit "1236987" eingegeben, da die Zahlen dazwischen automatisch ausgewählt werden. Es muss eine weitere Gleichung erstellt werden, um diese Einschränkungen zu berücksichtigen, und dann von meiner obigen nPr-Gleichung abgezogen werden.

Ce site Link hat ein großartiges Video, in dem jemand den Android-Login benutzt. Es geht auch mehr ins Detail in die Regeln. Die Mathematik auf dieser Seite ist völlig falsch, er ist nicht einmal in der Nähe einer echten Lösung.

Answer 1

bearbeiten : Nein, ich habe mich geirrt. Der Graph ändert sich, denn während im Allgemeinen Dinge wie 1 -> 3 nicht erlaubt sind (man müsste zuerst durch 2 gehen), kann man kann Dinge tun wie 2 -> 5 -> 1 -> 3: Die Kante 1 -> 3 wird verfügbar, da die 2 bereits im Pfad verwendet wurde.

Ich habe ein Programm geschrieben, um das zu berücksichtigen, und erhielt dieselben 389,112 wie Omnifarious (und dann wurde mir klar, dass mein Programm dasselbe tat wie seines).

Das hat mich neugierig gemacht: Ich bin ziemlich sicher, dass es 139.880 sind. Wie Jim sagte, kann dies durch einen Graphen modelliert werden. Die Potenzierung einer Adjazenzmatrix funktioniert nicht, weil sie Pfade mit Wiederholungen zählt, aber man kann den Graphen einfach per BFS durchgehen:

~~nodes = range(1, 10)

edges = {
    1: [2, 6, 5, 8, 4],
    2: [1, 4, 7, 5, 9, 6, 3],
    3: [2, 4, 5, 8, 6],
    4: [1, 2, 3, 5, 9, 8, 7],
    5: [1, 2, 3, 4, 6, 7, 8, 9],
    6: [3, 2, 1, 5, 7, 8, 9],
    7: [4, 2, 5, 6, 8],
    8: [7, 4, 1, 5, 3, 6, 9],
    9: [8, 4, 5, 2, 6],
}

def num_paths(length):
    q = deque([node] for node in nodes)
    paths = []
    while q:
        path = q.popleft()
        if len(path) == length:
            paths.append(path)
            continue
        for node in edges[path[-1]]:
            if node not in path:
                q.append(path + [node])
    return len(paths)

Und dann addiere einfach die Anzahl der Wege der Längen 4, 5, 6, 7, 8 und 9.

>>> sum(num_paths(i) for i in range(4, 10))
139880~~