Общая задача алгоритма подмножества - PullRequest
Новая
       8

Общая задача алгоритма подмножества

1 голос
/ 29 августа 2009

У меня следующая проблема.

У меня есть набор предметов {a1, a2, a3, ... aN}. Каждый из этих предметов может содержать другой набор предметов {b1, b2, b3, ... bN}. Таким образом, конечный результат выглядит примерно так: 

a1
  b4
  b22
  b40
  b11
  b9
a2
  b30
  b23
  b9
  b4
  b11
a3
  b22
  b4
  b60
  b9

В результате выполнения алгоритма я хотел бы получить группы объектов b-типа, которые подпадают под следующие правила:

  1. Если более одного объекта b-типа под объектом a-типа существует только под этим объектом a-типа, их следует сгруппировать.
  2. Если в более чем одном объекте типа a используется более одного объекта b-типа, их также следует сгруппировать.

Пример: 

b4, b9
b30, b23

b40, b60, b11 and b22 shouldn't be grouped because there are no pairs for them.

Я бы написал реализацию этого алгоритма на C #, поэтому было бы неплохо избежать структур данных, которые в нем не существуют, таких как двоичные деревья, связанные списки и т. Д. Но это не является обязательным требованием; все это тоже можно реализовать.

Уточнение : Наборы могут содержать столько объектов, сколько необходимо, но не более 1 каждого. Правила заключаются в том, что все уникальные объекты b-типа внутри одного и того же a-типа должны быть сгруппированы (более 1), и если более 1 объекта b-типа попадают в более чем 1 объект a-типа, они должны быть сгруппированы. Группы должны быть максимально большими.

Пример из реальной жизни : веб-страницы a-type и CSS-файлы, используемые на этих страницах, b-type . Чтобы ускорить загрузку страниц, вы хотите, чтобы на сервер было как можно меньше запросов, поэтому вы объединяете файлы CSS, но не хотите объединять файлы, которые используются сами по себе, только на нескольких страницах. , поскольку они будут кешированы, и вам не нужно повторно загружать их снова.

1 Ответ

2 голосов
/ 29 августа 2009

Сначала создайте карту, которая связывает каждый элемент b-типа с набором элементов a-типа, который содержит этот элемент b-типа.

В вашем примере вы получите:

b4: {a1, a2, a3}

b9: {a1, a2, a3}

b11: {a1, a2}

b22: {a1, a3}

b23: {a2}

b30: {a2}

b40: {a1}

b60: {a3}

Чтобы создать эту карту, отсканируйте все объекты b-типа в объектах a-типа, и, если объект b-типа не имеет ассоциации, создайте для него запись на карте; однако добавьте объект a-типа в набор, связанный с объектом b-типа.

Затем сравните все возможные пары множеств (O (n2)). Объедините два объекта b-типа, если они имеют одинаковый набор объектов a-типа.

Он реализован в виде пары вложенных циклов на карте (I = 1 TO N-1, J = N + 1 TO N).

Чтобы сравнить два набора, используйте библиотеку наборов и оператор сравнения.

Если объекты a-типа могут быть представлены маленькими целыми числами, вы можете представить набор в виде битового массива, который является довольно компактным и быстрым для сравнения.

...