help with matching data required

[Norman Fritag]

Hi there
I need some help, to matching data!
eg: out of 20 elements: eg (10,2,4 17,24,5,30, 40, 50, 100, 23, 35, 200,
3501, 201, 245, 323,2000, 33, 44,265,etc)
I would want to know which of these elements eg: make up the sum 275??
in this example the combination: 245,30 = 275 ; 200,24,50 =275;
200,30,40,5 = 275 and so forth
Would I have to use via code function and or could I us as well sql?

any hints are much appreciated

Regards

Norman

 

[Marshall Barton]

I need some help, to matching data!
eg: out of 20 elements: eg (10,2,4 17,24,5,30, 40, 50, 100, 23, 35, 200,
3501, 201, 245, 323,2000, 33, 44,265,etc)
I would want to know which of these elements eg: make up the sum 275??
in this example the combination: 245,30 = 275 ; 200,24,50 =275;
200,30,40,5 = 275 and so forth
Would I have to use via code function and or could I us as well sql?

What a bizzare question.

Since I believe that's an inherently recursive problem, I
don't see how that can be done using SQL.

 

[Duane Hookom]

Bizarre yes but possibly solvable with SQL. Assuming a smaller example with
single field tables of

Table Field
======== ======
tblWidth Wdth
tblLength Lngth
tblHeight Hght

add values to the tables and attempt to find a "box" where the volume = 275.

SELECT Lngth, Wdth, Hght, [Lngth]*[wdth]*[Hght] AS Volume
FROM tblLength, tblWidth, tblHeight
WHERE [Lngth]*[wdth]*[Hght]= 275;

Selecting any combination of Lngth * Wdth = 275 or Lngth * Hght =275 or just
Lngth = 275 would suggest you would need to add the value 1 to each table.
This could be done with a union query if you didn't want to actually enter 1
into each table.

If you had only one table of value, you would need to add the same table
into your query as many times as there are records in the table. You could
write code to create the select statement.

It should all be possible but I am having trouble identifying a real world
situation that would require this. (Maybe this is a homework assignment and
we just helped a student).

 

[Tom Ellison]

Dear Norman:

This is actually a bit of a classic query problem. There are some things I
must know to give a solution:

1. From the set of 20 (or however many) elements, can I pick the same
number more than once?

2. If I cannot pick a number from the table more times than it appears,
will any numbers appear more than once?

3. Is there a limit to the number of elements in a combination?

These affect the solution considerably, expecially that last one. There is
a union of cross-products involved in a very simple solution, but that would
run, like, forever if you want sets that have a huge number of results.

I did this once in preparing packages for shipping. We had items to ship
that weigh 1 - 15 pounds, all going to the same destination. How do you
pack boxes of 55 pounds from that? This minimizes shipping costs. A single
55 pound package costs less than a 25 and a 30 pound package.

Like I said, it's a classic problem. Is yours based on something like this?

Tom Ellison

 

[Tom Ellison]

Dear Norman:

I've gone ahead with a partial solution, based on some assumptions. Here's
a query:

SELECT N1.Numbers AS Nu1, N2.Numbers AS Nu2, N3.Numbers as Nu3, N4.Numbers
AS Nu4
FROM Numbs N1, Numbs N2, Numbs N3, Numbs N4
WHERE N1.ID <> N2.ID
AND N1.ID <> N3.ID
AND N1.ID <> N4.ID
AND N2.ID <> N3.ID
AND N2.ID <> N4.ID
AND N3.ID <> N4.ID
AND N1.Numbers <= N2.Numbers
AND N2.Numbers <= N3.Numbers
AND N3.Numbers <= N4.Numbers
AND N1.Numbers + N2.Numbers + N3.Numbers + N4.Numbers = 275

This gives the following results:

Query1 Nu1 Nu2 Nu3 Nu4
5 30 40 200
2 33 40 200
2 23 50 200
10 30 35 200
17 23 35 200
10 24 40 201
4 30 40 201
17 24 33 201
2 4 24 245
2 5 23 245


The whole thing, so far, is:

SELECT N1.Numbers AS Nu1, N2.Numbers AS Nu2, NULL AS Nu3, NULL AS Nu4
FROM Numbs N1, Numbs N2
WHERE N1.ID <> N2.ID
AND N1.Numbers <= N2.Numbers
AND N1.Numbers + N2.Numbers = 275

UNION ALL

