Schnellster Weg zum Filtern der A010784-Sequenz
https://stackoverflow.com/questions/5838716
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Die A010784-Sequenz bei OEIS ist die Sequenz, die nur Zahlen mit unterschiedlichen Ziffern enthält. Dies ist eine endliche Menge.
Ich habe versucht, mehrere Zahlen in dieser Reihenfolge mit bestimmten Attributen zu finden.
Zum Beispiel: 6 ist eine eindeutige Zahl der Größe 10. Dies kann wie folgt gefunden werden:
- 6 x 1= 6
- 6 x 2= 12
- 6 x 3= 18
- 6 x 4= 24
- 6 x 5= 30
- 6 x 6= 36
- 6 x 7= 42
- 6 x 8= 48
- 6 x 9= 54
- 6 x 10= 60
- 6 x 11= 66 (Zwei Sechser; dies sind keine unterschiedlichen Ziffern.)
Jetzt versuche ich die höchsten verfügbaren Zahlen für mehrere Größenordnungen.
Angenommen, alle Bestellungen reichen von 1 bis 20.Was ich gerade mache, ist eine Schleife von der höchstmöglichen eindeutigen Zahl, nämlich 9.876.543.210 und der höchsten eindeutigen Zahl der Größe 1, bis zu einer sehr niedrigen Zahl.
Diese Methode fühlt sich extrem ineffizient an. Zumindest für mich.Ich bin mir ziemlich sicher, dass mir einige Dinge über Factoring fehlen, die die Dinge viel schneller machen sollten.
def unique_num(num): # Check whether number is unique. return Boolean def unique_num_magnitude(num): # Check of which magnitude the unique number is return Integer # Dictionary with the current highest values # for each magnitude. values = {1: 987654321...} # Set limits upper_limit = 9876543210 lower_limit = 1 for numbers in range(upper_limit, lower_limit, -1): unique = unique_num(num) # Boolean if (unique): magnitude = unique_num_magnitude(num) if (values[magnitude] < num): values[magnitude] = num
Lösung
Sicher gibt es einen besseren Weg. Sie sollten die Zahlen von unten nach oben aufbauen, dh wenn eine Zahl a1 ... ak (dies sind k Ziffern) nicht die Größe N hat, so dass eine Ziffer innerhalb der ersten k Ziffern des Ergebnisses für einen Multiplikanden 2..N zweimal erscheint auch ist keine Zahl b1 ... bm a1 ... ak. Dies bietet eine kategorisch schnellere rekursive Aufzählungsprozedur, da dadurch eine exponentielle Menge an Suchraum weggeschnitten wird. Details, die OP als Übung überlassen wurden.
Längere Erklärung:
Angenommen, es gibt eine Prozedur
magnitude(number_str)
berechnet die Größe für die in 10-Basis dargestellte Zahl number_str, sodass die Prozedur 0 zurückgibt, wenn number_str mindestens ein doppeltes Vorkommen einer Ziffer enthält, 1, wenn bei number_str jede Ziffer unterschiedlich ist, die Zahl jedoch mit zwei multipliziert wird eine mehrfach vorkommende Ziffer usw.
Diese Prozedur kann in Bezug auf eine andere implementiert werden
unique_digits(number_str)
gibt true zurück, wenn alle Ziffern im number_str eindeutig sind, andernfalls false.
Nun kann magnitude als implementiert werden
magnitude(number_str):
n = str_to_int(number_str)
k = n
i = 0
while (unique_digits(int_to_str(k))):
k = k + n
i = i + 1
return i
Jetzt kann diese magnitude-Prozedur in einen nocarry_magnitude geändert werden, der die Prüfung subtil ändert:
nocarry_magnitude(number_str, limit):
l = length(number_str)
assert (l > 0)
n = str_to_int(number_str)
k = n
i = 0
while (unique_digits(right_substring(int_to_str(k), l))):
k = k + n
i = i + 1
if (i == limit):
break
return i
Diese Prozedur überprüft die mehrfach vorkommenden Ziffern nur in so vielen Ziffern ganz rechts (Ziffern niedrigster Ordnung) des Produkts in der Schleife, wie Ziffern in der ursprünglichen Eingabe vorhanden waren. Ein Grenzwertparameter ist erforderlich, um sicherzustellen, dass die Prozedur beendet wird, da die Prozedur ansonsten möglicherweise in einer Endlosschleife ausgeführt wird. Es ist klar, dass für jeden s einer Zeichenfolge gilt
magnitude(s) <= nocarry_magnitude(s, M) for large M
Nehmen Sie zum Beispiel Nummer 19:
19 * 1 = 19
19 * 2 = 38
19 * 3 = 57
19 * 4 = 76
19 * 5 = 95
19 * 6 = 114 // magnitude("19") = 5
19 * 7 = 133 // nocarry_magnitude("19", 100) = 6
Was ich oben in der Kurzbeschreibung geschrieben habe, ist das wenn
nocarry_magnitude(s, x) == k for x > k
Für jede Zeichenfolge, die durch Nachfixieren von s erhalten wird (bezeichnen Sie dies unten mit x + s), gilt Folgendes:
x : string of digits
magnitude(x + s) <= nocarry_magnitude(x + s, m) <= nocarry_magnitude(s, m)
when m >= magnitude(x + s)
Die erste Ungleichung ergibt sich aus der obigen Behauptung und die zweite ergibt sich aus der Definition des nocarry_magnitude. Es ist zu beachten, dass die Größe (x + s) <= Größe (n) im Allgemeinen kein Satz ist, wie durch veranschaulicht
magnitude( "56") = 1 // 56 * 2 = 112
magnitude("256") = 12 // the first duplicate occurs at 3328
was durch den Übertrag verursacht wird. nocarry_magnitude ignoriert den Übertrag, weshalb das Suffix eines Strings immer so groß ist wie jede Erweiterung (nach links, d. h. Ziffern höherer Ordnung).
Nun können Sie eine wesentlich schnellere rekursive Prozedur schreiben, um nach Zahlen mit einer Größe von mindestens M: zu suchen
search(str):
if (str != ""):
int n = nocarry_magnitude(str, M)
if (n < M):
return # the optimization
int k = magnitude(str)
if (k >= M):
store_answer(str)
for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
'10', '20', '30', '40', '50', '60', '70', '80', '90']:
search(d + str)
search("")
Hier ist eine vollständige Python-Implementierung (Suche nach Magnitude 36):
def unique_digits(s):
r = (len(list(s)) == len(set(s)))
return r
def magnitude(s):
n = int(s)
k = n
assert n > 0
i = 0
while (unique_digits(str(k))):
k = k + n
i = i + 1
return i
def nocarry_magnitude(s, limit):
l = len(s)
assert l > 0
n = int(s)
assert n > 0
k = n
i = 0
while (unique_digits(str(k)[-l:])):
k = k + n
i = i + 1
if (i >= limit):
break
return i
M = 36
def search(s):
if (not(s == "")):
n = nocarry_magnitude(s, M)
if (n < M):
return
k = magnitude(s)
if (k >= M):
print "Answer: %s |" % s,
i = int(s)
k = i
n = 1
while (n <= M):
print k,
k = k + i
n = n + 1
print
for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
'10', '20', '30', '40', '50', '60', '70', '80', '90']:
search(d + s)
search("")
Und hier ist ein Lauf, der weniger als eine Sekunde dauert. Dies findet die Antwort '27', die die eindeutige Zahl zu sein scheint, die die Rekordgröße 36 liefert:
Answer: 27 | 27 54 81 108 135 162 189 216 243 270 297 324 351 378 405
432 459 486 513 540 567 594 621 648 675 702 729 756 783
810 837 864 891 918 945 972
Andere Tipps
Ist das nicht nur ein Permutationsproblem?Für eine bestimmte Größe M machen Sie 10cM.
Wie viele Möglichkeiten gibt es beispielsweise bei Magnitude 2, 2 Ziffern aus 0..9 auszuwählen?(Eigentlich sollte es eine von 1..9 und eine von 0..9 sein, wobei die zweite Ziffer nicht mit der ersten übereinstimmt.)
Sie müssen sie sicherlich nicht alle durchgehen und überprüfen.Richten Sie einfach ein Set ein und wählen Sie eines aus, dann wählen Sie ein anderes.Besser noch, erstellen Sie sie einfach von Grund auf neu.Machen Sie zuerst alles, was mit 1 beginnt (10, 12, 13, 14 usw.), dann alles, was mit 2 usw. beginnt.
Sie haben zwei Probleme:
1) Iterieren über die A010784-Sequenz.
Verwenden Sie itertools.permutations, um aufeinanderfolgende mögliche Zahlen zu generieren.
2) Berechnen der Größe einer Zahl.
Mit diesem Codeausschnitt können Sie feststellen, ob eine Zahl nur eindeutige Ziffern hat:
def unique_num(x):
return len(str(x)) == len(set(str(x))
Sie können einige Zweige schneiden, wenn Sie nur nach den höchsten Zahlen suchen.Aus 6 x 11 = 66 wissen Sie auch, dass die Größe 11 höchstens 5 beträgt. Wenn Sie eine höhere Zahl mit einer Größe>= 5 kennen, können Sie 11 überspringen.
