Python: Notwendige Mindestlänge einer ID bestimmen

Vom einfachen Programm zum fertigen Debian-Paket, Fragen rund um Programmiersprachen, Scripting und Lizenzierung.
Antworten
buhtz
Beiträge: 499
Registriert: 04.12.2015 17:54:49

Python: Notwendige Mindestlänge einer ID bestimmen

Beitrag von buhtz » 07.05.2021 14:52:22

Nein, das ist keine Hausaufgabe. :D Ich suche nur nach einer pythonischen und vor allem performanten Lösung. Nebenbei suche ich auch die passenden mathematischen Fachwörter aus dem Bereich er Kombinatorik. Würde ich die Wörter kennen, fände ich vermutlich im Netz selbst die passende Lösung.

Vorbedingungen
  • Python3
  • Eine ID darf aus den einzelnen Zeichen string.ascii_uppercase + string.digits bestehen. Das sind 36 Zeichen.
  • Ich muss eine vorgegebene Anzahl an eindeutigen IDs erzeugen. Sagen wir `N` Stück.
Frage
  • Wie viele Zeichen, aus dem gegebenen Zeichenvorrat, muss die ID enthalten, um in der Gesamtmenge `N` noch eindeutig sein zu können?
Im Python Umfeld habe ich itertools.permutation und itertools.combination gefunden. So ganz schlau werd ich aber nicht draus.
Beim Weiterlesen, hab ich versucht es zu berechnen.

Ist das ein guter (pythonischer und performanter) Weg, oder würdet ihr es anders machen?

Code: Alles auswählen

#!/usr/bin/env python3
import sys
import string
import math


def unique_combinations(chars, length):
    # solution supported by
    # https://medium.com/i-math/combinations-permutations-fa7ac680f0ac
    return (
        math.factorial(len(chars)) /
        (math.factorial(length) *
         math.factorial((len(chars)-length)))
    )

if __name__ == '__main__':
    # character set for ID
    chars = string.ascii_uppercase + string.digits

    # number of needed uniqe IDs (e.g. cases in a data file)
    N = 100000

    length = 0
    while True:
        length += 1
        combs = unique_combinations(chars, length)
        if combs > N:
            print(f'ID must be {length} chars long.')
            sys.exit()

Benutzeravatar
smutbert
Moderator
Beiträge: 7790
Registriert: 24.07.2011 13:27:39
Wohnort: Graz

Re: Python: Notwendige Mindestlänge einer ID bestimmen

Beitrag von smutbert » 07.05.2021 15:34:24

Das hat jetzt nichts mit python oder nicht zu tun, aber ich würde das etwas direkter angehen.
Sagen wir du brauchst m unterschiedliche IDs, hast n verschiedenen Zeichen zur Verfügung und die Länge der ID soll x sein.
Bei einer einstelligen ID hättest du so klarerweise n unterschiedliche IDs, für eine zweite Stelle hättest du wieder n Möglichkeiten, insgesamt also n² unterschiedliche IDs,...
m = n ^ x

Die Lösung wäre also der Logarithmus zur Basis n von m, aufgerundet auf die nächstgrößere ganze Zahl natürlich, weil es keine 3,2-stellige ID geben kann.

Code: Alles auswählen

#!/usr/bin/env python3

import string
import math

n = len(string.ascii_uppercase) + len(string.digits)
m = 100000

x = round(math.log(m, n) + 0.5)

print("calculated ID length:", x)
print("number of possible IDs:", n ** x)

Antworten