Question

Стоит задача - создать цепочку, в которой будут содержаться все числа от 0000 до 9999, причём длина этой цепочки должна быть минимальной. То есть например у нас есть цепочка из 40к символов - 000000010002...9999, нужно переставить цифры местами. По моим подсчётам длина цепочки минимальная равна 10003.
Создал я программку, которая в массив из 40к ячеей закидывает все это. Теперь ,видимо, нужно в цикле смотреть все возможное переборы... но как это реализовать хз... Понятно, что цикл будет while(len(A))>10003:
А что в самом цикле? как уменьшать длину строки? Если есть какие-то идеи, напишите пожалуйста. (Python/Pascal). Важен не сам код, а понимание того, что нужно делать

Answer 1

{
Если что, часть программы не нужна для построения цепочки. Она просто иллюстрирует, что полученный результат верен.
}

var
 sq : array[0..999] of array[0..9] of boolean;
 co : array[0..999] of integer;
 ar : array[1..10003] of 0..9;
  i,j: integer;
 x: integer;
 t : boolean;
 begin
 for i := 0 to 999 do
   begin
   for j := 0 to 9 do
   sq[i][j] := false;
   co[i] := 0;
   end;
 for i := 1 to 3 do
   ar[i] := 0;
 i := 3;
 t := true;
 {write('000');}
 while t do
   begin
   i := i + 1;
   x := ar[i-3]*100 + ar[i-2]*10 + ar[i-1];
   if co[x] >= 10 then t := false
     else
     begin
     j := 1;
     while sq[x][j] do 
       j := (j + 1) mod 10;
     ar[i] := j;
     sq[x][j] := true;
     co[x] := co[x] + 1;
     {write(j)}
     end;
   end;
 {writeln;}
 writeln('Length: ',i - 1);


 {просто чтобы убедиться}
 for i := 0 to 999 do
   for j := 0 to 9 do
   sq[i][j] := false;

  t := true;
 j := 0;
 i := 1;
 while (i <= 10000) and t do
   begin
   x := ar[i] * 100 + ar[i+1] * 10 + ar[i+2];
   if sq[x][ar[i+3]] then t := false
     else
     begin
     sq[x][ar[i+3]] := true;
     j := j + 1;
     end;
   i := i + 1
   end;
 if t and (j = 10000) then
   write('Confirmed')
end.