SQLで組合せ最適化(メモ2)
あまり、整理できていないので
あとで整理する予定だが、列記する
以下SQLServerで確認
■素因数分解
nullやゴミを取り除いていない
WITH Input(iStart, iEnd) AS ( SELECT 1, 10 ), NaturalNumber(num) AS ( SELECT iStart FROM Input UNION ALL SELECT num + 1 FROM NaturalNumber INNER JOIN Input ON NaturalNumber.num + 1 <= Input.iEnd ), prime_factorization (num, value, prime, success) AS ( SELECT CAST(num AS INTEGER) ,CAST(num AS INTEGER) ,CAST(2 AS INTEGER) ,NULL FROM NaturalNumber UNION ALL SELECT num, CASE WHEN (value % prime) = 0 THEN value/prime ELSE value END, CASE WHEN (value % prime) = 0 THEN prime ELSE prime + 1 END, CASE WHEN (value % prime) = 0 THEN 1 ELSE 0 END FROM prime_factorization WHERE value > 1 OR (value = prime) ) SELECT num, (SELECT ',' + CAST(prime AS VARCHAR(MAX)) FROM prime_factorization PF WHERE success = 1 AND PF.num = NN.num FOR XML PATH('') ) AS primes FROM NaturalNumber NN
ごみを取り除くと
WITH Input(iStart, iEnd) AS ( SELECT 1, 50 ), NaturalNumber(num) AS ( SELECT iStart FROM Input UNION ALL SELECT num + 1 FROM NaturalNumber INNER JOIN Input ON NaturalNumber.num + 1 <= Input.iEnd ), primes (num, value, prime, success) AS ( SELECT CAST(num AS INTEGER) ,CAST(num AS INTEGER) ,CAST(2 AS INTEGER) ,NULL FROM NaturalNumber UNION ALL SELECT num, CASE WHEN (value % prime) = 0 THEN value/prime ELSE value END, CASE WHEN (value % prime) = 0 THEN prime ELSE prime + 1 END, CASE WHEN (value % prime) = 0 THEN 1 ELSE 0 END FROM primes WHERE value > 1 OR (value = prime) ), primes2 AS ( SELECT num, (SELECT ',' + CAST(prime AS VARCHAR(MAX)) FROM primes PF WHERE success = 1 AND PF.num = NN.num FOR XML PATH('') ) AS primes, (SELECT count(prime) FROM primes PF WHERE success = 1 AND PF.num = NN.num ) AS cnt FROM NaturalNumber NN ) SELECT num, SUBSTRING(primes, 2, LEN(primes)) FROM primes2 WHERE cnt > 0
■完全数
WITH Input(iStart, iEnd) AS ( SELECT 1, 100 ), NaturalNumber(num) AS ( SELECT iStart FROM Input UNION ALL SELECT num + 1 FROM NaturalNumber INNER JOIN Input ON NaturalNumber.num + 1 <= Input.iEnd ), Primes AS ( SELECT A.num, B.num prime FROM NaturalNumber A JOIN NaturalNumber B ON B.num <= A.num / 2 AND (A.num % B.num) = 0 ) SELECT NN.num "完全数", (SELECT '+' + CAST(PF.prime AS VARCHAR(MAX)) FROM Primes PF WHERE PF.num = NN.num FOR XML PATH('') ) AS "計算式" FROM Primes NN GROUP BY num HAVING SUM(prime) = num
WITH Input(iStart, iEnd) AS ( SELECT 1, 100 ), NaturalNumber(num) AS ( SELECT iStart FROM Input UNION ALL SELECT num + 1 FROM NaturalNumber INNER JOIN Input ON NaturalNumber.num + 1 <= Input.iEnd ), Primes AS ( SELECT A.num, B.num prime FROM NaturalNumber A JOIN NaturalNumber B ON B.num <= A.num / 2 AND (A.num % B.num) = 0 ) SELECT NN.num "不足数", (SELECT '+' + CAST(PF.prime AS VARCHAR(MAX)) FROM Primes PF WHERE PF.num = NN.num FOR XML PATH('') ) AS "計算式" FROM Primes NN GROUP BY num HAVING SUM(prime) < num
■過剰数
完全数と条件の符号が異なるだけである
WITH Input(iStart, iEnd) AS ( SELECT 1, 100 ), NaturalNumber(num) AS ( SELECT iStart FROM Input UNION ALL SELECT num + 1 FROM NaturalNumber INNER JOIN Input ON NaturalNumber.num + 1 <= Input.iEnd ), Primes AS ( SELECT A.num, B.num prime FROM NaturalNumber A JOIN NaturalNumber B ON B.num <= A.num / 2 AND (A.num % B.num) = 0 ) SELECT NN.num "過剰数", (SELECT '+' + CAST(PF.prime AS VARCHAR(MAX)) FROM Primes PF WHERE PF.num = NN.num FOR XML PATH('') ) AS "計算式" FROM Primes NN GROUP BY num HAVING SUM(prime) > num
■完全数でない擬似完全数
擬似完全数の前に、完全数をのぞいたもの
WITH Input(iStart, iEnd) AS ( SELECT 1, 100 ), NaturalNumber(num) AS ( SELECT iStart FROM Input UNION ALL SELECT num + 1 FROM NaturalNumber INNER JOIN Input ON NaturalNumber.num + 1 <= Input.iEnd ), Primes AS ( SELECT A.num, B.num prime FROM NaturalNumber A JOIN NaturalNumber B ON B.num <= A.num / 2 AND (A.num % B.num) = 0 ), Abundants AS ( SELECT NN.num, SUM(prime) - num AS abundant FROM Primes NN GROUP BY num HAVING SUM(prime) > num ), Goods AS ( SELECT P.num, prime, A.abundant FROM Abundants A JOIN Primes P ON P.num = A.num ) ,Knapsack(num, prime, pLst, sumVal) AS ( SELECT num, prime , CAST(prime AS varchar(max)) , prime FROM Goods UNION ALL SELECT a.num , b.prime , CAST(a.pLst + ',' + CAST(b.prime AS varchar(max)) AS varchar(max)) , a.sumVal+b.prime FROM Knapsack a JOIN goods b ON a.num = b.num AND a.prime < b.prime AND a.prime <= b.abundant ) SELECT num "擬似完全数", MAX(pLst) "式" FROM Knapsack WHERE num = sumVal GROUP BY num ORDER BY num
最後のグループ化は無駄に
重複計算してしまうので
なんとかしたい
■擬似完全数
WITH Input(iStart, iEnd) AS ( SELECT 1, 100 ), NaturalNumber(num) AS ( SELECT iStart FROM Input UNION ALL SELECT num + 1 FROM NaturalNumber INNER JOIN Input ON NaturalNumber.num + 1 <= Input.iEnd ), Primes AS ( SELECT A.num, B.num prime FROM NaturalNumber A JOIN NaturalNumber B ON B.num <= A.num / 2 AND (A.num % B.num) = 0 ), Parfects AS ( SELECT NN.num FROM Primes NN GROUP BY num HAVING SUM(prime) = num ), Abundants AS ( SELECT num, SUM(prime) - num AS abundant FROM Primes GROUP BY num HAVING SUM(prime) > num ), Goods AS ( SELECT P.num, prime, A.abundant FROM Abundants A JOIN Primes P ON P.num = A.num ), Knapsack(num, prime, pLst, sumVal) AS ( SELECT num, prime , CAST(prime AS varchar(max)) , prime FROM Goods UNION ALL SELECT a.num , b.prime , CAST(a.pLst + '+' + CAST(b.prime AS varchar(max)) AS varchar(max)) , a.sumVal+b.prime FROM Knapsack a JOIN goods b ON a.num = b.num AND a.prime < b.prime AND a.prime <= b.abundant ) SELECT num "擬似完全数", MAX(pLst) "式" FROM Knapsack WHERE num = sumVal GROUP BY num UNION SELECT PF.num, (SELECT '+' + CAST(PR.prime AS VARCHAR(MAX)) FROM Primes PR WHERE PF.num = PR.num FOR XML PATH('') ) AS "計算式" FROM Parfects PF ORDER BY num
■ORACLEでは、上がそのまま動かない
テーブルを作成しながら作成を試みる
create table natural_numbers as WITH Input(iStart, iEnd) AS ( SELECT 0, 9 FROM DUAL ), numb(num) AS ( SELECT iStart FROM Input UNION ALL SELECT num + 1 FROM numb INNER JOIN Input ON numb.num + 1 <= Input.iEnd ) SELECT TO_NUMBER(k.num || l.num || m.num || n.num) num FROM numb k, numb l, numb m, numb n ORDER BY k.num, l.num, m.num, n.num
WITH NaturalNumber AS ( SELECT num FROM Natural_Numbers WHERE num <= 100 ), Primes AS ( SELECT A.num, B.num prime FROM NaturalNumber A JOIN NaturalNumber B ON B.num <= A.num / 2 AND MOD(A.num, B.num) = 0 ), Parfects AS ( SELECT NN.num FROM Primes NN GROUP BY num HAVING SUM(prime) = num ), Abundants AS ( SELECT num, SUM(prime) - num AS abundant FROM Primes GROUP BY num HAVING SUM(prime) > num ), Goods AS ( SELECT P.num, prime, A.abundant FROM Abundants A JOIN Primes P ON P.num = A.num ), Knapsack(num, prime, pLst, sumVal) AS ( SELECT num, prime , TO_CHAR(prime) , prime FROM Goods UNION ALL SELECT a.num , b.prime , a.pLst || '+' || TO_CHAR(b.prime) , a.sumVal+b.prime FROM Knapsack a JOIN goods b ON a.num = b.num AND a.prime < b.prime AND a.prime <= b.abundant ) SELECT num "擬似完全数", MAX(pLst) "式" FROM Knapsack WHERE num = sumVal GROUP BY num ORDER BY num
WITH NaturalNumber AS ( SELECT num FROM Natural_Numbers WHERE num BETWEEN 1 AND 200 ), Primes AS ( SELECT A.num, B.num prime FROM NaturalNumber A JOIN NaturalNumber B ON B.num <= A.num / 2 AND MOD(A.num, B.num) = 0 ), Parfects AS ( SELECT NN.num FROM Primes NN GROUP BY num HAVING SUM(prime) = num ), Abundants AS ( SELECT num, SUM(prime) - num AS abundant FROM Primes GROUP BY num HAVING SUM(prime) > num ), Goods AS ( SELECT P.num, prime, A.abundant FROM Abundants A JOIN Primes P ON P.num = A.num ), Knapsack(num, prime, pLst, sumVal) AS ( SELECT num, prime , TO_CHAR(prime) , prime FROM Goods UNION ALL SELECT a.num , b.prime , a.pLst || '+' || TO_CHAR(b.prime) , a.sumVal+b.prime FROM Knapsack a JOIN goods b ON a.num = b.num AND a.prime < b.prime AND a.prime <= b.abundant ) SELECT num "擬似完全数", MAX(pLst) "式" FROM Knapsack WHERE num = sumVal GROUP BY num UNION SELECT PF.num, (SELECT LISTAGG(PR.prime, '+') WITHIN GROUP (order by PR.prime) FROM Primes PR WHERE PF.num = PR.num) FROM Parfects PF ORDER BY "擬似完全数"