Нахождение всех возможных наборов упаковок

Question

Скажем, у меня есть матрица S размера (m,n), где m - количество наборов, а n - количество всех возможных наборов элементов. В этой матрице, если запись S(i,j) равна 1, множество i имеет элемент j, а в противном случае элемент S(i,j) равен 0.

Мой вопрос: существуют ли какие-либо известные относительно эффективные алгоритмы для перечисления всех возможных упаковок наборов (т. Е. Таких комбинаций наборов, что никакие два набора не пересекаются)?

Используя это представление, упаковка k определяется как вектор p_k = [p_{k,1}, p_{k,1}, ... p_{k,km}], где элементы p_{k,r} являются индексами строк в S (т.е. наборах), так что пересечение наборов в p_k равно 0. Или, другими словами, внутреннее произведение любых двух векторов строк p_{k,r} * p_{k,s}', индексированных p_k в S, равно 0.

Я ищу реализацию в MATLAB (или что-то вызываемое из MATLAB), но если кто-нибудь знает о быстрой реализации в какой-то другой библиотеке, это также будет полезно.

Answer 1

Не может быть никакого алгоритма полиномиального порядка для перечисления всех возможных упаковок для вашей задачи, потому что таких упаковок экспоненциально много.Например, с m, n = 3,4, есть 2 ^ (n-1) конфигурации упаковки, которые включают все n элементов: {abcd}, {a} {bcd}, {ab} {cd}, {abc}{d}, {a} {b} {cd}, {a} {bc} {d}, {ab} {c} {d}, {a} {b} {c} {d}.(Предположительно, наборы не различаются; например, {abc} {d} эквивалентны {d} {abc}. Если наборы различаются , в следующем методе просто подсчитайте, не исключая подсчетов, то есть не применяет никаких правил.)

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

Один из способов перечисления всех допустимых случаев - это подсчет базового числа m + 1 H от H = 0 до доли (m + 1) ^ n, применяя некоторые правила для выбора допустимых конфигураций.Пусть dj обозначает j-ю цифру H, с d.1 наименее значимым.Если dj равно 0, элемент j является членом множества no;если dj = k> 0, j является членом множества k.Пусть Ai (H) = самое высокое положение цифры i в H или -i, если i не происходит;требуют Ai> A. (i + 1).A (H) может поддерживаться и тестироваться постепенно за время O (1), когда H считает.Например, чтобы исключить 1323 (== 1232) в следующем примере (ручной работы), обратите внимание, что A.2 (1323) = 2 <3 = A.3 (1323).</p>

Пример: n = 4 = #elements;m = 3 = #sets;H-последовательность с неотличимыми наборами должна быть: 0000, 0001, 0010, 0011, 0012, 0100, 0101, 0102, 0110, 0111, 0112, 0120, 0121, 0122, 0123, 1000, 1001, 1010, 1011, 1012, 11001101, 1102, 1110, 1111, 1112, 1120, 1121, 1122, 1123, 1200, 1201, 1202, 1203, 1210, 1211, 1212, 1213, 1220, 1221, 1222, 1223, 1230, 1231, 1232, 1233.

Answer 2

Боюсь, не совсем эффективно, но, безусловно, больше, чем грубая сила.

Я понимаю, что количество упаковок может варьироваться от 1 до (максимум) м.

Чтобы найти все возможные решения,начать с кардинальности 1 и повторять до:

• вы достигнете m

• или больше не будет кандидатов дляследующая итерация (подробнее об этом ниже).

Матрица-кандидат имеет ту же форму, что и S.На итерации n он содержит элементы действительной упаковки, найденные на итерации n-1.Он инициализируется на итерации 1 со значениями S.

На каждом шаге мощности

• для каждой строки матрицы-кандидата вы проверяете, можете ли вы создать несколько упаковок, которыевсе еще действительны, добавляя одну (и только одну) строку матрицы S:

  • Вы перебираете каждую строку S (это может быть сделано быстрее, если вы пропустите строки, которые уже находятся всама упаковка).Если он действителен, вы добавляете рассматриваемый индекс строки в упаковку, отправляете эту упаковку как новый результат и добавляете ее в матрицу-кандидат future, next итерацию (которая будет меньше на каждом шаге мощности, потому что некоторыерезультат комбинации в неправильных упаковках).

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

Пример

S=
 1 0 0 1  (a)
 1 1 0 0  (b)
 0 0 1 0  (c)

Итерация 1

(инициализация): произвести 3 результата и кандидатов: a, b и c (инициализация)

результаты

(a,b,c)

кандидатов

 1 0 0 1  (a)
 1 1 0 0  (b)
 0 0 1 0  (c)

Итерации 2

итерации по кандидату, затем по строкам:

• принять кандидата a

  • пропустить строку a (оптимизация 1)
  • попытаться объединить его со строкой b -> сбой
  • попытаться объединить егосо строкой c -> success
    • новые результаты (ac) и новый кандидат (ac) в следующий раз

• принять кандидата b

  • попытаться объединить его со строкой a -> fail
  • пропустить строку b (оптимизация 1)
  • попробуйте объединить его со строкой c -> success
    • новые результаты (bc) и новый кандидат (bc) для следующего раза

• принять кандидата c

  • пропустить a -> (в результате уже существует)
  • пропустить c -> (в результате уже существует)
  • пропустить строку c (оптимизация 1)

Новая матрица результатов (a, b, c, ac, bc)

Матрица новых кандидатов

 1 0 1 1 (ac)
 1 1 1 0 (bc)

Итерация 3

То же, что и выше ...

• принять кандидата (ac)

  • пропустить строку a (оптимизация 1)
  • попытаться объединить ее со строкой b -> fail
  • пропустить строку c (оптимизация 1)

• принять кандидата (bc)

  • попытаться объединить его со строкой a -> fail
  • пропустить строку b (оптимизация 1)
  • скip строка c (оптимизация 1)

Нет больше кандидатов: конец.

Матрица окончательных результатов (a, b, c,ac, bc)

Матрица окончательных кандидатов

 ()

Об оптимизации

• Оптимизация 1: нет необходимости пытаться объединитьстрока с кандидатом на упаковку, который уже содержит ее