Help! :-) задача на комбинаторику.

[cats_shadow]

Граждане программисты, подскажите алгоритм.. плз.. :-)

Дано:
2 массива байт равной длины. Значения элементов у первого и второго  массивов большей частью своей идентичны. (имеется в виду, что 1й элемент одного равен 1му элементу второго  и т.д.) . Часть элементов имеет различия (например 4й элемент первого не равен 4му элементу второго).

Надо получить множество массивов со всеми возможными комбинациями различающихся элементов.

P.S. Что-то туплю я. Интуитивно все получается, а вот алгоритмизовать...

Comments

проще показать: 2 столбца -- 2 массива

[cats_shadow]

120 120
120 120
27 27
39 39
99 99
99 99
90 90
112 112
98 98
76 76
54 54
32 32
10 10
112 112
12 12
34 34
56 56
78 78
90 90
100 100
1 1
23 23
41 41
23 23
23 45
12 12
34 34
109 109
117 117
121 121
117 247

Re: проще показать: 2 столбца -- 2 массива

[randir-spb.livejournal.com]

Каждый элемент - байт, то есть может быть в 255 состояниях + 1 состояние, совпадающее с состоянием в первом массиве.
То есть тебе надо решить, какие элементы будут отличаться (!) и перебрать варианты.
Или я чего-то не понял?
Какие элементы могут отличаться, пока тоже не ясно, но если их, скажем, не больше трех, то все относительно просто.

Re: проще показать: 2 столбца -- 2 массива

[cats_shadow]

1. каждый элемент массива может быть 2 256 состояниях (потому что байт) :-)
2. построить список отличающихся элементов проблемы не вызывает.

var diff: array of array [0..2] of byte; (список оличий)
a1,a2: array of byte; (обрабатываемые массивы одинаковой длины)
//
for i:=0 to length(a1)-1 do
begin
if (a1[i]<>a2[i]) and (a1[i]<>255) and (a2[i]<>255) //255 -- запрещенное значение, не обрабатывается
then
begin
j:=length(diff);
setlength(diff,j+1);
diff[j][0]:=i;
diff[j][1]:=a1[i];
diff[j][2]:=a2[i];
end;
end;

3. Задача из массива a1, используя список отличий (массив diff) получить набор мсассивов со всеми возможными комбинациями отличий

Re: проще показать: 2 столбца -- 2 массива

[randir-spb.livejournal.com]

Воскресенье...

Я бы предложил каждый элемент diff изобразить записью (i, a1, a2, flag), где flag : Boolean;

Далее, если рассмотреть набор diff[j].flag, как двоичное число длиной length(diff), то получается, что мы должны последовательно прибавлять к этому числу единицу, чтобы перебрать все варианты, от (false, false, ... false) до (true, true, ... true). Соответственно, для каждого варианта можно построить массив по алгоритму:

Берем массив a1, копируем в массив a.
Для всех элементов diff элементу a[diff[j].i] присваиваем diff[j].a1 если diff[j].flag ложно и diff[j].a2, если истинно.

Получаем частично искаженный массив a.

Потом, начиная с конца массива diff, если flag элемента = false, то меняем его на true и завершаем перебор, если же flag элемента = true, то меняем его на false и переходим к следующему. Если следующего элемента не оказалось, то мы перебрали все варианты.

Таким образом мы переберем от (false, false, ... false), когда массив a будет совпадать с a1 до (true, true, ... true), когда a будет совпадать с a2. На каждом шаге будет получаться массив a1, где часть элементов заменена на соответсвующие элементы из a2.

Я правильно понял?

Re: проще показать: 2 столбца -- 2 массива

[cats_shadow]

Хм... идея с двоичным числом забавна. :-) буду ее думать. TNX!!!