Home » Other » General » Puzzle n°04 - Evenly share batches of articles into groups ***
Puzzle n°04 - Evenly share batches of articles into groups *** [message #290794] Mon, 31 December 2007 15:57 Go to next message
Michel Cadot
Messages: 59729
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
We have a table of batches containing some articles (see Puzzle n°03).
We now want to aggregate these batches into groups with an as equal as possible number of articles without spliting the batches.
With the following test case:
DROP TABLE batches PURGE;
CREATE TABLE batches (batch_id INTEGER PRIMARY KEY, avail_qty INTEGER NOT NULL);
INSERT INTO batches VALUES (1, 1);
INSERT INTO batches VALUES (2, 1);
INSERT INTO batches VALUES (3, 1);
INSERT INTO batches VALUES (4, 1);
INSERT INTO batches VALUES (5, 1);
INSERT INTO batches VALUES (6, 1);
INSERT INTO batches VALUES (7, 1);
INSERT INTO batches VALUES (8, 2);
INSERT INTO batches VALUES (9, 3);
INSERT INTO batches VALUES (10, 4);
INSERT INTO batches VALUES (11, 4);
INSERT INTO batches VALUES (12, 4);
INSERT INTO batches VALUES (13, 5);
INSERT INTO batches VALUES (14, 5);
INSERT INTO batches VALUES (15, 13);
INSERT INTO batches VALUES (16, 20);
INSERT INTO batches VALUES (17, 20);
COMMIT;

If we want to aggregate into 3, 4 or 5 groups we must have something like (quantities are given and not batch_id):
SQL> DEFINE groups=3
SQL> /
     GROUP QUANTITIES           TOTAL
---------- --------------- ----------
         1 20,4,3,1,1              29
         2 20,4,2,1,1,1            29
         3 13,5,5,4,1              28

SQL> DEFINE groups=4
SQL> /

     GROUP QUANTITIES           TOTAL
---------- --------------- ----------
         1 20,1,1                  22
         2 20,1,1                  22
         3 13,4,3,1                21
         4 5,5,4,4,2,1             21

SQL> DEFINE groups=5
SQL> /

     GROUP QUANTITIES           TOTAL
---------- --------------- ----------
         1 20                      20
         2 20                      20
         3 13,1,1,1                16
         4 5,4,4,1,1               15
         5 5,4,3,2,1               15

The displayed ouput here is just to show the result it is not mandatory, you can display it as you want.

Enjoy!

Regards
Michel


[Updated on: Sat, 20 June 2009 10:12]

Report message to a moderator

Re: Puzzle n°04 - Evenly share batches of articles into groups *** [message #300263 is a reply to message #290794] Thu, 14 February 2008 15:38 Go to previous message
Frank_Zhou
Messages: 5
Registered: February 2008
Location: Braintree , MA
Junior Member
The SQL solution for this puzzles is based on my SQL Query for the "Bin FITING" problem
http://www.jlcomp.demon.co.uk/faq/Bin_Fitting.html
The restriction of this SQL solution is that we must predetermine
the number of groups. So this SQL is not flexiable at all. We can consider it as a prelimary try of this puzzle.

SELECT bucket_name AS GROUPS,
trim(BOTH ','FROM regexp_replace(XMLAgg(
     XMLElement(X,avail_qty) ORDER BY avail_qty desc),'<X>|</X><X>|</X>',',')) AS QUANTITIES, 
SUM(avail_qty) TOTAL        
FROM 
(SELECT batch_id , avail_qty , bucket_name, rn, bucket_1, bucket_2, bucket_3 
 FROM
 (SELECT batch_id , avail_qty , count(*) OVER ( ) counter,
         ROW_NUMBER() OVER (ORDER BY avail_qty  desc) rn FROM batches)
 MODEL 
 DIMENSION BY (rn)
 MEASURES (batch_id , avail_qty , 0 it, counter, 
 CAST(NULL AS NUMBER) bucket_name, CAST(NULL AS NUMBER) min_tmp,
 CAST(NULL AS NUMBER) bucket_1,    CAST(NULL AS NUMBER) bucket_2,  
 CAST(NULL AS NUMBER) bucket_3,    CAST(NULL AS NUMBER) pbucket_1,   
 CAST(NULL AS NUMBER) pbucket_2,   CAST(NULL AS NUMBER) pbucket_3 
 )
 RULES ITERATE (100000)
 UNTIL (ITERATION_NUMBER>= counter[1])
 (
 pbucket_1[2] = CASE WHEN it[ITERATION_NUMBER] = 0 THEN 0 END ,
 pbucket_2[2] = CASE WHEN it[ITERATION_NUMBER] = 0 THEN 0.00001 END ,
 pbucket_3[2] = CASE WHEN it[ITERATION_NUMBER] = 0 THEN 0.00002 END ,
 min_tmp[1] = least(sum(pbucket_1)[ANY], sum(pbucket_2)[ANY], sum(pbucket_3)[ANY]) ,
 bucket_1[ITERATION_NUMBER] = CASE WHEN sum(pbucket_1)[ANY] = min_tmp[1] 
                                   THEN avail_qty [ITERATION_NUMBER]  END,
 bucket_2[ITERATION_NUMBER] = CASE WHEN sum(pbucket_2)[ANY] =  min_tmp[1]
                                   THEN avail_qty [ITERATION_NUMBER]  END, 
 bucket_3[ITERATION_NUMBER] = CASE WHEN sum(pbucket_3)[ANY] =  min_tmp[1] 
                                   THEN avail_qty [ITERATION_NUMBER]  END, 
 bucket_name[ITERATION_NUMBER] =CASE WHEN sum(pbucket_1)[ANY] = min_tmp[1] THEN 1
                                     WHEN sum(pbucket_2)[ANY] = min_tmp[1] THEN 2
                                     WHEN sum(pbucket_3)[ANY] = min_tmp[1] THEN 3  
                                END,                         
pbucket_1[1] = sum(bucket_1)[ANY],
pbucket_2[1] = sum(bucket_2)[ANY],
pbucket_3[1] = sum(bucket_3)[ANY],
it[ITERATION_NUMBER] = ITERATION_NUMBER  
 )                  
) 
WHERE batch_id  IS NOT NULL
GROUP BY bucket_name; 




   GROUPS QUANTITIES      TOTAL                            
--------- --------------- ----------                            
1          20,4,3,1,1      29                            
2          20,4,2,1,1,1    29                            
3          13,5,5,4,1,1    29   
  
SQL> spool off;


[Updated on: Fri, 22 February 2008 13:41] by Moderator

Report message to a moderator

Previous Topic: Oracle on 64 bit
Next Topic: Puzzle n°02 - Hiding names in crossword array **
Goto Forum:
  


Current Time: Thu Nov 20 15:00:19 CST 2014

Total time taken to generate the page: 0.12284 seconds