Быстрый и эффективный способ проверить, является ли набор подмножеством любых других n наборов? - PullRequest
Новая
       99

Быстрый и эффективный способ проверить, является ли набор подмножеством любых других n наборов?

0 голосов
/ 12 марта 2020

У меня следующая проблема: у меня есть список элементов 

[O_0,..., O_n]

, где каждый элемент представлен двоичной степенью (o_0 представлен 2 ^ 0, ..., o_n равен 2 ^ п). Я построил список комбинаций этих элементов (каждая комбинация представлена ​​суммой двоичных представлений элементов). Например, у меня есть 

combs = [3, 9, 15, ......].

Учитывая новую комбинацию этих элементов, скажем, C_1, я хотел бы проверить, включен ли какой-либо из элементов combs в C_1. Я подумал, что эффективным и быстрым способом было вычислить для каждого элемента c_i from combs, проверить, если c_i & C_1 == c_i, что означает, что это верно для этого элемента. Это быстро, так как я делаю немного и Моя проблема в том, что вместо одного элемента C_1 у меня их очень много C_1, ..., C_k, и я должен проверить для каждого из них вышеуказанное условие. Так что мне было интересно, есть ли более быстрые способы, чем тот, который я упомянул, чтобы проверить состояние всех элементов (на самом деле это та же проблема, что и проверка, является ли набор подмножеством другого, поэтому я выбрал двоичное представление из начало превращать проблему в двоичную).

1 Ответ

0 голосов
/ 18 марта 2020

Мое понимание проблемы: учитывая набор k наборов Y и набор m наборов X, мы хотели бы найти подмножество S из Y, такое, что для всех y in S, существует x in X st x - это подмножество y.

Я предполагаю, что множества представлены n -векторами нулей и единицами, обозначающими включение. Вот установка: 

import pandas as pd # for drop_duplicates & benchmarks
import numpy as np

np.random.seed(0)

n = 100 # 100 "atomic" elements
m = 1000 # small sets
k = 1000 # large sets
X = pd.DataFrame(np.random.randint(0, 2, size=(m, n))).drop_duplicates().values
Y = pd.DataFrame(np.random.randint(0, 2, size=(k, n))).drop_duplicates().values
# For each row y in Y, we would like to check if there exists a row x in X
# s.t. x represents a subset of Y

def naive(Y, X):
  # O(k^2 + m^2) 
  for i, y in enumerate(Y):
    for x in X:
      found_subset = False
      if (x <= y).all():
        yield i
        found_subset = True
      if found_subset:
        break    

def naive_as_array(Y, X):
  return np.array(list(naive(Y, X)))

Функция naive выполняет итерацию по всем парам наборов, которые могут удовлетворять отношению включения и коротким замыканиям, когда это необходимо. Время выполнения равно O(m + k), где m = len(combs).

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

def contains(Y, X):
  """
  Y : k x n indicator array specifying sets
  X : m x n indicator array specifying sets
  output: subset Z of [0..k-1] s.t. i in Z iff there exists x in X s.t.
  # x is a subset of Y[i]. Z is represented by a 1D numpy array.
  """
  k, n = Y.shape
  assert Y.shape[1] == X.shape[1]
  detected = np.zeros(k, dtype=np.bool)
  inds = np.arange(k)

  # utility to account for sets that already have a subset detected
  def account_for_detected(Y, inds):
    mask = ~detected[inds]
    Y = Y[mask]
    inds = inds[mask]
    return Y, inds

  # inductively reduce Y.shape[1] (==X.shape[1])
  def f(Y, X, inds):
    if Y.shape[0] == 0 or X.shape[0] == 0:
      # collection Y is empty; inculsions are impossible
      return
    # avoid redundant comparisons by dropping sets y in Y
    # if it is already known that y contains some element of X
    Y, inds = account_for_detected(Y, inds)
    if Y.shape[1] == 1:
      # Y and X are collections of singletons
      Y = np.ravel(Y)
      X = np.ravel(X)
      X_vals = np.zeros(2, dtype=np.int)
      X_vals[X] = 1
      if X_vals[0] > 0:
        detected[inds] = True
      elif X_vals[1] > 0:
        detected[inds[Y==1]] = True
      return
    else:
      # make a recursive call
      Ymask = Y[:,0] == 0
      Xmask = X[:,0] == 0
      # if x in X is a subset of y in Y, x[0] <= y[0]
      f(Y[Ymask,1:], X[Xmask,1:], inds[Ymask])
      # by now, detected is updated in the outer scope
      # process the remaining Y's
      f(Y[~Ymask,1:], X[:,1:], inds[~Ymask])
      # done

  # make call at root:
  f(Y, X, inds)

  # return indices
  return np.where(detected)[0]

На шаге d между 1 и n мы разделяем множества Y на Y0 и Y1, где Y0 содержит множества в Y, которые не содержат элемент d и Y1 содержит наборы в Y, которые содержат элемент d. Аналогично, мы определяем X0 и X1. Ключевое наблюдение заключается в том, что наборы в X1 не могут встречаться как подмножества наборов в Y0. Следовательно, мы можем уменьшить количество сравнений в рекурсивном вызове.

Время: 

%timeit contains(Y, X)
%timeit naive_as_array(Y, X)
10 loops, best of 3: 185 ms per loop
1 loop, best of 3: 2.39 s per loop

enter image description here

...