Эффективный алгоритм нахождения всех максимальных подмножеств

Ответ 1

Предположим, что вы помечаете все наборы ввода.

A={1, 2, 3}, B={1, 2}, C={2, 3}, D={2, 4}, E={}

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

1={A,B}
2={A,B,C,D}
3={A,C}
4={D}

Теперь для каждого набора входных данных вычислим пересечение всех наборов ярлыков его элементов:

For A, {A,B} intesect {A,B,C,D} intersect {A,C} = {A}   (*)

Если пересечение содержит некоторую метку, отличную от самого множества, то оно является подмножеством этого множества. Здесь нет другого элемента, поэтому ответ отрицательный. Но,

For C, {A,B,C,D} intersect {A,C} = {A,C}, which means that it a subset of A.

Стоимость этого метода зависит от реализации множеств. Предположим, что растровые изображения (как вы намекали). Скажем, есть n наборов ввода максимального размера m и | U | предметов во вселенной. Тогда конструкция промежуточного множества дает | U | наборы битов размера n, поэтому существует время O (| U | n) для их инициализации. Для установки битов требуется время O (нм). Вычисление каждого пересечения как при (*) выше требует O (mn); O (mn ^ 2) для всех.

Полагая все это вместе, имеем O (| U | n) + O (nm) + O (mn ^ 2) = O (| U | n + mn ^ 2). Используя те же самые соглашения, ваш алгоритм "всех пар" равен O (| U | ^ 2 n ^ 2). Поскольку m <= | U |, этот алгоритм асимптотически быстрее. Вероятно, это будет скорее на практике, потому что нет сложной бухгалтерской отчетности, чтобы добавить постоянные факторы.

Дополнение: On Line Version

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

Ключ должен отметить, что A является надмножеством B, если if A' является подмножеством B' (дополнение для набора галочек).

Следуя этому вдохновению, мы сохраняем промежуточный набор, как и раньше. Когда поступит новый входной набор S, выполните тот же тест, что и описанный выше: пусть I(e) будет промежуточным для входного элемента e. Тогда это испытание

For X = \intersect_{e \in S} . I(e), |X| > 0

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

В противном случае мы должны добавить S в качестве нового максимального набора, но прежде чем это сделать, вычислите:

