Вычисление комбинаций/декартово произведение множеств (без дубликатов и без ограничений по порядку)

У меня есть комбинаторная задача, которую можно неэффективно решить, используя декартово произведение нескольких множеств. Конкретно, у меня есть несколько элементов и несколько элементов, которые удовлетворяют каждому элементу. Задача состоит в том, чтобы найти все возможные комбинации элементов, удовлетворяющие всем пунктам. Например:

items -> elements
------------------------
1 -> {a,b}     // a and b cover the item 1
2 -> {a,b}     // a and b cover the item 2
3 -> {a,b,c}   // a, b and c cover the item 3
4 -> {a,b,e,f} // a, b, e, f cover the item 4

Alternative representation:
element -> items covered
------------------------
a -> {1,2,3,4}
b -> {1,2,3,4}
c -> {3}
e -> {4}
f -> {4}

Цель состоит в том, чтобы найти все комбинации, которые охватывают пункты 1,2,3,4. Допустимые решения:

{a},{a,b},{a,c},{a,e},{a,f},{a,b,c},{a,b,e},{a,b,f},{a,b,c,e},{a,b,c,f}
{b},{b,c},{b,e},{b,f},{b,c,e},{b,c,f}

Обратите внимание, что порядок не важен, поэтому {a,b} = {b,a} ({a,b} x {c,d} = {c,d} x {a,b}). Также обратите внимание, что {a,a,a,a}, {a,a,a,b}... являются избыточными комбинациями.

Как видите, эта задача аналогична задаче set cover problem, где вселенная элементов для этого примера — это элементы U={1,2,3,4}, а набор подмножеств из U — S={ab={1,2,3,4},c={3},ef{4}}, где набор {1,2,3,4} — это набор элементов, покрываемых элементами a и b. , {3} — это набор элементов, покрываемых c, а {4} — это набор элементов, покрываемых элементами e и f. Однако цель здесь не в том, чтобы найти минимальную комбинацию наборов из S, которая покрывает все элементы из U, а в том, чтобы найти все комбинации элементов {a,b,c,e,f}, которые охватывают все элементы {1,2,3,4}.

Простую реализацию можно было бы реализовать, выполнив декартово произведение между наборами для 1, 2, 3 и 4, а затем отфильтровав избыточные комбинации. Однако такой подход очень неэффективен. Предположим, у меня есть такая ситуация:

1 -> {a,b,c,d,e,f,g,h}
2 -> {a,b,c,d,e,f,g,h}
3 -> {a,b,c,d,e,f,g,h}
4 -> {a,b,c,d,e,f,g,h}
5 -> {a,b,c,d,e,f,g,h}
6 -> {a,b,c,d,e,f,g,h,i}

Декартово произведение шести наборов даст 8^5*9=294912 комбинаций, тогда как на самом деле комбинаций намного меньше, а именно: {a,b,c,d,e,f,g} U {a,b,c,d,e,f,g} x {i}.

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

Как бы вы решили эту проблему?


algorithm cartesian-product combinations enumeration
person Markov Unchained    schedule 24.04.2013    source источник
comment
Вы пытаетесь найти все комбинации элементов, найденных путем объединения N наборов? Если да, то вот некоторый псевдокод для этого. В противном случае объясните, пожалуйста, что вы имеете в виду под обложкой - что означает набор для покрытия 1,2,3 и т.д. (обычно под обложкой подразумевается установить проблему с покрытием, но я не думаю, что это то, что вам здесь нужно)   -  person Zim-Zam O'Pootertoot    schedule 24.04.2013
comment
Вы используете слово комбинация нестандартным образом, поэтому необходимо определить его значение. Также необходимо определить удовлетворить (очевидно, вы имеете в виду обложку) и определить элемент и элемент. Или перепишите свой вопрос, используя стандартную терминологию.   -  person James Waldby - jwpat7    schedule 24.04.2013
comment
Возможно, мне следовало формализовать проблему, а не объяснять ее неформально, но я подумал, что ее будет легко понять на некоторых примерах. Я отредактировал описание, пытаясь лучше описать проблему. Спасибо за советы.   -  person Markov Unchained    schedule 24.04.2013
comment
почему вы не указали {a,b,e} в качестве допустимого решения в своем первом примере? Это потому, что вы указали только некоторые из допустимых комбинаций? Кстати, я добавил к своему ответу код Haskell, который дает немедленный результат для двух приведенных примеров ... насколько большими, по вашему мнению, будут входные данные?   -  person גלעד ברקן    schedule 25.04.2013
comment
Ты прав. {a,b,e} также является допустимым решением.   -  person Markov Unchained    schedule 25.04.2013

