Autogrammalgorithmen

Ein Autogramm ist ein Satz, der seine Buchstaben beschreibt. Zum Beispiel von Wikipedia:

  

Dieser Satz verwendet zwei a's, zwei c's, zwei d's, achtundzwanzig e's,   fünf fs, drei g's, acht hs, elf i's, drei ls, zwei m's,   dreizehn n, neun o, zwei p, fünf r, fünfundzwanzig s,   dreiundzwanzig t, sechs v, zehn w, zwei x, fünf y und ein z.

Diese Sätze sind extrem schwierig von Hand zu erstellen, also ist ein Computer für die Aufgabe am besten geeignet, aber wie kann das effizient gemacht werden? Was ist ein effizienter Algorithmus zum Suchen von Autogrammen mit einer gegebenen Anfangszeichenkette? Was ist mit verknüpften Autogrammen, bei denen der vorherige Satz den Inhalt des nächsten beschreibt? Während dieser Thread ist ungefähr das gleiche Thema, es fragt lediglich nach Existenz, und alle dort beschriebenen Algorithmen sind in der Praxis viel zu langsam.

Eine naive Vorgehensweise wäre es, die Mengen möglicher Zahlenkombinationen von beispielsweise 0 bis 40 für eine mögliche Lösung zu durchsuchen. Mit 40 ^ 26 Möglichkeiten würde dies jedoch unglaublich lange dauern.

Wir könnten unsere Suche verbessern, mit dem möglichen Aufwand, eine Lösung zu verpassen, indem wir mit einer ersten Schätzung der Buchstabenkombinationen beginnen und dann nur nach Autogrammen suchen, die von unserer Schätzung abweichen, um jeweils drei. Dies würde immer noch 6 ^ 26 mal dauern. Selbst bei einer Million Schecks pro Sekunde würde dies mehr als 5 Millionen Jahre dauern.

Eine weitere Verfeinerung ergibt sich aus der Erkenntnis, dass a, b, c, d, j, k, m, p, q und z niemals in irgendeinem Zahlenwort vorkommen, so dass diese zehn Buchstaben ihre Zählungen durch die anfängliche Zeichenfolge festgelegt haben . Wir haben jetzt nur 3 Billionen Kombinationen - immer noch nicht großartig.

Es könnte besser sein, mit einer ersten Schätzung zu beginnen und ...

1. Erstellen Sie ein neues "Autogramm", das die Buchstabenanzahl des vorherigen Autogramms beschreibt
2. Überprüfen Sie, ob wir noch ein Autogramm wiederholt haben. Wenn wir haben, und die Schleife ist die Länge 1, sind wir fertig. Ansonsten ändern Sie die Schätzung leicht und gehen Sie zu Schritt 1.

... aber das hat seinen gerechten Anteil an Einschränkungen. Trotz der scheinbaren Fruchtlosigkeit dieser Aufgabe haben andere Menschen Erfolg gehabt. Tatsächlich hat Ссылка sogar eine Kette von fünfundzwanzig verknüpften Autogrammen. Wie?