セットカバーのクエリ

Question

おはよう、私はSet Cover ProblemのT-SQLクエリを実装したいと思いますが、これをSQLで行う方法についてのヒントは見つかりませんでした。私の場合は

は、私のテーブルには、ちょうど2つの列（IDnumberとMut）を持って、私はすべてのMutの1を取得するためにIDNumberの最小数を見つけたいです。私本当にMutごとに3つのIDnumbersを取得したいが、私はより簡単かもしれないので、私はより良いと思った。

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）を見つけて、どのセットにすべてのマットがあるかを判断できるように思えます。最小数のID番号を有するセットは、最小セットである。

そのような無理な力は働くかもしれませんが、ひどく非効率です。私の実際の世界のケースは巨大ではない、私は43ユニークMuts（例では9）と2000〜IDnumbersを持っていますが、2^2000がかなり大きいので、実行には時間がかかると思っています...

ありがとう！

Answer 1

...私がテストするために、より大きなデータセットをしたいと思いますが、これは与えられた、少なくともデータセットのあなたの結果と一致したがここで、その後、各IDNumberについてMut値のビットマスクを算出し、アプローチです再帰的なCTEを使用して、セットを完成させるすべての可能な組み合わせを生成します。このコードは、IdNumberの可能な組み合わせをすべて出力しますが、組み合わせの中で1つ以上のIdNumberが重複しているものを除きます（サンプルデータセットの1,2,3,4,5,6など）。

これを実際のデータと連動させるには、ビット値をMutの値に割り当てる別のメカニズムを見つける必要があることが大きな違いです。 （私はここでちょっと騙して、それぞれMutの文字の小数ASCIIコードを操作することによってビット値を計算することができます - 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ビット演算子は、1つまたは他の値が整数型である場合にのみ機能します。したがって、この解決策は64個の異なるMut値（マスクはbigintです）に制限されています - それを超えて動作させるには、カスタムのビットコンパレータ（おそらくCLRを使用します）。しかし、という値があることに疑問があるので、今のところあなたのために働くかもしれません。

Answer 2

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