Frühestes Datum mit den Ziffern 0-9 nur einmal im Format DD/MM HH:MM:SS suchen

Question

Benötigt wird ein Algorithmus zur Ermittlung des frühesten Datums unter Verwendung der Ziffern 0-9 nur einmal im Format TT/MM HH:MM:SS. Die tatsächliche Antwort würde lauten: 26/03 17:48:59

Answer 1

Am einfachsten ist es, alle Permutationen von [0...9] zu erzeugen und zu prüfen, ob sie ein gültiges Datum sind.

10 ! = 3 628 800

Wenn Sie die Effizienz verbessern wollen, wäre ein Backtracking hilfreich. In diesem Fall handelt es sich nur um ein einfaches Problem der Erfüllung einer Bedingung, die Anzahl der gültigen Daten ist viel geringer als die Anzahl der Permutationen. Außerdem können Sie sie in der Reihenfolge des niedrigsten Monats, dann des niedrigsten Tages usw. betrachten.

Zum Beispiel

01 funktioniert nicht, weil die erste Ziffer der Zeit (10s Stunden) 0 oder 1 sein muss. 02 funktioniert nicht, weil die erste Ziffer der Uhrzeit jetzt 1 sein muss und das Datum im Februar nur 0,1,2 sein kann.

Und so weiter.

FWIW - Es gibt nur 769 gültige Daten

import datetime
import itertools

count = 1
for perm in itertools.permutations( range(10) ):

    i = 0;
    day = perm[i]+perm[i+1]*10
    i+=2
    month = perm[i]+perm[i+1]*10
    i+=2
    hour =  perm[i]+perm[i+1]*10
    i+=2
    minute =  perm[i]+perm[i+1]*10
    i+=2
    second =  perm[i]+perm[i+1]*10
    try:
        print datetime.datetime( 2012, month, day, hour, minute, second)
        count+=1
    except:
        pass

print count

Answer 2

Dies ist eine Problem der Erfüllung von Nebenbedingungen . Vielleicht möchten Sie zunächst mit dem Datumsformat MM/TT HH:MM:SS arbeiten und Ihre Antwort später umrechnen. In diesem Format ist die lexikografisch kleinste gültige Datumsfolge die gesuchte Antwort. Wenn Sie also systematisch suchen, wäre das erste gültige Datum, das Sie finden, die Lösung.

Im Grunde genommen hat Ihr Suchraum 12 x 31 x 24 x 60 x 60 meist gültige Daten. Ihre Beschränkungen umfassen also:

month < 13
day   < 32
hour  < 24
minutes < 60
seconds < 60
occurrence(date, i) == 1 for each i = 0 to 9

Sie könnten dann eine Backtracking-Suchalgorithmus um systematisch durch den Suchraum zu gehen.