Помогите, комбинаторная программа медленно работает, Подскажите, дело в самой задаче или в алгоритме? Опции

[knight]

Задача такая: надо распределить определённый объём по нескольким другим и оценить такие сочетания.
Я сделал так:
=================================================

procedure TForm1.Button2Click(Sender: TObject);
var i:integer;
v:array of byte;//  [0..4]
s,p:integer;
t:cardinal;
begin
i:=0;
p:=30;
setlength(v,3);
for i:=0 to length(v)-1 do
v[i]:=0;
t:=windows.GetTickCount ;
repeat
if v[0]=p then begin showmessage('Приехали'); break;end;
v[length(v)-1]:=v[length(v)-1]+1;
for i:=length(v)-1 downto 1 do
begin
if (v[i]> p-1) then begin V[i-1]:=V[i-1]+1; V[i]:=0; end;
end;
s:=0;
for i:=0 to length(v)-1 do s:=s+v[i];
if s=p then begin
for i:=0 to length(v)-1 do form1.Memo1.Lines.Add(inttostr(v[i])+'  ');
form1.Memo1.Lines.Append('------------------------');
form1.Memo1.Lines.Append(inttostr(s));
form1.Memo1.Lines.Append('==========================');
              end;
until v[0]=p;
t:=windows.GetTickCount -t;
form1.Memo1.Lines.Append(floattostr(t/100)+' c');
end;

================================================
это означает, что имеем некий массив типа байт, и гоним все сочетания, которые могут в нём быть, и в лёт отфильтровываем те сочетания, которые в сумму дают заданное значение.
Требования такие: должна быть довольно высокая точность деления объёма. (в примере это 30 а надо где-то более 100)
Данный пример отфильтровывает нужные сочетания где-то за минуту.
Возможно ли создание гораздо более быстрого алгоритма?
Например такого, который не фильтрует из всех сочетний, а создаёт их сам?
Спасибо за ответы.

Сообщение отредактировано: volvo - 3.11.2006 23:23

[volvo]

Возможно ли создание гораздо более быстрого алгоритма?

У тебя время, в основном, тратится НЕ на вычисления, а на вывод информации. Смотри... Твой первоначальный вариант выдал мне 49 с. Ну, о том, секунды это или нет, можно еще поспорить, не в этом сейчас дело. Будем считать, 49 единиц. Закомментируем 2 строки:

if s=p then begin
  for i:=0 to length(v)-1 do form1.Memo1.Lines.Add(inttostr(v[i])+'  ');
  { form1.Memo1.Lines.Append('------------------------'); }
  form1.Memo1.Lines.Append(inttostr(s));
  { form1.Memo1.Lines.Append('=========================='); }
end;

Результат - меньше 32 единиц... А ведь его можно еще уменьшить... Так что...

[knight]

У тебя время, в основном, тратится НЕ на вычисления, а на вывод информации.

Во. Спасибо! Точно, чё-то я затупил. Да, и там в конце надо делить на 1000, тогда будут секунды.
Да, я это убрал, и результаты:
при длине масива в 3 элемента и точности (p) 100 время 0.07 секунды
А при длине уже в 4 элемента время 8.3 секунды
Если длина 5 - то я по дождал несколько минут а оно только еле-еле до половины допёрло.
Вот.
Ну у меня от времени довольно много зависит. Это только подпрограмма, которая должна сама выполняться какое-то количество раз, и вообще : получится то-ли типа рендеринга долгого и нудного, то-ли прога, считающая в лёт.
Может такая задача как-то кем-то решена, может ссылочку или хотябы её название кто-нить знает?

[volvo]

Вот тут я делал нечто очень подходящее тебе:
Разбиение числа на слагаемые

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

Справишься?

[volvo]

Вот я тут наколдовал что-то. Ты бы рассказал, как надо результаты представлять (точнее, куда передавать), а то неизвестно, что с ними делать (в массив что-ли в динамический закидывать?)... Но вот сама генерация при таком алгоритме происходит практически мгновенно:

uses windows;
var
  p: integer;
  len: integer;

type
  parr = array[0 .. 10] of integer;

{.$define PRINTING}

procedure generate(prev: integer; var arr: parr; level: integer);
var i: integer;
begin
  if level = 0 then begin
    arr[len] := p - prev;
    {$ifdef PRINTING}
    for i := 0 to len do
      write(arr[i]:4);
    writeln;
    {$endif}
  end
  else begin
    for i := 0 to p - prev do begin
      arr[len - level] := i;
      generate(prev+i, arr, level - 1);
    end;
  end;

end;

var
  arr: parr;
  T: dword;
begin
  p := 120;
  len := 5;

  T := gettickcount();
  generate(0, arr, len);
  writeln('p = ', p, ' len = ', succ(len), ' generated: ', gettickcount() - T, ' cycles...');
end.

p = 120 len = 5 generated: 141 cycles...
p = 100 len = 6 generated: 1531 cycles...
p = 120 len = 6 generated: 3688 cycles...
p = 70 len = 7 generated: 3703 cycles...

Меньше чем за 4 секунды генерируются сочетания из 7 чисел, дающих в сумме 70...

[knight]

Вот я тут наколдовал что-то. Ты бы рассказал, как надо результаты представлять (точнее, куда передавать), а то неизвестно, что с ними делать (в массив что-ли в динамический закидывать?)...

Здравствуйте!
Спасибо большое. Да, в принципе можно в массив сочетания закинуть и там уже с ними эксперементировать.
Щас пытаюсь воткнуть код в делфи... Только я не понял как он работает. Всё вроде просто, а чего он делает не поюму.

Сообщение отредактировано: knight - 15.09.2006 11:24