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

[cats_shadow]

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

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

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

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

Comments

[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 (ноль)"