Найти наименьшую последовательность, в которой будут все возможные коды - Free Pascal

Формулировка задачи:

Кодовый замок открывается с помощью кода из 4 подряд идущих цифр в системе счисления с основанием 10. найти наименьшую последовательность, в которой будут все возможные коды.

Решение задачи: «Найти наименьшую последовательность, в которой будут все возможные коды»

Листинг программы

program test;
 
const
  MaxCombination = 10000;
type
  TVectorBool = array[0..MaxCombination - 1] of boolean;
  TVectorByte = array[0..MaxCombination - 1] of byte;
 
  procedure GetSequence(var Sequence: TVectorByte);
  var
    UsedComb: TVectorBool;
    CountUsedCombination: integer;
    Depth: integer;
 
    function DFS(Combination: word): boolean;
    var
      Digit: byte;
    begin
      if CountUsedCombination = MaxCombination then
      begin
        DFS := True;
        exit;
      end;
      Inc(Depth);
      DFS := False;
      Combination := (Combination * 10) mod MaxCombination;
      for Digit := 0 to 9 do
      begin
        if not UsedComb[Combination + Digit] then
        begin
          UsedComb[Combination + Digit] := True;
          Inc(CountUsedCombination);
          DFS := DFS(Combination + Digit);
          if DFS then
          begin
            Sequence[Depth - 1] := Digit;
            break;
          end;
          Dec(CountUsedCombination);
          UsedComb[Combination + Digit] := False;
        end;
      end;
      Dec(Depth);
    end;
 
  var
    i: integer;
  begin
    for i := low(UsedComb) to high(UsedComb) do
      UsedComb[i] := False;
    CountUsedCombination := 1;
    Depth := 1;
    UsedComb[0] := True;
    DFS(0);
  end;
 
var
  i: integer;
  Sequence: TVectorByte;
begin
  GetSequence(Sequence);
  Write('000');
  for i := low(Sequence) to high(Sequence) do
    Write(Sequence[i]);
  writeln;
end.

Объяснение кода листинга программы

В этом коде используется алгоритм обхода графа в глубину для поиска всех возможных комбинаций чисел от 0 до 9.

В начале определяется максимальное количество комбинаций, которые могут быть созданы (обозначено как MaxCombination).
Создаются две типы векторов: TVectorBool и TVectorByte. TVectorBool используется для отслеживания использованных комбинаций, а TVectorByte используется для хранения полученных последовательностей.
Определяется процедура GetSequence, которая принимает на вход TVectorByte и возвращает все возможные комбинации чисел от 0 до 9. Внутри этой процедуры определены несколько вспомогательных переменных: UsedComb (использованные комбинации), CountUsedCombination (количество использованных комбинаций), Depth (глубина текущего поддерева).
Внутри процедуры определена функция DFS, которая рекурсивно генерирует все комбинации чисел от 0 до 9. Если все комбинации уже использованы, то функция возвращает True. Иначе, она увеличивает глубину, устанавливает значение текущей комбинации, рекурсивно вызывает DFS для следующей комбинации, и если результат True, то добавляет текущую цифру в последовательность и возвращает False.
В основной части кода создается экземпляр TVectorBool и TVectorByte, инициализированные значениями по умолчанию.
Запускается процедура GetSequence, передавая на вход созданный экземпляр TVectorByte.
После того, как все комбинации сгенерированы, выводится полученная последовательность. Код решает задачу поиска всех возможных комбинаций чисел от 0 до 9, но он не оптимален, так как использует рекурсию и может вызвать переполнение стека при больших значениях MaxCombination.