Home » Other » General » Puzzle n°04 - Evenly share batches of articles into groups ***
Puzzle n°04 - Evenly share batches of articles into groups *** Mon, 31 December 2007 15:57
 Michel Cadot Messages: 67887Registered: March 2007 Location: Nanterre, France, http://... Senior MemberAccount 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
 Frank_Zhou Messages: 5Registered: 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: Tue Jun 22 20:37:02 CDT 2021