Последние записи

made in programmersforum 6

Интенсив по Python: Работа с API и фреймворками 24-26 ИЮНЯ 2022. Знаете Python, но хотите расширить свои навыки?
Slurm подготовили для вас особенный продукт! Оставить заявку по ссылке - https://slurm.club/3MeqNEk

Online-курс Java с оплатой после трудоустройства. Каждый выпускник получает предложение о работе
И зарплату на 30% выше ожидаемой, подробнее на сайте академии, ссылка - ttps://clck.ru/fCrQw

14th
Апр

Комбинаторика — нахождение всех возможных комбинаций

Posted by Chas under Delphi

Есть 4 числа: 1, 2, 3, 4. Нужно узнать все возможные комбинации из этих 4-х чисел в числе, состоящем из N знаков.

Например если число пятизначное, то чтобы узнать все комбинации, нужно сделать пять вложенных циклов от 1 до 4. А если число знаков в числе неизвестно заранее и оно может изменяться от 1 и до бесконечности (грубо говоря). Как в таком случае вычислить все комбинации?

В результате получается 4 в степени N возможных вариантов, где N — число знаков в числе.

Сtrl
Поиск — великая вещь…

procedure generate(l, r: Integer; var k: longint);

var

  i, v: Integer;

begin

  if (l = r) then

  begin

    for i := 1 to n do

      write(a, ' ');

    writeln;

    k := k + 1;

  end

  else

  begin

    generate(l + 1, r, k); { вызов новой генерации }

    for i := l + 1 to r do

    begin

      v := a[l];

      a[l] := a;

      a := v; { обмен a,a[l] }

      generate(l + 1, r, k); { вызов новой генерации }

    end;

    v := a[l];

    for i := l to r - 1 do

      a := a;

    a[r] := v;

  end;

end;

chandrasecar
Наверняка можно и лучше сделать. Но тоже рабочий вариант. Если заранее неизвестно сколько цифр в наборе и каков их состав:

combi:='';

  MainForm.ListBox1.Clear;

  for i:=1 to n do  //n-максимальная длина, тип Integer

    combi:=combi+s; //s-максимальное число тип Char. переменная combi строкового типа. например если нужно узнать сколько комбинаций в пятизначном числе (переменная n=5) состоящей из чисел от 0 до 3, то s='3';

  for i:=0 to StrToInt(combi) do begin

    a:=0;

    for j:=1 to Length(IntToStr(i)) do begin

      if (StrToInt(IntToStr(i)[j]) in [0..StrToInt(s)]) then a:=a+1;

    end;

    if a=Length(IntToStr(i)) then MainForm.ListBox1.AddItem(IntToStr(i),nil); // в ListBox1 записываем результат

  end;

Минус в том, что чем длиннее комбинация тем дольше считает. Например на пятизначную комбинацию состоящей из чисел от 0 до 3 тратиться время в несколько секунд. Этот код максимально подходит под мои личные задачи.

тема на форуме