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

Ответ 1

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

СОВЕТ: Функция ISMEMBER может представлять для вас особый интерес.

EDIT:

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

Ответ 2

Я думаю, что вопрос, который вы хотите задать, "задан список наборов, выберите набор, содержащий все остальные". Есть куча крайних случаев, когда я не знаю, какой результат вы хотите (например, 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 является подмножеством setA.

Ответ 3

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

Итак,..., вы хотите взять объединение всех множеств, а затем найти первый набор в своем списке с таким количеством элементов. Это не слишком сложно, пропуская переформатирование ввода во внутреннюю форму списка... 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, {}}  

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

- Edit - Сбежал меньше, чем скрывал несколько строк реализации. Также...

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

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

Ответ 4

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

Например, если у нас есть набор {1, 2, 3, 4}, и мы хотим проверить, установлено ли set 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}}