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

Logheaza-te in site pentru a trimite solutii si comentarii