Ответы (2)


arrow_upward
2
arrow_downward

Во-первых, поймите, что если набор элементов не удовлетворяет всем требованиям, то и ни одно из его подмножеств не удовлетворяет.

Во-вторых, поймите, что если набор удовлетворяет всем требованиям, то и все его супермножества удовлетворяют.

Теперь все, что вам нужно сделать, это:

Пусть S будет множеством всех элементов. Пусть R — пустое множество.

Определите функцию find( s, r ), которая выполняет:

If r includes s, return r.
If s does not satisfy all items, return r.

Otherwise add s to r.
For every item I in  s,
     let s' be s-I
     let s be f(s', r)

return s.

Просто позвоните find(S,R) и получите ответ.

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

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

person Agentlien    schedule 24.04.2013

arrow_upward
1
arrow_downward

Что, если бы вы сделали это:

1 -> {a,b}
2 -> {b,c}
3 -> {a,b,c}
4 -> {a,e,f}

=>

a -> [1,3,4]
b -> [1,2,3]
c -> [2,3]
e -> [4]
f -> [4]

Затем перечислите комбинации левой части, которые обеспечивают (как минимум) [1,2,3,4]

For each item in the set of all-satisfying sets, enumerate combinations 
with other items.

All-Satisfying-Sets: {{a,b},{b,e},{b,f}}
Combinations within All-Satisfiying-Sets: {{a,b,e},{a,b,f},{b,e,f},{a,b,e,f}}
Others: {c}
Combinations with Others: {{a,b,c},{b,e,c},{b,f,c}
                          ,{a,b,e,c},{a,b,f,c},{b,e,f,c},{a,b,e,f,c}}

Или вы можете сделать это в Haskell:

import Data.List (union, subsequences, sort)

example1 = [(["a"],[1,2,3,4])
           ,(["b"],[1,2,3,4])
           ,(["c"],[3])
           ,(["e"],[4])
           ,(["f"],[4])]

example2 = [(["a"],[1,2,3,4,5,6])
           ,(["b"],[1,2,3,4,5,6])
           ,(["c"],[1,2,3,4,5,6])
           ,(["e"],[1,2,3,4,5,6])
           ,(["f"],[1,2,3,4,5,6])
           ,(["g"],[1,2,3,4,5,6])
           ,(["h"],[1,2,3,4,5,6])
           ,(["i"],[6])]

combs items list = 
  let unify (a,b) (a',b') = (sort (a ++ a'), sort (union b b')) 
  in map fst
     . filter ((==items) . snd) 
     . map (foldr unify ([],[])) 
     . subsequences 
     $ list


OUTPUT:

*Main> combs [1..4] example1
[["a"],["b"],["a","b"],["a","c"],["b","c"],["a","b","c"],["a","e"],["b","e"],
["a","b","e"],["a","c","e"],["b","c","e"],["a","b","c","e"],["a","f"],["b","f"], 
["a","b","f"],["a","c","f"],["b","c","f"],["a","b","c","f"],["a","e","f"],
["b","e","f"],["a","b","e","f"],["a","c","e","f"],["b","c","e","f"],
["a","b","c","e","f"]]
person גלעד ברקן    schedule 24.04.2013
comment
Да, это идея, но я пытаюсь выяснить, является ли эта проблема очень известной проблемой и лучшим алгоритмом для ее решения. - person Markov Unchained; 24.04.2013