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

[cats_shadow]

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

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

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

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

Comments

[randir-spb.livejournal.com]

Уточни, что значит "большей частью".
Как именно отличаются элементы? Два элемента меняются местами или, скажем, третий элемент первого массива равен 0.5, а третий элемент второго - 0.51, а остальные элементы нули?

проще показать: 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!!!

[slobin.livejournal.com]

a1 = [3, 14, 15, 92, 6, 7, 8]
a2 = [3, 14, 16, 92, 6, 8, 8]

def allofthem(prefix, a1, a2):
    assert len(a1) == len(a2)
    for i in range(len(a1)):
        if a1[i] != a2[i]:
            prefix1 = prefix + a1[0:i+1]
            prefix2 = prefix + a2[0:i+1]
            set1 = allofthem(prefix1, a1[i+1:], a2[i+1:])
            set2 = allofthem(prefix2, a1[i+1:], a2[i+1:])
            return set1 + set2
    return [prefix + a1]

print allofthem([], a1, a2)

... У меня есть мысль, и я её думаю ...

[cats_shadow]

Кир, переведи, плз...

[slobin.livejournal.com]

На какой? И, честно говоря, я всегда думал, что тексты на питоне максимально наглядны, и не прочитать их практически невозможно. Не я сказал, что "питон -- это исполняемый псевдокод".

... Вот и окончился сказочный вечер ...

[cats_shadow]

давай на паскаль :-)
не знаю я питона :-)

[slobin.livejournal.com]

На язык без автоматического распределения памяти??? Я уж не помню, когда в последний раз на таком писал! Без операций "вырезать подмассив" и "склеить два массива" это долго, нудно и скучно. Ты бы ещё ассемблер предложил. ;-) Ну хорошо: какого типа, по-твоему, должен быть результат? (...) Впрочем, если исходные два массива лезут в паскалевский string и если тебе достаточно вывести результат на печать, то ладно, уболтал, сейчас напишу.

... Не сломаешь - не починишь ...

[cats_shadow]

Мне нужен набор (массив из) массивов, элементы которого я дальше буду скармливать (при совпадении опредеоленных условий) другим функциям, как параметр.

Ты проще -- алгоритм напиши. :-)

[slobin.livejournal.com]

Если верить содержимому каталога d:\store\mysrc, на паскале я в последний раз писал в 99 году. Так что извиняйте, если что не так. ;-)

function head(s: string; i: integer): string;
begin
  head := copy(s, 1, i);
end;

function tail(s: string; i: integer): string;
begin
  tail := copy(s, i+1, length(s)-i);
end;

procedure allofthem(prefix, a1, a2: string);
  var i: integer;
      prefix1, prefix2: string;
begin
  (* length(a1) = length(a2) *)
  for i := 1 to length(a1) do
  begin
    if a1[i] <> a2[i] then
    begin
      prefix1 := prefix + head(a1, i);
      prefix2 := prefix + head(a2, i);
      allofthem(prefix1, tail(a1, i), tail(a2, i));
      allofthem(prefix2, tail(a1, i), tail(a2, i));
      exit;
    end;
  end;
  writeln(prefix + a1);
end;

begin
  allofthem('', 'abcdefg', 'abCdeFg');
end.

... Кошкам так нравится нравиться ...

[awind.livejournal.com]

хе-хе. на питоне таки значительно понятней. да и на перле бы понятней было, несмотря на славу write only.

[cats_shadow]

это уж кто какой язык пользует, тому на том и понятно... а я вообще алгоритм спрашивал, а не код. :-Р

[awind.livejournal.com]

а алгоритм тебе на чём описывать? на псевдокоде проще всего, а ничего настолько питоно-специфичного чтобы оно мешало пониманию там нет. а то что его можно скормить интертрепатору и проверить только плюс.

[cats_shadow]

гм. на русском (или английском) литературном. Как в школе на информатике. :-), или блок-схему нарисовать. А для понимания псевдокода еще и его синтаксис знать надо.

[checat.livejournal.com]

Пройти по массиву, подсчитать количество различающихся байт N, всего байт M.
Создать 2^N массивов.
В нулевом все элементы из первого исходного.
В первом все элементы из первого исходного, кроме первого отличающегося, который из второго исходного.
Во втором все элементы из первого исходного, кроме второго отличающегося, который из второго исходного.
В третьем все элементы из первого исходного, кроме первого и второго отличающихся, которые из второго исходного.
...

[cats_shadow]

ышшо раз -- алгоритм нужен... ты пишешь примерно то же, что Рандир про представление в виде двоичного числа написал...

[checat.livejournal.com]

то, что тут применимы оказались двойчные числа - случайность, позволяющая оптимизировать. написан как раз алгоритм. взять а, сделать с ним б. ты напиши, что непонятно в этой последовательности действий.

[cats_shadow]

"В нулевом все элементы из первого исходного."
понятно
"В первом все элементы из первого исходного, кроме первого отличающегося, который из второго исходного."
теоретически понятно
"Во втором все элементы из первого исходного, кроме второго отличающегося, который из второго исходного."
тоже понять можно
"В третьем все элементы из первого исходного, кроме первого и второго отличающихся, которые из второго исходного."
вероятно...

А как цикл построить??? Или количество отличающихся элементов-то от случая к случаю не фиксировано. :-)

[checat.livejournal.com]

Эх, ты... Я думал, многоточие расшифруешь сам...

Более общий вариант (если исходных массивов больше двух):
Пройти по массиву, подсчитать количество различающихся байт N.
Создать массив размера N для индексов отличающихся байт.
Создать массив размера N для счётчиков.
Создать массив размера N для максимальных значений счётчиков.
Заполнить индексы.
Занести в каждый счётчик 0 (указание брать значение отличающегося байта с соответствующим индексом из первого исходного массива).
Занести в каждое максимальное значение счётчика число вариантов значений для байта с данным индексом.

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

Если отличающиеся байты встречаются достаточно часто, можно отказаться от массива индексов, просто для неразличающихся байтов максимум соответствующего счётчика равен 1.

В оптимизированном варианте предел для всех счётчиков - 2, роль "массива счётчиков" совмещена с номером заполняемого выходного массива i, его биты являются счётчиками со значениями 0 и 1, и переполнение битов автоматически переносится на следующий бит. Оптимизированный вариант для 2-х массивов и двоичной системы:


Пройти по массиву, подсчитать количество различающихся байт N.
Создать массив размера N для индексов отличающихся байт, заполнить его.
Создать 2^N массивов.
Для каждого массива (i от 0 до 2^N-1)
скопировать все данные из первого массива,
кроме тех отличающихся байтов [0...N-1],
чьему порядковому номеру
в числе i соответствует единица в соответствующей битовой позиции,
а эти байты взять из второго массива.

Если различающихся байт достаточно много, то при реализации для индекса i придётся использовать специальную арифметику вместо стандартной целочисленной машинной, у которой разрядность целого числа ограничена.

[checat.livejournal.com]

Одну ошибку сделал. Вместо "Если значение счётчика достигло максимального значения для данного счётчика, записать в счётчик единицу" надо читать "Если значение счётчика достигло максимального значения для данного счётчика, записать в счётчик 0 (ноль)"

[cats_shadow]

ты написал линейный алгоритм для заданного количества различающихся элементов (2х).