Стоит задача - создать цепочку, в которой будут содержаться все числа от 0000 до 9999,...

Question

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

Comments

Скажем, у нас изначально записаны 3 цифры. Если предположить, что можно приписывать по одной цифре так, чтобы каждый раз последние четыре образовывали новую последовательность, то получится 10003

---

да да) очевидно так)

---

Пока что нет хороших идей насчет решения.Если, скажем, есть цепочка из 40к символов, в которой все последовательности идут подряд, последовательность abcd гарантированно встретится на позициях 4*abcd .. 4*abcd + 3. Так что при просмотре цепочки встречается последовательность, стоящая не на своей позиции, это гарантированно повтор. Но это работает только для начального состояния цепочки, так что не годится для решения

---

*если при просмотре цепочки

---

Можно попытаться построить идеальную цепочку из 10003 цифр с нуля. Никаких гарантий, что это может сработать

---

хмм, ну очень уважаемый мной человек сказал, что он эту цепочку получил и именно длины 10003.. я думаю, всё же это возможно.  Только как её создать с нуля? Считать кол-во вхождений каждого числа и пока они все не будут равны единице прибавлять цифры и менять их местами? это же дня два прога работать будет..

---

В любом случае попробую! Спасибо огромное0

---

Эм. Нет. Составить массив типа boolean из всех последовательностей. Каждый раз смотреть последние три цифры цепочки и выбирать такую четвертую, чтобы эта последовательность еще не встречалась в массиве

---

Опять же, никаких гарантий, что сработает

---

Так. Кажется, получилось, но я не уверен

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<br>   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.

Comments

Забавно, что это вообще сработало. Как вы поняли, достаточно просматривать возможные варианты i-того символа, начиная с (a[i-1] + 1) mod 10

---

Стоп

---

Забавно. Я думал, что начинаю с a[i-1] + 1, а начинал с единицы. Но главное, что работает. Не знаю, почему

---

ОМГ, сейчас буду разбираться! Спасибо огромное!