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

Question

Я ищу эффективный способ определить, является ли набор подмножеством другого набора в Matlab или Mathematica.

Пример: Set A = [1 2 3 4] Set B = [4 3]Установите C = [3 4 1] Установите D = [4 3 2 1]

Выходные данные должны быть: Установить A

Наборы B и C принадлежат множеству A, потому что A содержит все ихэлементы, следовательно, они могут быть удалены (порядок элементов в наборе не имеет значения).Множество D имеет те же элементы, что и множество A, и поскольку множество A предшествует множеству D, я хотел бы просто сохранить множество A и удалить множество D.

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

Мой код Matlab не очень эффективен для этого - он в основном состоит из вложенных циклов.

Предложения очень приветствуются!

Дополнительное объяснение: проблема в том, что при большом количестве наборов будет очень большое количество парных сравнений.

Answer 1

Скорее всего, вы захотите взглянуть на встроенные функции установки набора в MATLAB.Зачем изобретать велосипед, если не нужно?;)

Подсказка: Функция ISMEMBER может представлять для вас особый интерес.

РЕДАКТИРОВАТЬ:

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

setList = {[1 2 3 4],...  %# All your sets, stored in one cell array
           [4 3],...
           [3 4 1],...
           [4 3 2 1]};
nSets = numel(setList);                       %# Get the number of sets
setSizes = cellfun(@numel,setList);           %# Get the size of each set
[temp,sortIndex] = sort(setSizes,'descend');  %# Get the sort index
setList = setList(sortIndex);                 %# Sort the sets

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

for outerLoop = nSets:-1:2
  for innerLoop = 1:(outerLoop-1)
    if all(ismember(setList{outerLoop},setList{innerLoop}))
      setList(outerLoop) = [];
      break;
    end
  end
end

После выполнения вышеуказанного кода setList удалит из него все наборы, которые являются подмножествами или дубликатами.других наборов, предшествующих им в списке.

В лучшем случае (например, данные примера в вашем вопросе) внутренний цикл каждый раз прерывается после первой итерации, выполняя только nSets-1 сравнения множеств с использованием IsMember .В худшем случае внутренний цикл никогда не прерывается, и он будет выполнять (nSets-1)*nSets/2 сравнения наборов.

Answer 2

Предполагая, что если ни один набор не является надмножеством всех предоставленных наборов, вы хотите вернуть пустой набор. (Т. Е. Если ни один набор не является надмножеством всех наборов, верните "no thing".)

Итак, ..., вы хотите взять объединение всех наборов, а затем найти первый набор в вашем списке с таким количеством элементов. Это не так сложно, пропуская переформатирование ввода во внутреннюю форму списка ... Mathematica:

    topSet[a_List] := Module[{pool, biggest, lenBig, i, lenI},  
        pool = DeleteDuplicates[Flatten[a]];  
        biggest = {}; lenBig = 0;  
        For[i = 1, i <= Length[a], i++,  
            lenI = Length[a[[i]]];  
            If[lenI > lenBig, lenBig = lenI; biggest = a[[i]]];  
            ];  
        If[lenBig == Length[pool], biggest, {}]  
    ]  

Например:

    topSet[{{1,2,3,4},{4,3},{3,4,1},{4,3,2,1}}]  
      {1,2,3,4}  
    topSet[{{4, 3, 2, 1}, {1, 2, 3, 4}, {4, 3}, {3, 4, 1}}]  
      {4,3,2,1}  
    topSet[{{1, 2}, {3, 4}}]  
      {}  

Как большой тест:

    <<Combinatorica`  
    Timing[Short[topSet[Table[RandomSubset[Range[10^3]], {10^3}]]]]  
      {14.64, {}}  

То есть, набор из 1000 случайно выбранных подмножеств диапазона [1,1000] был проанализирован за 14,64 секунды (и, что неудивительно, ни один из них не оказался надмножеством всех из них).

- Правка - Экранировал меньше, чем прятал несколько строк реализации. Также ...

Анализ времени выполнения: пусть L будет количеством списков, N будет общим количеством элементов во всех списках (включая дубликаты). Назначение пула принимает O (L) для выравнивания и O (N) для удаления дубликатов. В цикле for все L-назначения для lenI кумулятивно требуют времени O (N), а все L-условия требуют не более O (L) времени. Остальное O (1). Поскольку L

Доказательство правильности: надмножество, если оно существует, (1) содержит себя, (2) содержит любую перестановку себя, (3) содержит каждый элемент, присутствующий в любом (другом) наборе, (4) имеет длину или дольше, чем любой другой набор в коллекции. Последствия: надмножество (если присутствует) является самым длинным набором в коллекции, любой другой набор равной длины является его перестановкой и содержит копию каждого элемента, содержащегося в любом наборе. Следовательно, существует надмножество, если существует множество, равное объединению набора множеств.

Answer 3

Я думаю, что вопрос, который вы хотите задать, это «учитывая список наборов, выберите набор, который содержит все остальные». Существует множество крайних случаев, когда я не знаю, какой вывод вы хотели бы получить (например, A = {1, 2} и B = {3, 4}), поэтому вам нужно многое уточнить.

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

setA = {1, 2, 3, 4};
setB = {4, 3};
setC = {3, 4, 1};
setD = {4, 3, 2, 1};
Complement[setD, setA] == {}
 True

указывает, что setD является подмножеством набора A.

Answer 4

In Mathematica Я предлагаю использовать для этого Alternatives.

Например, если у нас есть набор {1, 2, 3, 4} и мы хотим проверить, является ли набор x подмножеством, мы могли бы использовать: MatchQ[x, {(1|2|3|4) ..}].Преимущество этой конструкции состоит в том, что как только будет найден элемент, который не принадлежит, тест остановится и вернет значение False.

Мы можем упаковать этот метод следующим образом:

maximal[sets_] :=
  Module[{f},
    f[x__] := (f[Union @ Alternatives @ x ..] = Sequence[]; {x});
    f @@@ sets
  ]

maximal @ {{1, 2, 3, 4}, {4, 3}, {5, 1}, {3, 4, 1}, {4, 3, 2, 1}}

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