Math - Finden Sie die Anzahl der Permutationen zwischen zwei Strings

Question

Dies ist keine Hausaufgabe =). Ich mache ein Projekt, das automatisch eine Liste von sequentiellen Computernamen generiert, und ich möchte eine Warnung hinzufügen, wenn die Liste eine verrückte lange Liste sein wird.

Ich weiß, wie man die Anzahl der Permutationen von sagen A-ZZZ, aber ich habe eine Menge Zeit versuchen, eine Einschluss-Ausschluss-Set anwenden. Hier ist das Szenario, um es einfach zu halten, wird der Zeichensatz nur A - Z sein und Groß-/Kleinschreibung wird nicht beachtet, also "A" = "a".

Der Benutzer gibt den Bereich von "ABC" bis "AX" ein. Also muss ich nur zwischen diesen beiden zählen. Also würde die psudo-Logik die volle Gesamtzahl von A - ZZZ bekommen, dann muss ich alles vor "ABC" und alles nach "AX" ausschließen.

Die Frage ist also, wie finde ich die Anzahl vor "ABC" und nach "AX". Ich habe mir all meine alten, diskreten und mathematischen Bücher angeschaut, aber nichts passt wirklich, oder gibt mir die richtige Antwort, wenn ich die Nummern anschließe (n!/N1! * N2! ...). Ich habe sogar versucht, etwas wie das Konvertieren von Binär oder Hex in Dezimal zu machen, aber wie Sie wissen, ist das ein episches Fehlschlagen =).

Danke,

Dave

Answer 1

Die einfachste Lösung ist sowohl Strings als Zahlen in einer Basis-26-Darstellung zu betrachten:

ABC = 26^2 * 0 + 26^1 * 1 + 26^0 * 2 = 28(base 10) 
ACC = 26^2 * 0 + 26^1 * 2 + 26^0 * 2 = 54(base 10) 

ACC - ABC = 54 - 28 = 26 

es ist also insgesamt 27 Saiten im Bereich [ABC, ACC].

Die Grundidee ist ein positional numeral system mit Basis 26 (alle Buchstaben von A - Z).

Es gibt nur ein Problem bei diesem Ansatz:
Es nicht in der Lage ist der Umgang mit leeren Zeichen wie diese nicht der „default“ folgen -Verhalten in dem Sinne, dass sie nur als Präfix erscheinen.

Eine Abhilfe für dieses Problem aus unserer Value-Mapping zu erweitern wäre

A = 0, B = 1, ..., Z = 25 

zu

empty = -1, A = 0, ..., Z = 25 

Während dies die Definition eines Zahlensystem bricht, sind wir nun in der Lage Handhabung auch kürzere Strings:

magnitude([ZZ, AAA]) = AAA - ZZ + 1 = 0 - (-1) + 1 = 2