SELECT N1.Numbers AS Nu1, N2.Numbers AS Nu2, N3.Numbers as Nu3, NULL AS Nu4
FROM Numbs N1, Numbs N2, Numbs N3
WHERE N1.ID <> N2.ID
AND N1.ID <> N3.ID
AND N2.ID <> N3.ID
AND N1.Numbers <= N2.Numbers
AND N2.Numbers <= N3.Numbers
AND N1.Numbers + N2.Numbers + N3.Numbers = 275

This is simply a set of 4 queries giving all the results adding together 2,
3, and 4 values. Except it won't run. Sigh! Each of the queries
individually will run. The first two together run. Here's what they give:

Added Nu1 Nu2 Nu3 Nu4
30 245


10 265


35 40 200

24 50 201

30 44 201





Now, the table Numbs contains 2 columns, Numbers and ID. I put your numbers
in it and let the Autonumber ID take care of itself.

The thing with the IDs is to prevent any value from being used twice, unless
it's in the table twice. Unlike many of my discussions before, when a row
HAS an identity (such as when it cannot be used twice in the crossproduct
here) but does NOT have a natural key, then an identity can be
indispensable. Well, not indispensable. But pretty handy, and this is a
case for it.

Now, when I put the 3 queries together in one big UNION ALL query, it fails.
It gives:

Data type mismatch in criteria expression. (Error 3464)

This is obviously a false indication. How could the queries work
independently without error, but give this error when placed in UNION? I
don't see how!

The criteria like:

N1.Numbers <= N2.Numbers
AND N2.Numbers <= N3.Numbers

prevent the sum from showing up in reverse. 6 + 3 = 9 and 3 + 6 = 9. It's
probably not useful to show both.

Somehow, I couldn't get this to match one of your sample results: 200 + 24
+ 50 = 275. I cannot explain this one. : )

I've done this very successfully in MSDE. It doesn't seem to be working out
well in Jet. In addition to not running the UNION as explained above, it
also won't let me save the query. It gives:

"Record is deleted"

when I try to save the query. Nuts! Maybe everyone can see why I always
perform difficult tasks in MSDE. You can't save a query because a record is
deleted! Forget it!

When I hear back about details I asked for, maybe we can put together
something useful.

Tom Ellison

 

[Tom Ellison]

I see the query results have been thoroughly mangled in my post. It's going
to take a bit of extra effort to interpret them. Sorry. They were very
neat when I posted them.

If you can look at them in HTML (assuming they are still posted that way) it
looks very nice.

Tom Ellison

 

[Duane Hookom]

Oops I see I was multiplying while the original question pertained to
adding. Please Replace([SQL QUERY],"*","+")

--
Duane Hookom
MS Access MVP
--

Bizarre yes but possibly solvable with SQL. Assuming a smaller example
with single field tables of

Table Field
======== ======
tblWidth Wdth
tblLength Lngth
tblHeight Hght

add values to the tables and attempt to find a "box" where the volume =
275.

SELECT Lngth, Wdth, Hght, [Lngth]*[wdth]*[Hght] AS Volume
FROM tblLength, tblWidth, tblHeight
WHERE [Lngth]*[wdth]*[Hght]= 275;

Selecting any combination of Lngth * Wdth = 275 or Lngth * Hght =275 or
just Lngth = 275 would suggest you would need to add the value 1 to each
table. This could be done with a union query if you didn't want to
actually enter 1 into each table.

If you had only one table of value, you would need to add the same table
into your query as many times as there are records in the table. You could
write code to create the select statement.

It should all be possible but I am having trouble identifying a real world
situation that would require this. (Maybe this is a homework assignment
and we just helped a student).

 

[Marshall Barton]

Bizarre yes but possibly solvable with SQL. Assuming a smaller example with
single field tables of

Table Field
======== ======
tblWidth Wdth
tblLength Lngth
tblHeight Hght

add values to the tables and attempt to find a "box" where the volume = 275.

SELECT Lngth, Wdth, Hght, [Lngth]*[wdth]*[Hght] AS Volume
FROM tblLength, tblWidth, tblHeight
WHERE [Lngth]*[wdth]*[Hght]= 275;

Selecting any combination of Lngth * Wdth = 275 or Lngth * Hght =275 or just
Lngth = 275 would suggest you would need to add the value 1 to each table.
This could be done with a union query if you didn't want to actually enter 1
into each table.

If you had only one table of value, you would need to add the same table
into your query as many times as there are records in the table. You could
write code to create the select statement.