Y = \intersect_{e \in S'} . I'(e) = ( \union_{e \in S'} . I(e) )'

где снова устанавливается галочка '. Форма объединения может быть немного быстрее для вычисления. Y содержит максимальные множества, которые были заменены на S. Они должны быть удалены из максимального набора и из I. Наконец добавьте S в качестве максимального набора и обновите I с помощью элементов S.

Давайте работать в нашем примере. Когда A прибывает, мы добавляем его в I и имеем

1={A}  2={A}  3={A}

Когда прибывает B, мы находим X = {A} intersect {A} = {A}, поэтому отбрасываем B и продолжаем. То же самое происходит и для C. Когда D прибывает, мы находим X = {A} intersect {} = {}, поэтому продолжаем с Y = I'(1) intersect I'(3) = {} intersect {}. Это правильно говорит нам, что максимальное число A не содержится в D, поэтому удалить ничего не удастся. Но он должен быть добавлен как новый максимальный набор, а I становится

1={A}  2={A,D}  3={A}  4={D}

Прибытие e не вызывает никаких изменений. Положите приход нового набора F={2, 3, 4, 5}. Найдем

X = {A} isect {A,D} isect {A} isect {D} isect {}

поэтому мы не можем выбросить F. Продолжить с помощью

Y = \intersect_{e in {1}} I'(e) = I'(1) = {D}

Это говорит нам, что D является подмножеством F, поэтому его следует отбрасывать при добавлении F, оставляя

1={A} 2={A,F} 3={A,F} 4={F} 5={F}

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

Я надеюсь, что это будет полезно.

Резюме

Общий принцип работы здесь - мощная идея о том, что урожаи часто в дизайне алгоритмов. Это обратная карта. Всякий раз, когда вы обнаруживаете, что выполняете линейный поиск, чтобы найти элемент с заданным атрибутом, подумайте о создании карты из атрибута обратно в элемент. Часто дешево строить эту карту, и это сильно сокращает время поиска. Примером примера является карта перестановок p[i], которая сообщает вам, в какой позиции элемент I'th будет занимать после перенастройки массива. Если вам нужно найти элемент, который попадает в заданное местоположение A, вы должны выполнить поиск p для A, линейной операции времени. С другой стороны, обратное отображение pi такое, что pi[p[i]] == i перестает вычисляться, чем p (поэтому его стоимость "скрыта" ), но pi[a] дает желаемый результат в постоянное время.

Реализация оригинальным плакатом

import collections
import operator

def is_power_of_two(n):
    """Returns True iff n is a power of two.  Assumes n > 0."""
    return (n & (n - 1)) == 0

def eliminate_subsets(sequence_of_sets):
    """Return a list of the elements of `sequence_of_sets`, removing all
    elements that are subsets of other elements.  Assumes that each
    element is a set or frozenset and that no element is repeated."""
    # The code below does not handle the case of a sequence containing
    # only the empty set, so let just handle all easy cases now.
    if len(sequence_of_sets) <= 1:
        return list(sequence_of_sets)
    # We need an indexable sequence so that we can use a bitmap to
    # represent each set.
    if not isinstance(sequence_of_sets, collections.Sequence):
        sequence_of_sets = list(sequence_of_sets)
    # For each element, construct the list of all sets containing that
    # element.
    sets_containing_element = {}
    for i, s in enumerate(sequence_of_sets):
        for element in s:
            try:
                sets_containing_element[element] |= 1 << i
            except KeyError:
                sets_containing_element[element] = 1 << i
    # For each set, if the intersection of all of the lists in which it is
    # contained has length != 1, this set can be eliminated.
    out = [s for s in sequence_of_sets
           if s and is_power_of_two(reduce(
               operator.and_, (sets_containing_element[x] for x in s)))]
    return out

Ответ 2

В верхней части моей головы находится O (D * N * log (N)), где D - количество уникальных чисел.

Рекурсивная функция "помощник" работает следующим образом: @arguments - это наборы и домен (количество уникальных чисел в наборах): Базовые случаи:

• Если домен пуст, верните
• Если набор пуст или множества имеют длину, равную 1, верните

Итеративный случай:

• Удалите все пустые множества из наборов
• Выберите элемент D в домене
• Удалить D из домена
• Разделяйте наборы в два набора (set1 и set2) в зависимости от того, содержит ли набор D
• Удалить D из каждого набора в наборах
• Установить результат = объединение (хелпер (set1, домен), хелпер (set2, домен))
• Для каждого набора в set1 добавьте D back
• результат возврата

Обратите внимание, что время выполнения зависит от используемой реализации Set. Если для хранения набора используется дважды связанный список:

Шаги 1-5,7 принимают O (N) Соединение шага 6 - это O (N * log (N)) путем сортировки, а затем слияния

Следовательно, общий алгоритм O (D * N * log (N))

Вот java-код для выполнения следующих

import java.util.*;

public class MyMain {

    public static Set<Set<Integer>> eliminate_subsets(Set<Set<Integer>> sets) throws Exception {
        Set<Integer> domain = new HashSet<Integer>();
        for (Set<Integer> set : sets) {
            for (Integer i : set) {
                domain.add(i);
            }
        }
        return helper(sets,domain);
    }

    public static Set<Set<Integer>> helper(Set<Set<Integer>> sets, Set<Integer> domain) throws Exception {
        if (domain.isEmpty()) { return sets; }
        if (sets.isEmpty()) { return sets; }
        else if (sets.size() == 1) { return sets; }

        sets.remove(new HashSet<Integer>());

        // Pop some value from domain
        Iterator<Integer> it = domain.iterator();
        Integer splitNum = it.next();
        it.remove();

        Set<Set<Integer>> set1 = new HashSet<Set<Integer>>(); 
        Set<Set<Integer>> set2 = new HashSet<Set<Integer>>();
        for (Set<Integer> set : sets) {
            if (set.contains(splitNum)) {
                set.remove(splitNum);
                set1.add(set);
            }
            else {
                set2.add(set);
            }
        }

        Set<Set<Integer>> ret = helper(set1,domain);
        ret.addAll(helper(set2,domain));

        for (Set<Integer> set : set1) {
            set.add(splitNum);
        }
        return ret;
    }

    /**
     * @param args
     * @throws Exception 
     */
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        Set<Set<Integer>> s=new HashSet<Set<Integer>>();
        Set<Integer> tmp = new HashSet<Integer>();
        tmp.add(new Integer(1)); tmp.add(new Integer(2)); tmp.add(new Integer(3));
        s.add(tmp);

        tmp = new HashSet<Integer>();
        tmp.add(new Integer(1)); tmp.add(new Integer(2));
        s.add(tmp);

        tmp = new HashSet<Integer>();
        tmp.add(new Integer(3)); tmp.add(new Integer(4));
        s.add(tmp);
        System.out.println(eliminate_subsets(s).toString());
    }


}

* Новые годы разрушительны

Ответ 3

Эта проблема изучена в литературе. Учитывая, что S_1,..., S_k, которые являются подмножествами {1,..., n}, Yellin [1] дал алгоритм для нахождения максимального подмножества {S_1,..., S_k} во времени O (kdm) где d - средний размер S_i, а m - мощность максимального подмножества {S_1,..., S_k}. Позднее это было улучшено для некоторого диапазона параметров, полученными Еллиным и Ютлой [2] до O ((kd) ^ 2/sqrt (log (kd))). Считается, что по-настоящему субквадратичный алгоритм этой проблемы не существует.

[1] Daniel M. Yellin: Алгоритмы для подмножества тестирования и поиска максимальных наборов. SODA 1992: 386-392.

[2] Daniel M. Yellin, Charanjit S. Jutla: Поиск экстремальных множеств в менее чем квадратичное время. Inf. Обработать. Lett. 48 (1): 29-34 (1993).

Ответ 4

Предположения предварительной обработки:

Подход №2 - Используйте подход с ковшом

Те же предположения. Можно ли предположить уникальность? (то есть нет {1,4,6}, {1,4,6}) В противном случае вам нужно будет проверить, нет ли в какой-то момент, возможно, после создания ведра.

semi psuedo

List<Set> Sets;//input
List<Set> Output;
List<List<Set>> Buckets;
int length = Sets[0].length;//"by descending lengths"
List<Set> Bucket = new List<Set>();//current bucket

//Place each set with shared length in its own bucket
for( Set set in Sets )
{
 if( set.length == length )//current Bucket
 {
  Bucket.add(set);
 }else//new Bucket
 {
  length = set.length;
  Buckets.Add(Bucket);
  Bucket = new Bucket();
  Bucket.Add(set);
 }
}
Buckets.add(Bucket);



//Based on the assumption of uniqueness, everything in the first bucket is
//larger than every other set and since it is unique, they are not proper subsets
Output.AddRange(Buckets[0]);

//Iterate through the buckets
for( int i = 1; i < Buckets.length; i++ )
{
 List<Set> currentBucket = Buckets[i];

 //Iterate through the sets in the current bucket
 for( int a = 0; a < currentBucket.length; a++ )
 {
  Set currentSet = currentBucket[a];
  bool addSet = true;
  //Iterate through buckets with greater length
  for( int b = 0; b < i; b++ )
  {
   List<Set> testBucket = Buckets[b];

   //Iterate through the sets in testBucket
   for( int c = 0; c < testBucket.length; c++ )
   {
    Set testSet = testBucket[c];
    int testMatches = 0;

    //Iterate through the values in the current set
    for( int d = 0; d < currentSet.length; d++ )
    {
     int testIndex = 0;

     //Iterate through the values in the test set
     for( ; testIndex < testSet.length; testIndex++ )
     {
      if( currentSet[d] < testSet[testIndex] )
      {
       setClear = true;
       break;
      }
      if( currentSet[d] == testSet[testIndex] )
      {
       testMatches++;
       if( testMatches == currentSet.length )
       {
        addSet = false;
        setClear = true;
        break;
       }
      }
     }//testIndex
     if( setClear ) break;
    }//d
    if( !addSet ) break;
   }//c
   if( !addSet ) break;
  }//b
  if( addSet ) Output.Add( currentSet );
 }//a
}//i

Подход №1 (O( n(n+1)/2 ))... недостаточно эффективен

semi psuedo

//input Sets
List<Set> results;
for( int current = 0; current < Sets.length; current++ )
{
 bool addCurrent = true;
 Set currentSet = Sets[current];
 for( int other = 0; other < current; other++)
 {
  Set otherSet = Sets[other];
  //is current a subset of other?
  if( currentSet.total > otherSet.total 
   || currentSet.length >= otherSet.length) continue;
  int max = currentSet.length;
  int matches = 0;
  int otherIndex = 0, len = otherSet.length;
  for( int i = 0; i < max; i++ )
  {
   for( ; otherIndex < len; otherIndex++ )
   {
     if( currentSet[i] == otherSet[otherInex] )
     {
      matches++;
      break;
     }
   }
   if( matches == max )
   {
    addCurrent = false;
    break;
   }
  }
  if( addCurrent ) results.Add(currentSet);
 }
}

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

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

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