Набор наборов, содержащих наборы, которые являются подмножеством другого в наборе
Когда встроенные перечисления не достаточно, можно сделать это старомодный путь и обработать собственное. Например, если бы Вы хотели добавить дополнительное свойство, например, поле описания, Вы могли бы сделать это следующим образом:
public class Action {
public string Name {get; private set;}
public string Description {get; private set;}
private Action(string name, string description) {
Name = name;
Description = description;
}
public static Action DoIt = new Action("Do it", "This does things");
public static Action StopIt = new Action("Stop It", "This stops things");
}
можно тогда рассматривать его как перечисление как так:
public void ProcessAction(Action a) {
Console.WriteLine("Performing action: " + a.Name)
if (a == Action.DoIt) {
// ... and so on
}
}
прием должен удостовериться, что конструктор является частным (или защищенный, если Вы хотите наследоваться), и что Ваши экземпляры статичны.
4 ответа
Тривиальным подходом было бы сохранить список наборов и выполнить линейный поиск по нему для каждого входящего набора (проверка, является ли входящий подмножеством).
Это, очевидно, выполняется за O (n) времени для линейного поиска и, возможно, за O (m) размер для размера входящего набора. Таким образом, общее время O (n * m) (количество наборов в зависимости от размера каждого набора).
Самая очевидная оптимизация, конечно, заключается в индексировании по размерам наборов. Затем вы проверяете каждый входящий набор только на те, которые имеют такой же или больший размер. (Набор не может быть подмножеством какого-либо меньшего набора, да!)
Следующая оптимизация, которая приходит на ум, - это создание индекса элементов. Таким образом, для каждого входящего набора вы найдете пересечение каждого набора, содержащего каждый из элементов. Другими словами, если для входящего набора {a, b, c} мы обнаружим, что элемент {a} существует в наборах A, B и D, элемент {b} существует в B, E и F, и {c} существует в A, B и Z ... тогда входящее множество является подмножеством B (пересечение {A, B, D}, {B, E, F} и {A, B, Z}).
Итак, для меня это звучит как сложность O (m * log (n)). (Мы должны выполнить хешированный поиск по каждому элементу каждого входящего набора). Вставки также должны быть в том же порядке (вставка идентификатора нового набора в каждую карту элемента). (В анализе Big-O 2 * O (m log (n)) сокращается до O (m log (n)), конечно).
Тривиальная идея, которая будет работать в O (K), где K - размер добавляемого элемента.
- сохранять наборы любым способом
- сохранить карту set_id -> set_size
- сохранить карту объекта -> set_id
и A, и B равны O (K).
Если отдельные элементы ваших наборов A, B, ... отображаются в различные (и относительно) простые числа, и вместе с каждым набором вы сохраняете произведение всех членов как p ( A), p (B) и т. Д. Тогда подмножества и надмножества можно найти по тому, является ли p (X) множителем p (Y) или наоборот.
Я думаю, вы могли бы получить очень большие числа, но теоретически это работает.
Например:
if [abcd] -> [2 3 5 7], p (abc) = 30, p (abd) = 42, p (bc) = 15, p ( abcd) = 210
Какой тупой сайт! Я зарегистрировался, так что, возможно, со временем смогу комментировать материал вчерашнего дня. Однако до тех пор ...
@Stephen C: хотя я считаю, что мой английский достаточен, я, кажется, приобрел экспликатор: однако он пропустил кое-что, и его комментарий должен быть следующим:
@ Стивен С: поиск факторов произвольное число действительно является NP полным, но здесь не имеет значения. В вопрос в том, может ли меньшее из двух числа точно делит большее, a простая операция модуля. Например, p (bc) = 15 является делителем p (abcd) = 210, так что bc является подмножеством abcd (как и множества abd и abc).
Добавление нового набора S к существующему набору из N наборов составляет O (N), предполагая, что сравнение и разделение больших чисел занимает примерно одно и то же время независимо от N.
Для каждой существующей записи E в наборе множеств, остановить, если p (S)
p (E) и p (E) точно делит p (S). Добавьте S, если дойдете до конца коллекции. Массив BigNums подойдет.
@JL: если вы хотите быть моим преследователем, пожалуйста, постарайтесь 1) добавить ценность 2) точно.