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

[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 19:23

[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 7:24