Задавал вопрос на парочке ресурсов, пока ответ не нашел. Не могу придумать, как оптимально сделать следующий алгоритм:
Входные данные:
некоторое натуральное число 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}
Потом пробежаться по списку и удалить все варианты, содержащие хотя бы один недоступный массив чисел. Ну, либо можно сразу убирать ненужные варианты, но это все-таки не путь джедаев какой-то - генерируются все варианты и удаляются ненужные.