Генерация всех возможных комбинаций слов

Delphi , Синтаксис , Синтаксис

В данной статье мы рассмотрим задачу генерации всех возможных комбинаций слов из заданного набора. Для этого мы предложим два решения на языке Object Pascal (Delphi).

Решение 1: Рекурсивная функция

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

procedure TForm1.generarCombinaciones(const elementos: TStringList;
  const combinacion: string; inicio: Integer);
var
  i: Integer;
begin
  if combinacion <> '' then
    ShowMessage(combinacion);

  for i := inicio to elementos.Count-1 do
    GenerarCombinaciones(elementos, combinacion + elementos.Strings[i] + ' ', i + 1);
end;

procedure TForm1.Button2Click(Sender: TObject);
var
   sl : TStringList;
begin
   sl := TStringList.Create;
   sl.Add('Mark');
   sl.Add('Anna');
   sl.Add('John');
   sl.Add('Martha');

   generarCombinaciones(sl,'',0);

   sl.free;
end;

Эта функция generarCombinaciones принимает в качестве параметров список слов, текущую комбинацию и индекс начала генерации. Если текущая комбинация не пустая, она выводится на экран. Затем функция рекурсивно вызывается для каждого слова в списке начиная с заданного индекса.

Решение 2: Рекурсивный подход с использованием битовых массивов

Второе решение основано на рекурсивном подходе, который использует битовые массивы для отслеживания использованных слов. Ниже приведен пример такой реализации:

program Project_delphi_stackoverflow;

{$APPTYPE CONSOLE}
{$R *.res}

uses
  System.SysUtils, Types, Classes;

procedure GeneratePermutations(input_list: TStringList; output_list: TStringList; current_combination: TStringList; used: TBits);
var
  i: Integer;
  combination: string;
begin
  if current_combination.Count > 0 then
  begin
    combination := Trim(current_combination.DelimitedText);
    output_list.Add(combination);
  end;

  for i := 0 to input_list.Count - 1 do
  begin
    if not used[i] then
    begin
      used[i] := True;
      current_combination.Add(input_list[i]);
      GeneratePermutations(input_list, output_list, current_combination, used);
      current_combination.Delete(current_combination.Count - 1);
      used[i] := False;
    end;
  end;
end;

procedure OutputCombinations(output_list: TStringList);
var
  combination: string;
begin
  WriteLn('----------------------------------------------------------');
  WriteLn(Format('Number of combinations: %d', [output_list.Count]));
  WriteLn('----------------------------------------------------------');
  for combination in output_list do
    WriteLn(combination);
  WriteLn;
end;

var
  input_list, output_list, current_combination: TStringList;
  used: TBits;

begin
  input_list := TStringList.Create;
  output_list := TStringList.Create;
  current_combination := TStringList.Create;
  used := TBits.Create;
  try
    // Your test data N=4
    input_list.Add('Mark');
    input_list.Add('Anna');
    input_list.Add('John');
    input_list.Add('Martha');
    used.Size := input_list.Count;

    GeneratePermutations(input_list, output_list, current_combination, used);
    OutputCombinations(output_list);

    // Your test data N=5
    input_list.Add('Joe');
    output_list.Clear;
    used.Size := input_list.Count;

    GeneratePermutations(input_list, output_list, current_combination, used);
    OutputCombinations(output_list);

    // Your test data N=6
    input_list.Add('Alice');
    output_list.Clear;
    used.Size := input_list.Count;

    GeneratePermutations(input_list, output_list, current_combination, used);
    OutputCombinations(output_list);


    // Your test data N=4
     input_list.Clear;
    input_list.Add('Mark');
    input_list.Add('Anna');
    input_list.Add('Mark');
    input_list.Add('Martha');
    used.Size := input_list.Count;

    GeneratePermutations(input_list, output_list, current_combination, used);
    OutputCombinations(output_list);

  finally
    input_list.Free;
    output_list.Free;
    current_combination.Free;
    used.Free;
  end;

  ReadLn;
end.

Функция GeneratePermutations принимает в качестве параметров список слов, список результатов, текущую комбинацию и битовый массив для отслеживания использованных слов. Если текущая комбинация не пустая, она добавляется в список результатов. Затем функция рекурсивно вызывается для каждого слова в списке, которое еще не было использовано.

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

Данная статья рассматривает задачу генерации всех возможных комбинаций слов из заданного набора с помощью двух решений на языке Object Pascal (Delphi).

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

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

:: Главная :: Синтаксис ::