krxrossの雑記帳

2017-02-05

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



完全数でない擬似完全数(ORACLE)


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



■擬似完全数(ORACLE)


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 "擬似完全数"

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/krxross/20170205/1486309401
Connection: close