How to work out packing options...!

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

SQL Server Development (2000)

How to work out packing options...!

Author

Topic

uberman
Posting Yak Master

159 Posts

Posted - 2004-09-27 : 11:26:49

I am having real trouble with the following... I can describe what I want, but can't seem to work out how to get to it.

The following is a **very** simplified version of what I am try to do with 100s' of stores and 1000's of items :-(

If I have a set of stores


declare @stores table(
	store varchar(10),
	item integer,
	quantity integer
)

insert into @stores
select 'A', 1, 1
union
select 'B', 1,1
union
select 'B', 2,1
union
select 'C',1,1
union
select 'C',2,3
union
select 'D', 1, 1

select * from @stores

I need to work out that I need to create the following packing options


declare @boxes table(

	box integer,
	item integer,
	quantity integer
	
)

insert into @boxes
select 1,1,1
union
select 2,1,1
union
select 2,2,1
union
select 3,1,1
union 
select 3,2,3

select * from @boxes -- this is what I need to work out from 
--the stores, that I need 3 boxes with varing items and quantities

and then having worked out what the different options are I need to be able to create the following


declare @result table(
	store varchar(10),
	box integer
)

insert into @result
select 'A', 1
union
select 'B', 2
union
select 'C', 3
union
select 'D', 1

select * from @result

Any help, pointers etc would be gratefully appreciated as my head hurts and I can't work out how to do this in a sufficently generic way that it'll work in any and all cases (not just the example I have posted).

clarkbaker1964
Constraint Violating Yak Guru

428 Posts

Posted - 2004-09-27 : 19:30:53

Are you trying to get every Box permutation for each store?

Surf On Dude!

uberman
Posting Yak Master

159 Posts

Posted - 2004-09-28 : 04:06:07

Er, I **think** so,

From what the stores are recieving you can see there are three distinct boxes, which need to contain different items.

Box 1 : 1 item1 : goes to stores A and D
Box 2 : 1 item1, 1 item2 : goes to store B
Box 3 : 1 item1, 3 item2 : goes to Store C

So I need to work out all the different boxes and then assign them to each store, making sure that Store B **only** gets Box 2 because although they have 1 item1 (which would match Box 1), they also have 1 item2, so only Box 2 is suitable.

(I am actually dealing with boxes, tubes, flat packs and much more across many stores and items and packing options, but if I can get a flying start on this then I should be able to scale it up).

I am still a bit stumped and all I can see is so sort of iterative processing (notice I **didnt** say cursor)

clarkbaker1964
Constraint Violating Yak Guru

428 Posts

Posted - 2004-09-28 : 12:44:12

Lookup Cross Joins in the BOL... This will take two tables and create a join the represents every combination...

quote:
BOL
Using Cross Joins
A cross join that does not have a WHERE clause produces the Cartesian product of the tables involved in the join. The size of a Cartesian product result set is the number of rows in the first table multiplied by the number of rows in the second table. This is an example of a Transact-SQL cross join:

USE pubs
SELECT au_fname, au_lname, pub_name
FROM authors CROSS JOIN publishers
ORDER BY au_lname DESC

The result set contains 184 rows (authors has 23 rows and publishers has 8; 23 multiplied by 8 equals 184).

However, if a WHERE clause is added, the cross join behaves as an inner join. For example, these Transact-SQL queries produce the same result set:

USE pubs
SELECT au_fname, au_lname, pub_name
FROM authors CROSS JOIN publishers
WHERE authors.city = publishers.city
ORDER BY au_lname DESC

-- Or
USE pubs
SELECT au_fname, au_lname, pub_name
FROM authors INNER JOIN publishers
ON authors.city = publishers.city
ORDER BY au_lname DESC

Surf On Dude!

uberman
Posting Yak Master

159 Posts

Posted - 2004-09-29 : 04:30:07

Ah, NO, I dont not require every combination, I need distinct combinations that span multiple rows! (unless I am misunderstanding the suggestion)

Given that I have the following


declare @stores table(
	store varchar(10),
	item varchar(10),
	quantity integer
)

insert into @stores
select 'Store A', 'item 1', 1
union
select 'Store B', 'item 1',1
union
select 'Store B', 'item 2',1
union
select 'Store C','item 1',1
union
select 'Store C','item 2',3
union
select 'Store D', 'item 1', 1
union
select 'Store E', 'item 1',1
union
select 'Store E', 'item 2',1

I need to get to the following


Store A  gets  Box 1
Store B  gets  Box 2
Store C  gets  Box 3
Store D  gets  Box 1
Store E  gets  Box 2

which means I need to work out from the store information that I need to the following boxes


Box    Item   Quantity
---    ----   -------- 
Box 1  item1  1
Box 2  item1  1
Box 2  item2  2
Box 3  item1  1
Box 3  item2  3

I think I may need some more levels of abstraction to get the details, but even using loops I am having trouble working out when I have seen a combination before and have a box to use or when I need to create and assign a new box.

Any other thoughts/suggestions?

byrmol
Shed Building SQL Farmer

1591 Posts

Posted - 2004-09-29 : 07:17:15

Easy on the loops there uberman :-)
We need to do some relational division to get it done.

