1

Задавал вопрос на парочке ресурсов, пока ответ не нашел. Не могу придумать, как оптимально сделать следующий алгоритм:

Входные данные:

некоторое натуральное число N

некоторый массив массивов (массивы не повторяются), содержащих произвольные списки чисел (от 1 до N), например: { {1}, {1,2,7}, {3, 5}, ... ,{1,2,3,4,5,6} }

Выходные данные:

массив массивов массивов вида: { { {1}, {2,3}, {4,7}, {5}, {6,8},... }, { {1,2}, {3, 9}, {4,7}, {5}, {6,8},... }, … }

Любой массив массивов из выходных данных должен содержать все числа из набора (1, 2, ..., N) и ни одно число не должно повторяться дважды.

Возвращаемый массив массивов массивов должен содержать все возможные комбинации массивов массивов, удовлетворяющим условиям выше.

Отмечу, на всякий случай, что массив массивов, который есть во входных данных, может не содержать какие-либо из возможных комбинаций (например {1, 2, 3}). Соответственно, эта комбинация и НЕ должна рассматриваться далее.

Пример:

Входные данные:

N = 4

Массив массивов:

{  
{1},  
{2},  
{4},  
{1,2},  
{1,3},  
{1,3,4},  
{2,4},  
{3,4}   
}

Возвращаемые данные:

Массив массивов массивов:

{

{ {1},{2},{3,4} },

{ {1,2},{3,4} },

{ {1,3}, {2}, {4} },

{ {1,3}, {2,4} },

{ {1,3,4}, {2} }

}

Обновление

Мой вариант:

Cначала генерируется таблица вида (пусть N = 5):

11111 (все числа в одном массиве)    
11112 (четыре первых числа в одном массиве и одно во втором)    
...    
12131    
12133    
...    
12345

Потом из нее, построчно генерируются массивы массивов (соответственно):

{1,2,3,4,5}
{1,2,3,4},{5}
...
{1,3,5},{2},{4}
{1,3},{2},{4,5}
...
{1},{2},{3},{4},{5}

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

4
  • 1
    Задание С4 на ЕГЭ по информатике прям! Нифига не понятно, но якобы решить можно :) "Не могу придумать, как оптимально сделать следующий алгоритм:" Значит Вы уже придумали алгоритм, просто он через одно место работает? Представьте его, пожалуйста. Может хоть что-нибудь прояснится
    – fremail
    7 июл 2014 в 17:58
  • Обновил вопрос.
    – balalexv
    7 июл 2014 в 18:04
  • 1
    Это вам не сюда, а на маткод. Только переформулируйте в виде: «Дан набор подмножеств конечного множества. Найдите (эффективным образом) все такие поднаборы этого набора, что в каждом поднаборе (1) подможества дизъюнктны, и (2) их объединение покрывает исходное множество.» А так вообще пахнет динамическим программированием.
    – VladD
    7 июл 2014 в 20:55
  • @VladD, это действительно круто!
    – avp
    7 июл 2014 в 21:58

1 ответ 1

1

Первый вариант. Надо перебрать все сочетания из L (длина входного массива) по 1,2,...,N. Для перебора сочетаний разумно воспользоваться генерацией сочетаний.

Иными словами. сначала берем по одному массиву из входных данных, проверяем будут ли элементы от 1 до N. Далее берем сочетания двух массивов, объединяем (проверка чтоб элементы были от 1 до N) и пересекаем (чтоб не было повторов) их. И так далее. Максимальное количество массивов, участвующих в сочетании не может быть больше N - случай когда есть массивы по одному элементу от 1 до N: {1},{2},...,{N}.

Второй вариант. Для каждого массива, содержащего 1 подбираем массивы, дополняющие, но не пересекающиеся с ним. Т.е. выбрали массив с единицей, далее если в в массиве нет двойки, ищем массивы с двойкой. И так далее пока не дойдем до N. Соответственно если есть не пересекающиеся массивы с числами от 1 до N, добавляем такое сочетание в вывод.

Для небольших N массивы можно представить в виде бинарной записи числа, и на пересечение/объединение проверять битовыми операциями.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.