Рекурсивный генератор всех комбинаций строк длиной `Len` с заданным числом «1» на Delphi

Delphi , Синтаксис , Циклы

Рекурсивный генератор всех комбинаций строк длиной Len с заданным числом «1» на Delphi

Вам когда-нибудь приходилось генерировать все возможные комбинации строк длиной Len с заданным числом «1»? Это может показаться сложной задачей, но с помощью рекурсии и правильного подхода можно создать эффективный генератор комбинаций на Delphi.

Представьте, что у вас есть строка длиной Len, и вы хотите заполнить ее «0» и «1», но при этом общее количество «1» должно быть равно N. Как генерировать все комбинации, которые удовлетворяют этим условиям?

Одним из подходов является использование рекурсии. Рекурсия — это когда функция вызывает сама себя в своем теле. В нашем случае, функция рекурсивно вызывается для генерации всех комбинаций.

Давайте рассмотрим пример кода на Delphi:

program CombinationGenerator;

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  System.Generics.Collections;

type
  TCombination = record
    Len: Integer;
    N: Integer;
    OnesLeft: Integer;
    S: string;
  end;

procedure GenerateCombinations(const C: TCombination);
begin
  if C.Len = 0 then
  begin
    Writeln(C.S);
    Exit;
  end;

  if C.Len > C.OnesLeft then
    GenerateCombinations(TCombination.Create(C.Len - 1, C.N, C.OnesLeft, C.S + '0'));

  if C.OnesLeft > 0 then
    GenerateCombinations(TCombination.Create(C.Len - 1, C.N, C.OnesLeft - 1, C.S + '1'));
end;

var
  C: TCombination;
begin
  C := TCombination.Create(5, 2, 2, '');
  GenerateCombinations(C);
  C.Free;
  Readln;
end.

В этом примере мы создаем запись TCombination, которая содержит длину строки Len, общее количество «1» N, количество оставшихся «1» OnesLeft и саму строку S.

Функция GenerateCombinations рекурсивно вызывает сама себя, генерируя все комбинации. Если длина строки равна нулю, мы выводим текущую комбинацию и завершаем рекурсию.

Если длина строки больше, чем оставшееся количество «1», мы рекурсивно вызываем функцию с новой комбинацией, добавляя «0» в конец строки. Если оставшееся количество «1» больше нуля, мы рекурсивно вызываем функцию с новой комбинацией, добавляя «1» в конец строки.

Пример выше генерирует все комбинации строк длиной 5 с двумя «1». Вывод программы будет следующим:

00011
00101
00110
01001
01010
01100
10001
10010
10100
11000

Подтвержденный ответ: Рекурсивный подход является эффективным способом генерации всех комбинаций строк длиной Len с заданным числом «1». Приведенный выше пример кода демонстрирует, как можно реализовать такой генератор на Delphi.

Альтернативный ответ: Существуют и другие подходы к решению этой задачи, например, использование итеративных циклов или генераторов. Однако рекурсивный подход является простым и понятным способом решения этой задачи, и он может быть использован в качестве базового алгоритма для более сложных задач.

Создано по материалам из источника по ссылке.

Рекурсивный генератор всех комбинаций строк длиной `Len` с заданным числом «1» на Delphi.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Циклы ::