OraQA

The following is an interesting puzzle posted on Usenet rec-puzzles.org archive:

Partition 1,2,3,…,16 into two equal sets, such that the sums of the numbers in each set are equal, as are the sums of their squares and cubes.

————————–SQL Solution———————————–

SELECT set_name ||' = { ' ||trim(BOTH ','FROM regexp_replace(XMLAgg(
       XMLElement(X,num) ORDER BY num),'<X>|</X><X>|</X>',','))||' } ' AS SET_ITEMS
FROM
(SELECT num, set_name
 FROM
 (SELECT num, value, row_number() OVER (ORDER BY value DESC) rn
  FROM
  (SELECT LEVEL num, LEVEL + power(LEVEL,2) + power(LEVEL,3) value
     FROM dual CONNECT BY LEVEL <=16))
 MODEL
 DIMENSION BY (rn)
 MEASURES (num, value, count(*) OVER ( ) cnt,
 CAST(NULL AS VARCHAR2(2)) set_name,  CAST(NULL AS NUMBER) min_tmp,
 CAST(NULL AS NUMBER  ) set_A_value,  CAST(NULL AS NUMBER) set_B_value,
 CAST(NULL AS NUMBER  )   Set_A_Sum,  CAST(NULL AS NUMBER) Set_B_Sum
 )
 RULES ITERATE (100) UNTIL (iteration_number>= cnt[1])
 (
  Set_A_Sum[1]= CASE iteration_number
                     WHEN 0 THEN 0
       ELSE Set_A_Sum[CV()] END,
  Set_B_Sum[1]= CASE iteration_number
                     WHEN 0 THEN power(10,-10)
       ELSE Set_B_Sum[CV()] END,
  min_tmp[1] = LEAST(sum(Set_A_Sum)[ANY],sum(Set_B_Sum)[ANY]),
  set_name[iteration_number] =   CASE min_tmp[1]
                                      WHEN sum(Set_A_Sum)[ANY] THEN 'A'
                 ELSE 'B' END,
  set_A_value[iteration_number]= CASE min_tmp[1]
                                      WHEN sum(Set_A_Sum)[ANY]
           THEN value[CV()] END,
  set_B_value[iteration_number]= CASE min_tmp[1]
                                      WHEN sum(Set_B_Sum)[ANY]
          THEN value[CV()] END,
  Set_A_Sum[2] = sum(set_A_value)[ANY],
  Set_B_Sum[2] = sum(set_B_value)[ANY]
 )
)
WHERE num IS NOT NULL
GROUP BY SET_NAME;
SET_ITEMS
---------------------------------------------------------
A = { 1,4,6,7,10,11,13,16 }
B = { 2,3,5,8,9,12,14,15 }

Elapsed: 00:00:00.31

Filed under SQL. Follow any responses to this entry through this RSS 2.0 feed.