I used your DDL (thankyou) but CREATEd the table so I could write views against it.


CREATE VIEW DIVBOX
AS
SELECT S.STORE, COUNT(*) AS DIVGROUP
FROM STORES S CROSS JOIN STORES X
WHERE S.ITEM = X.ITEM AND S.QUANTITY = X.QUANTITY
GROUP BY S.STORE

Once we have this, the rest just rolls.


-- BOXES AND THERE CONTENTS
SELECT  DISTINCT DIVGROUP AS BOXID, S.ITEM, S.QUANTITY 
FROM DIVBOX X
INNER JOIN STORES S ON S.STORE = X.STORE 
--STORE AND THE BOX
SELECT  DISTINCT DIVGROUP AS BOXID, S.STORE
FROM DIVBOX X
INNER JOIN STORES S ON S.STORE = X.STORE

The BoxID is not a nice sequence but a simply update would fix that.

DavidM

"Always pre-heat the oven"

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2004-09-29 : 09:02:56

I don't think that works, does it? With the original set of data (no store E) I get the same box for stores B and C.

I think this works, but it looks overcomplicated to me... I'm terrible at division!


CREATE VIEW StoreCount AS
SELECT store, COUNT(*) AS ct
FROM Stores
GROUP BY store
GO

SELECT storeA AS store, MIN(storeB) AS box
FROM (
    SELECT A.store AS storeA, B.store AS storeB, COUNT(*) AS ct
    FROM Stores AS A
    INNER JOIN Stores AS B
      ON A.item = B.item AND A.quantity = B.quantity
      AND A.store >= B.store
    GROUP BY A.store, B.store
  ) AS S
INNER JOIN StoreCount AS AC ON AC.store = S.storeA AND AC.ct = S.ct
INNER JOIN StoreCount AS BC ON BC.store = S.storeB AND BC.ct = S.ct
GROUP BY storeA

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-29 : 09:36:12

how about:


declare @stores table(store varchar(10), item int, quantity int)

insert into @stores
select 'A', 1, 1 union all select 'B', 1,1 union all select 'B', 2,1 
union all select 'C',1,1 union all select 'C',2,3 union all select 'D', 1, 1

--select * from @stores

declare @boxes table(box int, item int, quantity int)

insert into @boxes
select 1,1,1 union all select 2,1,1 union all select 2,2,1 
union all select 3,1,1 union all select 3,2,3

--Select * From @boxes


Select 
	Distinct
	Z.store,
	box = (Select top 1 B.box
		From @stores A, @boxes B
		Where A.store = Z.store
		Group By A.store, B.box
		Having count(distinct A.item) = sum(case when A.item=B.item and A.quantity = B.quantity then 1 else 0 end)
		Order By count(distinct B.item))
From @stores Z

Corey

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2004-09-29 : 10:02:17

quote:

Originally posted by Seventhnight

how about:


[...]
insert into @boxes
select 1,1,1 union all select 2,1,1 union all select 2,2,1 
union all select 3,1,1 union all select 3,2,3
[...]

I think you're supposed to work out what the boxes are from the Stores table!

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-29 : 11:04:19

Oops...

Corey

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-29 : 11:14:50

