Motto: Cel mai mare număr posibil este acela din care oricât ai scădea, tot nu se cunoaşte. (Traian Furnea)
B. Superpermutări minimale
Fiind date n caractere, găsiţi cel mai scurt şir care conţine toate cele n! permutări ale acestor caractere, ca subşiruri contigue (the shortest superstring problem).
De exemplu,
- pentru n=1, soluţia este secvenţa 1 (de lungime 1);
- pentru n=2, soluţia este 121 (de lungime 3);
- pentru n=3, soluţia este 123121321 (de lungime 9).
Găsiţi soluţia problemei pentru cazul n=4.
Notă: Există o conjectură care dă lungimea celei mai scurte secvenţe de acest tip; pentru n caractere, ea este 1! + 2! + ... + n!.
Pentru a salva problema in format docx apasati aici