It should all be possible but I am having trouble identifying a real world
situation that would require this. (Maybe this is a homework assignment and
we just helped a student).

Duane,
This approach would require a different query for each list
size. I.e. the query must know how many records are in the
table so you can use a matching number of joins.

In the case of Norman's example, there would be a few more
than 104,857,600,000,000,000,000,000,000 records, which, at
best, would take a while to process ;-)

 

[Duane Hookom]

I was only speaking theoretically (I learned that from Tom ;-). I stated
"You could write code to create the select statement" which would handle
multiple lists/values. I hadn't done the math on the number of combinations
but it ran fairly quickly with 5-6 records! Them Cartesians know how to work
fast.

--
Duane Hookom
MS Access MVP
--

Bizarre yes but possibly solvable with SQL. Assuming a smaller example
with
single field tables of

Table Field
======== ======
tblWidth Wdth
tblLength Lngth
tblHeight Hght

add values to the tables and attempt to find a "box" where the volume =
275.

SELECT Lngth, Wdth, Hght, [Lngth]*[wdth]*[Hght] AS Volume
FROM tblLength, tblWidth, tblHeight
WHERE [Lngth]*[wdth]*[Hght]= 275;

Selecting any combination of Lngth * Wdth = 275 or Lngth * Hght =275 or
just
Lngth = 275 would suggest you would need to add the value 1 to each table.
This could be done with a union query if you didn't want to actually enter
1
into each table.

If you had only one table of value, you would need to add the same table
into your query as many times as there are records in the table. You could
write code to create the select statement.

It should all be possible but I am having trouble identifying a real world
situation that would require this. (Maybe this is a homework assignment
and
we just helped a student).

Duane,
This approach would require a different query for each list
size. I.e. the query must know how many records are in the
table so you can use a matching number of joins.

In the case of Norman's example, there would be a few more
than 104,857,600,000,000,000,000,000,000 records, which, at
best, would take a while to process ;-)

 

[Tom Ellison]

Duane:

"speaking theoretically"? Is that a good thing? : )

I try to employ the fastest Cartesians I can find. I'm not telling you from
where they come.

There are ways to improve performance.

If the sum is to be N, and you're finding the combinations of 6 values that
add up to the target, add up the 5 smallest values. Subtract that from N
and filter out all values larger than that. That reduces the Cartesians
quite a bit in some cases. Killing Cartesians we can call it. Well,
actually, we just deport them. Do this in subqueries in the FROM clause,
rather than filtering them out AFTER they have been created. Faster.

Simply, if your sum is to be 300, you don't need to consider any number
larger than 300 (assuming there can be no negative values). I haven't built
that into this query yet. Had enough trouble with Jet as it is. Worst I've
ever seen!

I had a similar thread I answered a few years ago that had 10,000 values in
the table. The number of combinations were staggering. We were picking
football teams. I believe it came to 10^XXXX, that is, a 4 digit number.
We computed that computers don't last long enough to solve the problem. It
took only minutes to find a team of 6 players, though. We managed to find a
few ways to reduce the combinations, down to a 3 digit exponent. Not very
helpful in that set of circumstances, but it was a large improvement.
Perhaps my grandchildren will live to see this problem solved.

Tom Ellison

I was only speaking theoretically (I learned that from Tom ;-). I stated
"You could write code to create the select statement" which would handle
multiple lists/values. I hadn't done the math on the number of combinations
but it ran fairly quickly with 5-6 records! Them Cartesians know how to
work fast.

--
Duane Hookom
MS Access MVP
--

Bizarre yes but possibly solvable with SQL. Assuming a smaller example
with
single field tables of

Table Field
======== ======
tblWidth Wdth
tblLength Lngth
tblHeight Hght

add values to the tables and attempt to find a "box" where the volume =
275.

SELECT Lngth, Wdth, Hght, [Lngth]*[wdth]*[Hght] AS Volume
FROM tblLength, tblWidth, tblHeight
WHERE [Lngth]*[wdth]*[Hght]= 275;

Selecting any combination of Lngth * Wdth = 275 or Lngth * Hght =275 or
just
Lngth = 275 would suggest you would need to add the value 1 to each
table.
This could be done with a union query if you didn't want to actually
enter 1
into each table.

If you had only one table of value, you would need to add the same table
into your query as many times as there are records in the table. You
could
write code to create the select statement.

It should all be possible but I am having trouble identifying a real
world
situation that would require this. (Maybe this is a homework assignment
and
we just helped a student).

