Поиск всех возможных комбинаций

← →
Layner © (2006-05-05 11:58) [0]

Здравствуйте! Помогите найти алгоритм поиска всех возможных комбинаций последовательностей чисел. Т.е. дано, на входе массив чисел. Например 3 строки на 10 столбиков.

Вот пример:
procedure TForm1.Button1Click(Sender: TObject); var a: array of array of integer; i,j: integer; s: string; begin inherited; SetLength(a,3,10); for i:=0 to 2 do for j:=0 to 9 do a[i,j]:=Random(50); s:=""; for i:=0 to 2 do begin for j:=0 to 9 do s:=s+#9+IntToStr(a[i,j]); s:=s+#13#10; end; Showmessage(s); end;

нужно записать все возможные комбинации значения данных, условие 1:
- 10 цифр в строку, одна цифра берется из одного столбика
- если в массиве вестречается число "-1", то это число в обработку не брать.

Поясню... что то с математикой не силен, а надо составить все возможные варианты составления изделия из комплектующих.... То что тут Random, на самом деле это ID товара - состовляющего. Первая строка в массиве - это "родные товары", они всегда есть, то что ниже, это его замены. И если в масиве -1, то это просто нет замен.

Заранее благодарю за любую помощь.

← →
TUser © (2006-05-05 12:06) [1]

Приведи пример входных данных и ожидаемого результата. А то русский есть языка великий сила :)

← →
Layner © (2006-05-05 12:31) [2]

например:
2 3 4 -1 19 -1 -1 28 -1

результат:
2,3,4 2,19,4 2,28,4

Т.е. в данном случае всего 3 результирующих строки. Если бы было все 9 цифр <> -1, то было бы 9 вариантов (3*3)

← →
Layner © (2006-05-05 12:32) [3]

То, что под "результом", это бы и хотел найти. Сам найти не могу :(

← →
TUser © (2006-05-05 12:50) [4]

Создаешь три списка с возможными значениями. Далее - три вложенных цикла.

← →
Layner © (2006-05-05 12:53) [5]

Не совсем понял, размерность массива может быть любой, товаров может быть под 50, и замен у каждого может быть до пяти... т.е. не обязательно 3*3, а может и 50*5...

← →
TUser © (2006-05-05 13:06) [6]

Т.е. число этих списков (и циклов) заранее неизвестно?

type
TListsOfIntegers =
array of
array of integer;

var N: array of integer;
L: TListsOfIntegers;

function Next (var N: array of integer): boolean;
var i: integer;
begin
result := false;
i:=high(N);
while i >= 0 do
if N[i] < high(L[i]) then
inc (N[i])
for i:=i+1 to high(N) do N[i] := 0;
result := true;
Break;
else dec (i)
end;

procedure ...
begin
// создаем L, в каждой строчке - не знаю сколько элементов, не равных -1
...

for i:=0 to length(L)-1 do
if length(L[i]) = 0 then
{нет ни одной комбинации}

// Пишем комбинации
SetLength (N, length(L));
for each i: N[i] := 0;
repeat
{напечатать комбинацию L[N[0],N[1],N[2]...]}
until Next (N);
end;

← →
balepa © (2006-05-05 13:07) [7]

А если:
2 3 4
-1 19 -1
8 28 5

Как должно получиться ?

Так ?
2,3,4
2,19,4
2,19,5
2,28,4
2,28,5
8,3,4
8,19,4
8,19,5
8,28,5

← →
Layner © (2006-05-05 13:08) [8]

TUser, спасибо, сейчас поразбираюсь, вроде что то усек :)

← →
Layner © (2006-05-05 13:10) [9]

balepa © (05.05.06 13:07)
Да, именно так. Может есть тоже вариант решения?

← →
balepa © (2006-05-05 13:26) [10]

> Layner © (05.05.06 13:10) [9]

А вариант TUser неподошел ?
Если честно некода в данный момент думать об этом (работа мешает :)), но вроде сложного ничего нет.
Если сегодня "освобожусь" мож и накидаю чего-нибудь.

рекурсивно - не просто, а очень просто.
procedure TForm1.Button1Click(Sender: TObject); var Rows, Cols: Integer; x, y, Rnd: Integer; A: array of array of Integer; s: string; procedure GetThem(Col: Integer; ss: string); var y: Integer; begin if Col = Cols then Memo2.Lines.Add(ss) else for y := 0 to Rows - 1 do if A[y, Col] > 0 then GetThem(Col + 1, ss + IntToStr(A[y, Col]) + ","); end; begin Randomize; Memo1.Clear; Memo2.Clear; Rows := 2 + Random(4); Cols := 2 + Random(4); SetLength(A, Rows, Cols); for y := 0 to Rows - 1 do begin s := ""; for x := 0 to Cols - 1 do begin Rnd := 1 + Random(50); Rnd := Rnd * Ord(Rnd < 35); A[y, x] := Rnd; s := s + IntToStr(Rnd) + " "; end; Memo1.Lines.Add(s); end; GetThem(0, ""); end;

Огромное спасибо всем ответившим, отрабатываю, напишу, по какому пути пошел.

http://delphimaster.net/view/2-1145813851/

адаптировать не долго

MBo © (05.05.06 13:41)
Спасибо большое за рекурсию, получилось все просто на УРА!!! Только благодаря Вам :)
Всех поздравляю с Днем Победы!

Поиск всех возможных комбинаций Найти похожие ветки