Rezolvare:
Solutia 1 (Szabo Zoltan):
Pornim de la o permutare si incercam sa adaugam printr-un numar minim de cifre toate permutarile inca neadaugate. Adaugarea unei noi cifre se realizeaza cu scopul de a salva cat mai multe din ultimele cifre generate.
Am notat toate cele 24 de permutari de 4 numere, si fiind atent sa nu repet o permutare de doua ori inutil am ajuns urmatoarele trei solutii de baza, dintre care doar prima are lungime minima de 7+5+5+6+5+5=33.
123412314231243121342132413214321 - solutia buna
1234123142312431214321413241342134 - solutie fara restrictia de lungime minimala
12341231423124312413241342134321432 - solutie fara restrictia de lungime minimala
Numarul solutiilor distincte: putem incepe cu 24 de permutari distincte, fiecare generand cate o solutie diferita de celelalte. Deci numarul solutiilor distincte este 4!=24.
1. 123412314231243121342132413214321
2. 124312413241234121432142314213421
3. 132413214321342131243123412314231
...
24. 432143241324312434213423142341234
Soluţia 2 (Ştefan Gaţachiu):
Cel mai scurt șir, cu lungimea 33, este 123412314231243121342132413214321
care conține permutările în următoarea ordine, de la stânga la dreapta („sărind” acolo unde este cazul peste una sau două poziții):
1234, 2341, 3412, 4123, 2314, 3142, 1423, 4231, 3124, 1243, 2431, 4312, 2134, 1342, 3421, 4213, 1324, 3241, 2413, 4132, 3214, 2143, 1432, 4321.
Soluţia 3 (Ady Nicolae): Va fi postata in curand