Duane,
This approach would require a different query for each list
size. I.e. the query must know how many records are in the
table so you can use a matching number of joins.

In the case of Norman's example, there would be a few more
than 104,857,600,000,000,000,000,000,000 records, which, at
best, would take a while to process ;-)

 

[Duane Hookom]

Marsh, I told you Tom was the chief theorist in the query realm!

--
Duane Hookom
MS Access MVP
--

Duane:

"speaking theoretically"? Is that a good thing? : )

I try to employ the fastest Cartesians I can find. I'm not telling you
from where they come.

There are ways to improve performance.

If the sum is to be N, and you're finding the combinations of 6 values
that add up to the target, add up the 5 smallest values. Subtract that
from N and filter out all values larger than that. That reduces the
Cartesians quite a bit in some cases. Killing Cartesians we can call it.
Well, actually, we just deport them. Do this in subqueries in the FROM
clause, rather than filtering them out AFTER they have been created.
Faster.

Simply, if your sum is to be 300, you don't need to consider any number
larger than 300 (assuming there can be no negative values). I haven't
built that into this query yet. Had enough trouble with Jet as it is.
Worst I've ever seen!

I had a similar thread I answered a few years ago that had 10,000 values
in the table. The number of combinations were staggering. We were
picking football teams. I believe it came to 10^XXXX, that is, a 4 digit
number. We computed that computers don't last long enough to solve the
problem. It took only minutes to find a team of 6 players, though. We
managed to find a few ways to reduce the combinations, down to a 3 digit
exponent. Not very helpful in that set of circumstances, but it was a
large improvement. Perhaps my grandchildren will live to see this problem
solved.

Tom Ellison

I was only speaking theoretically (I learned that from Tom ;-). I stated
"You could write code to create the select statement" which would handle
multiple lists/values. I hadn't done the math on the number of
combinations but it ran fairly quickly with 5-6 records! Them Cartesians
know how to work fast.

--
Duane Hookom
MS Access MVP
--

Duane Hookom wrote:

Bizarre yes but possibly solvable with SQL. Assuming a smaller example
with
single field tables of

Table Field
======== ======
tblWidth Wdth
tblLength Lngth
tblHeight Hght

add values to the tables and attempt to find a "box" where the volume =
275.

SELECT Lngth, Wdth, Hght, [Lngth]*[wdth]*[Hght] AS Volume
FROM tblLength, tblWidth, tblHeight
WHERE [Lngth]*[wdth]*[Hght]= 275;

Selecting any combination of Lngth * Wdth = 275 or Lngth * Hght =275 or
just
Lngth = 275 would suggest you would need to add the value 1 to each
table.
This could be done with a union query if you didn't want to actually
enter 1
into each table.

If you had only one table of value, you would need to add the same table
into your query as many times as there are records in the table. You
could
write code to create the select statement.

It should all be possible but I am having trouble identifying a real
world
situation that would require this. (Maybe this is a homework assignment
and
we just helped a student).


Duane,
This approach would require a different query for each list
size. I.e. the query must know how many records are in the
table so you can use a matching number of joins.

In the case of Norman's example, there would be a few more
than 104,857,600,000,000,000,000,000,000 records, which, at
best, would take a while to process ;-)

 

[Tom Ellison]

Well, I just keep replying to my own posts.

I've had some fun, creating the sums up to 6 values per sum:

Nu1 Nu2 Nu3 Nu4 Nu5 Nu6
17 33 35 40 50 100
17 24 40 44 50 100
23 33 35 40 44 100
2 4 5 24 40 200
2 4 10 24 35 200
2 5 10 23 35 200
4 5 10 23 33 200
2 5 10 17 40 201
2 4 5 23 40 201
2 4 10 23 35 201
2 5 10 24 33 201
2 4 5 30 33 201


The query for this:

SELECT N1.Numbers AS Nu1, N2.Numbers AS Nu2, N3.Numbers as Nu3,
N4.Numbers AS Nu4, N5.Numbers AS Nu5, N6.Numbers AS Nu6
FROM Numbs N1, Numbs N2, Numbs N3, Numbs N4, Numbs N5, Numbs N6
WHERE N1.ID <> N2.ID
AND N1.ID <> N3.ID
AND N1.ID <> N4.ID
AND N1.ID <> N5.ID
AND N1.ID <> N6.ID
AND N2.ID <> N3.ID
AND N2.ID <> N4.ID
AND N2.ID <> N5.ID
AND N2.ID <> N6.ID
AND N3.ID <> N4.ID
AND N3.ID <> N5.ID
AND N3.ID <> N6.ID
AND N4.ID <> N5.ID
AND N4.ID <> N6.ID
AND N5.ID <> N6.ID
AND N1.Numbers <= N2.Numbers
AND N2.Numbers <= N3.Numbers
AND N3.Numbers <= N4.Numbers
AND N4.Numbers <= N5.Numbers
AND N5.Numbers <= N6.Numbers
AND N1.Numbers + N2.Numbers + N3.Numbers + N4.Numbers + N5.Numbers +
N6.Numbers = 275