I continued working on it (just because I didn't pay attention), but I came up with something pretty similar to yours arnold...although I did stay with the table variable.


declare @stores table(
	store varchar(10),
	item integer,
	quantity integer
)

insert into @stores
select 'A', 1, 1
union
select 'B', 1,1
union
select 'B', 2,1
union
select 'C',1,1
union
select 'C',2,3
union
select 'D', 1, 1
union
select 'E', 1,1
union
select 'E', 2,1

--select * from @stores

Select
	Store,
	box = min(box),
	itemCnt
From
	(
	Select A.store, box=B.store, itemCnt = count(*)
	From @stores A
	Inner Join @stores B
	On A.item = B.item and A.quantity = B.quantity
	Group By A.store, b.store
	Having count(*) = (Select count(*) From @stores where store = A.store)
	) Z
Group By store, itemcnt
Order By store

Corey

uberman
Posting Yak Master

159 Posts

Posted - 2004-09-29 : 11:29:09

I am reassured that this isn't actually easy.

Arnolds solution gives me something to work with, and maybe one day I'll comprehend it!

I was hoping to take a solution and run with it to my more complex needs but I am still at the crawling stage, I think I need a bit more guidance, which might also help me understand what is happening more...

I know how each item is to be packed (box, tube etc.), so in the refined example below I need to work out the varying combinations of tubes and boxes and what each store gets, rather than just dealing with boxes (I **could** consider each packing option one at a time, 'box', then 'tube' etc, but that just takes me back into loop world).

I've included Arnolds work for ease of cut n paste as well...

(also, I'll be googlin' around this subject but if anyone has some handy links to help me get my head round this they would be appreciated)

create table stores (
store varchar(10),
item varchar(10),
quantity integer
)
go

create table items(
	item varchar(10),
	pack_in varchar(10),
)


insert into stores
select 'Store A', 'item 1', 1
union
select 'Store A', 'item 3', 1
union
select 'Store B', 'item 1',1
union
select 'Store B', 'item 2',1
union
select 'Store C','item 1',1
union
select 'Store C','item 2',3
union
select 'Store D', 'item 1', 1
union
select 'Store E', 'item 1',1
union
select 'Store E', 'item 2',1
union
select 'Store F', 'item 1', 1
union
select 'Store F', 'item 3', 2
union
select 'Store G', 'item 3', 1


insert into items
select 'item 1', 'box'
union
select 'item 2', 'box'
union
select 'item 3', 'tube'
go


CREATE VIEW StoreCount AS
SELECT store, COUNT(*) AS ct
FROM Stores
GROUP BY store
GO


SELECT storeA AS store, MIN(storeB) AS box
FROM (
    SELECT A.store AS storeA, B.store AS storeB, COUNT(*) AS ct
    FROM Stores AS A
    INNER JOIN Stores AS B
      ON A.item = B.item AND A.quantity = B.quantity
    GROUP BY A.store, B.store
  ) AS S
INNER JOIN StoreCount AS AC ON AC.store = S.storeA AND AC.ct = S.ct
INNER JOIN StoreCount AS BC ON BC.store = S.storeB AND BC.ct = S.ct
GROUP BY storeA


go

drop table stores
drop table items
drop view StoreCount

kselvia
Aged Yak Warrior

526 Posts

Posted - 2004-09-29 : 12:04:03

It's not your exact problem but similar: http://www.dbforums.com/archive/index.php/t-339072.html A recent topic around here in other forms (TSP - Traveling Salesman Problem and other NP-Hard problems)
--Ken
I want to die in my sleep like my grandfather, not screaming in terror like his passengers.

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-29 : 14:00:52

After reading your 'refined' example, I think I am failing to understand your question.

Let me see if I have it all straight.

You have a stores that should get specific items and quantities

These items may be packed in diffent mediums

You are trying to determine the least number of 'package sets' to serve all of the stores

For each 'package set' you need to know what items go into each medium for that set

Do I have it all straight?

Corey

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2004-09-29 : 14:48:34

quote:
Me:
I think this works, but it looks overcomplicated to me...

I'm a little relieved to find that this is essentially the method used by Joe Celko at the end of section 27.3.2 (Set Equality) of SQL For Smarties. It's probably worth comparing the store columns in the main subquery... I'll go back and edit it in.

byrmol
Shed Building SQL Farmer

1591 Posts

Posted - 2004-09-29 : 23:18:06

Nice Arnold.

I thought mine looked too easy and indeed it was. Division is the hardest operation to do in SQL. Harder than recursion to visualise for me at least. Worse, there are a couple of different forms of it..

DavidM

"Always pre-heat the oven"

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2004-09-30 : 03:43:13

Another way to do it with just one join is this:


SELECT storeA AS store, MIN(storeB) AS box
FROM (
    SELECT A.store AS storeA, B.store AS storeB, COUNT(*) AS ct,
      COUNT(CASE WHEN A.item = B.item AND A.quantity = B.quantity THEN 1 END) AS ctMatch
    FROM Stores AS A
    INNER JOIN Stores AS B
      ON A.store >= B.store
    GROUP BY A.store, B.store
  ) AS S
WHERE ct = ctMatch * ctMatch
GROUP BY storeA

But I think I'd put it in the "clever but stupid" category

uberman
Posting Yak Master

159 Posts

Posted - 2004-09-30 : 04:24:57

quote:
You have a stores that should get specific items and quantities

Yes

quote:
These items may be packed in diffent mediums

Yes, each item will go in either a box, a tube, a flat pack etc. So a store will get 1 box and/or 1 tube and/or 1 flat pack etc, and these packs will contain the items in differing quantities.

quote:
You are trying to determine the least number of 'package sets' to serve all of the stores

Kind of. The store will only get 1 box, 1 tube, 1 whatever, I need to know how many different variations of boxes/tubes/etc. that there are...

quote:
For each 'package set' you need to know what items go into each medium for that set

Yes, and then which stores are to get that set (where set is the specific variety of box, tube, etc.)

Sorry this is so complex and I really appreciate all the input. I am now going to look the other examples and see if I can fit it all in with what I have got

kselvia
Aged Yak Warrior

526 Posts

Posted - 2004-09-30 : 11:47:32

I have never heard of SQL Division (assuming you don't mean 4 / 2 = 2) What is it?

--Ken
I want to die in my sleep like my grandfather, not screaming in terror like his passengers.

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2004-09-30 : 13:11:58

quote:
Originally posted by kselvia

I have never heard of SQL Division (assuming you don't mean 4 / 2 = 2) What is it?

Celko to the rescue:

http://www.dbazine.com/celko1.html

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources