Запрос для Set Cover
Добрый день, я хотел бы реализовать T-SQL-запрос для решения проблемы покрытия, но не смог найти никаких подсказок о том, как это сделать в SQL.
В моем случае в моей таблице только два столбца (IDnumber
а также Mut
) и я хочу найти минимальное количество IDNumber
чтобы получить один из каждого Mut
, Я очень хочу получить три IDnumbers
для каждого Mut
но я решил, что лучше начать с одного, потому что это может быть проще.
DECLARE @myTable TABLE (
IDnumber int,
Mut varchar(1))
INSERT @myTable VALUES
(1,'C'), (1,'N'), (1,'Z'), (1,'M'), (1,'E'), (2,'E'), (3,'B'), (3,'N'), (3,'D'), (3,'K'),
(3,'W'), (4,'O'), (4,'G'), (4,'N'), (4,'B'), (4,'U'), (4,'C'), (5,'Q'), (5,'H'), (6,'K'),
(6,'Y'), (6,'M'), (6,'A'), (6,'O'), (6,'U'), (6,'J'), (7,'H'), (7,'U'), (7,'M'), (7,'L'),
(8,'B'), (8,'K'), (8,'P'), (9,'Y'), (9,'K'), (10,'Z'), (11,'R'), (12,'X'), (12,'R'),
(12,'O'), (12,'Z'), (4,'C'), (1,'Z'), (4,'S'), (6,'E'), (5,'G'), (4,'C'), (4,'S'), (4,'H'),
(6,'D'), (7,'W'), (3,'U'), (6,'N'), (7,'Y'), (6,'N'), (6,'F'), (4,'C'), (4,'I'), (7,'P'),
(10,'H'), (10,'Z'), (10,'S'), (7,'Z'), (6,'B'), (7,'Z'), (8,'X'), (8,'J'), (8,'P'), (10,'K'),
(8,'K'), (12,'P'), (8,'W'), (10,'M'), (12,'F'), (9,'T'), (9,'D'), (14,'Y'), (12,'P'),
(14,'J'), (13,'D'), (15,'H'), (12,'J'), (6,'H'), (2,'Z'), (8,'G'), (10,'Q'), (6,'D'),
(5,'X'), (9,'T'), (6,'W'), (6,'K'), (10,'W'), (7,'J'), (11,'W'), (12,'V'), (9,'F'), (7,'F'),
(4,'M'), (5,'K'), (12,'G'), (12,'T'), (15,'T'), (13,'W'), (7,'J'), (9,'T'), (10,'U'), (9,'S'),
(10,'L'), (10,'J'), (10,'H'), (11,'H'), (12,'S'), (12,'A'), (14,'L'), (13,'K'), (13,'D'),
(4,'M'), (3,'N'), (4,'F'), (7,'M'), (7,'V'), (5,'R'), (4,'K'), (5,'F'), (7,'G'), (8,'M'),
(4,'X'), (7,'F'), (9,'S'), (7,'N'), (6,'W'), (6,'W'), (5,'S'), (9,'Z'), (10,'I'), (11,'Y'),
(11,'D'), (9,'X'), (7,'G'), (9,'S'), (9,'H'), (9,'T'), (8,'J'), (10,'U'), (9,'F'), (9,'S'),
(7,'D'), (14,'R'), (10,'F'), (7,'E'), (15,'M'), (12,'F'), (5,'C'), (8,'E'), (16,'G'), (11,'V'),
(10,'I'), (12,'I'), (11,'Y'), (12,'I'), (14,'J'), (15,'D'), (19,'J'), (16,'B'), (12,'G'),
(9,'J'), (18,'J'), (18,'C'), (16,'Q'), (18,'P'), (13,'F'), (19,'T'), (15,'J'), (15,'R'),
(15,'Q'), (15,'O'), (11,'A'), (24,'B'), (19,'S'), (22,'I'), (15,'X'), (20,'T'), (15,'E'),
(9,'V'), (8,'H'), (16,'N'), (17,'H')
-- Since the above list was generated by a bunch of random numbers/letters I need to
-- delete the duplicates
;WITH cte AS (
SELECT IDnumber, mut,
row_number() OVER(PARTITION BY IDNumber, mut ORDER BY IDNumber) AS [rn]
FROM @myTable
)
DELETE cte WHERE [rn] > 1
SELECT *
FROM ( SELECT IDnumber, Mut FROM @myTable) AS S
PIVOT
(COUNT(Mut) FOR mut IN ([A],[B],[C],[D],[E],[F],[G],[H],[I],[J],[K],[L],[M],[N],[O],[P],
[Q],[R],[S],[T],[U],[V],[W],[X],[Y],[Z])) AS pvt
Таким образом, вы можете увидеть из сводной таблицы, что минимум IDnumbers
будет 3,5,7 и 12.
Как можно было бы реализовать алгоритм? Мне кажется, что я мог бы найти все комбинации (2^6), которые были бы множествами, а затем определить, какие множества имеют все Muts. Набор с наименьшим числом номеров ID является минимальным набором.
Такая грубая сила может сработать, но это будет ужасно неэффективно. Мой реальный случай не огромен, у меня 43 уникальных Muts
(не девять в примере) и ~ 2000 IDnumbers
, но я думаю, что это заняло бы некоторое время, потому что 2^2000 чертовски большой...
Спасибо!
2 ответа
Вот подход, который вычисляет битовую маску Mut
значения для каждого IDNumber
затем использует рекурсивный CTE для генерации всех возможных комбинаций, которые дополняют набор. Код выводит все возможные IdNumber
комбинации, которые дают конечный результат, за исключением тех, где один или несколько IdNumber
избыточен в комбинации (такой как 1,2,3,4,5,6
в наборе данных образца).
Чтобы преобразовать это для работы с вашими реальными данными, главное отличие состоит в том, что вам почти наверняка понадобится найти другой механизм для назначения битовых значений Mut
ценности. (Я могу немного обмануть здесь и вычислить значения битов, манипулируя десятичным кодом ASCII для каждого Mut
письмо - POWER(2,ASCII(Mut) - 64)
).
DECLARE @myTable TABLE (
IDnumber int,
Mut varchar(1))
INSERT @myTable VALUES
(1,'A'),(1,'B'),(1,'C'),(1,'D'),
(2,'A'),(2,'C'),(2,'D'),
(3,'A'),(3,'B'),(3,'F'),(3,'Z'),
(4,'A'),(4,'B'),(4,'E'),(4,'F'),
(5,'Y'),
(6,'X'),(6,'Z')
-- calculate the target bitmask
DECLARE @target bigint = ( SELECT SUM(POWER(2,ASCII(Mut) - 64))
FROM (SELECT DISTINCT Mut FROM @myTable) AS x
)
;WITH baseCTE
AS
(
--calculate a starting bitmask for each ID
SELECT IDnumber, sum(mutbit) AS bitmask
FROM (SELECT DISTINCT IDnumber, CAST(POWER(2,ASCII(Mut) - 64) AS bigint) AS mutbit FROM @myTable) AS x
GROUP BY IDnumber
)
,recCTE
AS
(
SELECT IDnumber, bitmask, CAST(IdNumber AS varchar(max)) AS trail, 1 AS lev
FROM baseCTE
UNION ALL
SELECT b.IDnumber, b.bitmask | r.bitmask, CAST(CONCAT(r.trail,',',b.IDnumber) AS varchar(max)), r.lev + 1
FROM recCTE AS r
JOIN baseCTE AS b
ON b.IDnumber > r.IDnumber
WHERE b.bitmask | r.bitmask <> r.bitmask --ignore combinations which don't add any new Mut values
)
SELECT trail, lev
FROM recCTE
WHERE bitmask = @target
ORDER BY lev
NB. Битовые операторы SQL Server работают только тогда, когда одно или другое значение имеет целочисленный тип, поэтому это решение ограничено 64 различными Mut
значения (где маска является bigint
) - чтобы заставить его работать сверх этого, вам нужно будет использовать собственный побитовый компаратор (возможно, используя CLR). Тем не менее, поскольку вопрос упоминает, что у вас есть 43 Mut
ценности, это может работать для вас на данный момент.
Я хотел бы, чтобы тестирование проводилось на большем наборе данных, но это соответствует вашим результатам, по крайней мере, для данного набора данных...
DECLARE @myTable TABLE (
IDnumber INT,
Mut VARCHAR(1))
DECLARE @results TABLE (
IDnumber INT)
INSERT @myTable VALUES
(1,'A'),(1,'B'),(1,'C'),(1,'D'),
(2,'A'),(2,'C'),(2,'D'),
(3,'A'),(3,'B'),(3,'F'),(3,'Z'),
(4,'A'),(4,'B'),(4,'E'),(4,'F'),
(5,'Y'),
(6,'X'),(6,'Z')
DECLARE @IDnumber INT
WHILE EXISTS (SELECT 1 FROM @myTable)
BEGIN
WITH MutRank AS
(
-- Find how many IDNumbers are associated with each mut
SELECT Mut,
COUNT(DISTINCT IDnumber) AS IDnumberCnt
FROM @myTable
GROUP BY Mut
), MutRarity AS
(
-- Translate the IDNumberCnt into a weighted rarity so dupes at
-- a IDNumberCnt level reduce their rarity compared to the next level
SELECT Mut,
RANK() OVER (ORDER BY IDnumberCnt DESC) AS MutRarity
FROM MutRank
)
-- Grab the IDNumber that is associated to the most "rare" muts
SELECT @IDnumber = n.IDnumber
FROM (SELECT TOP 1 m.IDnumber,
SUM(MutRarity) AS IDNumberValue
FROM @myTable m
JOIN MutRarity mr
ON m.Mut = mr.Mut
GROUP BY m.IDnumber
ORDER BY IDNumberValue DESC, IDnumber) n
-- Save the number in our results
INSERT @results (IDnumber)
SELECT @IDnumber
-- Purge all records for the "covered" muts and the selected IDNumber
DELETE m2
FROM @myTable m1
JOIN @myTable m2
ON m1.Mut = m2.Mut
AND m1.IDnumber = @IDnumber
END
SELECT *
FROM @results
ORDER BY IDnumber