This is the first query that doesn't run almost instantaneously. It talks
2-3 seconds. It will get worse from here.

To really see slow, add a few dozen rows to the table. That ought to do it!

I'll bet we could put the UNION in another query and it would all work
together. But there are a number of variations on this dependent on what is
wanted in terms of the questions I asked earlier. If I can force myself,
I'll quit writing these and find out what is really wanted before I "finish
solving" a problem that may not be the right problem to start.

Tom Ellison

 

[Tom Ellison]

The question now is, where is Norman Fritag? You remember Norman, don't
you?

I'm here having all this fun, and he's not around!

Hello, Norman? Are you waiting for things to quiet down?

I put in about 20 more numbers and ran it again. There are now thousands of
combinations of 6 numbers that add up to 275. It takes most of a minute to
find them.

I think I'm through playing now. Not completely certain. It's actually fun
to play with. I guess that makes me rather perverse. Playing with lists of
numbers!

Hey, Norman, maybe you have the right idea, to stay away from me! : )

Tom Ellison

 

[Marshall Barton]

Marsh, I told you Tom was the chief theorist in the query realm!

You got that right Duane!

Are your fast Cartesians in any way related to the Artesians
of great beer fame? ;-)

I still say this is a partitions problem that is most
naturally solved by a recursive procedure and our version of
SQL doesn't do that.

 

[Marshall Barton]

The question now is, where is Norman Fritag? You remember Norman, don't
you?

I'm here having all this fun, and he's not around!

Hello, Norman? Are you waiting for things to quiet down?

I put in about 20 more numbers and ran it again. There are now thousands of
combinations of 6 numbers that add up to 275. It takes most of a minute to
find them.

I think I'm through playing now. Not completely certain. It's actually fun
to play with. I guess that makes me rather perverse. Playing with lists of
numbers!

Tom,

I don't know if perverse is really applicable, strange
maybe, different for sure ;-)

If that's your idea of "fun", you might want to try solving
some more difficult problems. How about coming up with a
four line proof of Fermat's Last Theorem ;-))

 

[Tom Ellison]

Dear Marsh:

Response inline, below.

Tom Ellison

You got that right Duane!

Are your fast Cartesians in any way related to the Artesians
of great beer fame? ;-)
Well?


I still say this is a partitions problem that is most
naturally solved by a recursive procedure and our version of
SQL doesn't do that.

Exactly. At least we have unions!

A hierarchical self-referencing table with an indefinite number of levels is
another "un-doable" query for this same reason. However, I have always
found it both possible and useful to define a finite set of "levels" in
advance. Once you know the maximum possible number of levels, you can
generate the query code for a giant UNION.

There's really a lot to a study of how all this can be made to work. A lot
of the kind of "theory" you guys accuse me of doing, but it fnally works out
in a functioning design. Not JUST theory, OK?

 

[Tom Ellison]

Dear Marsh:

I accept your challenge, provided I be allowed to write it in SQL!

Just for starters, could I be allowed to have 5 lines?

Tom Ellison

 

[Marshall Barton]

Dear Marsh:

Response inline, below.


Well?

I don't remember Tom. I thought it was Springs, but maybe
they got married and are using Well-Springs now ;-)

Exactly. At least we have unions!

A hierarchical self-referencing table with an indefinite number of levels is
another "un-doable" query for this same reason. However, I have always
found it both possible and useful to define a finite set of "levels" in
advance. Once you know the maximum possible number of levels, you can
generate the query code for a giant UNION.

There's really a lot to a study of how all this can be made to work. A lot
of the kind of "theory" you guys accuse me of doing, but it fnally works out
in a functioning design. Not JUST theory, OK?

I am more of a code whacker and naturally go for the code,
so I appreciate seeing solutions from a different realm.

 

[Marshall Barton]

Of course you can use SQL ;-)

Take a many lines as you like, I guess if you're using SQL,
it would be four queries ;-))