Home » Other » Training & Certification » selecting a best combination of numbers from a list of numbers
selecting a best combination of numbers from a list of numbers [message #281617] Sun, 18 November 2007 17:20 Go to next message
dews
Messages: 7
Registered: November 2007
Junior Member
I would be greatful if anyone can help me in the following

I want to extract 3 or lesser numbers whose sum is 25 (if not then nearest to 25) from a varying list of numbers.

As an example following is the list of numbers
10, 12, 4 , 5 (In some case i will have only one number in the list and in some other case it might be upto 10)

I should get a list of three numbers as follows
10, 12

[Updated on: Sun, 18 November 2007 23:01]

Report message to a moderator

Re: selecting a best combination of numbers from a list of numbers [message #281618 is a reply to message #281617] Sun, 18 November 2007 17:52 Go to previous messageGo to next message
BlackSwan
Messages: 25046
Registered: January 2009
Location: SoCal
Senior Member
What does this question have to do with Oracle?

Do you realize that the homework forum is near the bottom of the page?
Re: selecting a best combination of numbers from a list of numbers [message #281619 is a reply to message #281618] Sun, 18 November 2007 18:03 Go to previous messageGo to next message
dews
Messages: 7
Registered: November 2007
Junior Member
Hi,

Thanks for giving an immediate response.

I am looking forward for a PL/SQL program for doing this. I have lot of products for sale in different category.

I need to rollout an offer for customers where customers can pick up three or lesser products upto USD 25 from each category.

example
product category name price
book-1 books&periodicals 10
book-2 " 3
book-3 " 4
book-4 " 12

similarly different products under different category.

I am looking for your help in selecting three or lesser products whose sum is 25 from this products details table.

[Updated on: Sun, 18 November 2007 23:01]

Report message to a moderator

Re: selecting a best combination of numbers from a list of numbers [message #281620 is a reply to message #281617] Sun, 18 November 2007 18:11 Go to previous messageGo to next message
BlackSwan
Messages: 25046
Registered: January 2009
Location: SoCal
Senior Member
http://www.orafaq.com/forum/t/88153/0/
Please read & FOLLOW posting guidelines as stated in URL above.



Re: selecting a best combination of numbers from a list of numbers [message #281621 is a reply to message #281620] Sun, 18 November 2007 18:20 Go to previous messageGo to next message
dews
Messages: 7
Registered: November 2007
Junior Member
Hi,

Once again thanks. This is the first time i am posting in this forum. But i used to read most of the posts of other members to learn more abot pl/sql programming.

I will follow the guidelines while submitting new posts.

Re: selecting a best combination of numbers from a list of numbers [message #281623 is a reply to message #281617] Sun, 18 November 2007 18:36 Go to previous messageGo to next message
dews
Messages: 7
Registered: November 2007
Junior Member
For better clarification i described my problem as follows (Please ignore my previous posts with the same subject). Can anyone help me to resolve this?

I have a table product_details which contains the columns category, product and price. Some sample records are as follows.

"books&periodicals","book-1",10
"books&periodicals","book-2",4
"books&periodicals","book-3",5
"books&periodicals","book-4",12
"Kitchen Utensils","Frying Pan",25
"Kitchen Utensils","Knife set",10
"Electricals","Iron Box",10
"Electricals","Bulb",12

I am trying to write a pl/sql block to retrieve a result set which satisfies the following criteria

1. From each category products up to a total of price 25. If not a better combination of products whose total value comes closer to 25
2. Number of products from each category should not exceed 3
3. Number of products in each category can vary.

After applying these critearia, result set for the given sample would be as follows

"books&periodicals","book-1",10
"books&periodicals","book-4",12
"Kitchen Utensils","Frying Pan",25
"Electricals","Iron Box",10
"Electricals","Bulb",12

Since there are indefinite products in each category, i am struggling to write a code for this.

[Updated on: Sun, 18 November 2007 23:00]

Report message to a moderator

Re: selecting a best combination of numbers from a list of numbers [message #281625 is a reply to message #281623] Sun, 18 November 2007 19:19 Go to previous messageGo to next message
rleishman
Messages: 3724
Registered: October 2005
Location: Melbourne, Australia
Senior Member
I think you actually have two problems:
1) Think of an algorithm to get what you want.
2) Code that algorithm in PL/SQL

The second bit is easy for anyone with a bit of PL/SQL experience, providing you have already solved the first bit.

There are a number of quick-and-dirty ways that an amateur mathematician/logician like myself could solve this, but inevitably it would be hokey and non-scalable (so I'm not even going to try).

This looks a bit like a problem that I read about in a popular science book, although that was a logistics problem where you had to source N units of a certain product from any combination of known warehouses with known inventories of the product and known transport costs, and minimise the cost. There is a mathematical way to solve these types of problem, but its too complex to describe here, and besides - I don't even remember how to do it.

Of course, it also has similarities to the "Travelling Salesman Problem", for which there is no solution other than "brute force". If that were the case, then you would be justified in writing a simple PL/SQL routine that caculated EVERY combination of products, sorted them by cost, and discarded the ones over the threshold. Whoever is asking you to do this should be made to understand that this type of solution scales exponentially and would almost certainly bring your server to its knees.

I suggest you consult a mathematician in order to obtain an algorithm, then worry about coding it.

Ross Leishman
Re: selecting a best combination of numbers from a list of numbers [message #281656 is a reply to message #281625] Sun, 18 November 2007 23:46 Go to previous messageGo to next message
sundha
Messages: 6
Registered: November 2007
Junior Member
Hi,

You can use the following query for your requirement

SELECT * FROM
(SELECT categories,product,price,SUM(price) OVER (PARTITION BY categories ORDER BY price ROWS 2 PRECEDING ) total_price FROM
(SELECT categories,product,price,row_number() OVER (PARTITION BY categories ORDER BY price) row_num
FROM product_details
WHERE price <26)
WHERE row_num < 4)
WHERE total_price < 26

If you have any problem with this query kindly let me know

Sundari
Re: selecting a best combination of numbers from a list of numbers [message #281680 is a reply to message #281617] Mon, 19 November 2007 00:35 Go to previous messageGo to next message
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
Senior Member

Hi Sundari ,
(Sundhari = Beautiful Lady in Indian Languages Neutral )
Welcome to the Forum .
And you have tried a good Attempt even .Keep going !!!

But you Query may not work well when there is a different price sequence like 10,11,15 .


@ dews :
As per Ross, Get an algorithm first and try to implement first


Thumbs Up
Rajuvan.

[Updated on: Mon, 19 November 2007 00:36]

Report message to a moderator

Re: selecting a best combination of numbers from a list of numbers [message #281692 is a reply to message #281680] Mon, 19 November 2007 00:58 Go to previous messageGo to next message
sundha
Messages: 6
Registered: November 2007
Junior Member
Hi Raju,

It would help me to solve this problem, if you tell me which two products should be returned when the products price are 11,10 and 15.

Thanks in advance,
Sundari
Re: selecting a best combination of numbers from a list of numbers [message #281697 is a reply to message #281617] Mon, 19 November 2007 01:05 Go to previous messageGo to next message
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
Senior Member

Hi Sundari,

Thats what I am telling OP (Not me ) Need to build a Logic/Algorithm.

In case of 10,11,15 and say two more Prices 23 and 2 ).

Your query will return 10,11 when there is One better combination of 10,15 exists .

For your question , let me give you my combination 10 and 15
(out of 10,11,15) Just try Smile

Thumbs Up
Rajuvan.
Re: selecting a best combination of numbers from a list of numbers [message #281708 is a reply to message #281623] Mon, 19 November 2007 01:22 Go to previous messageGo to next message
Michel Cadot
Messages: 64139
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Provide a test case: create table and insert statements.
Tell us you Oracle version (at least 3 decimals).

Regards
Michel
Re: selecting a best combination of numbers from a list of numbers [message #281710 is a reply to message #281708] Mon, 19 November 2007 01:25 Go to previous messageGo to next message
Littlefoot
Messages: 20901
Registered: June 2005
Location: Croatia, Europe
Senior Member
Account Moderator
Whoa! That's something new? No more 4 decimals? Wink

P.S. Forgot to mention (while making fun, shame on me!): you (Dews, not Michel) might want to search for "Operations Research"; such things are discussed there.

[Updated on: Mon, 19 November 2007 01:30]

Report message to a moderator

Re: selecting a best combination of numbers from a list of numbers [message #282075 is a reply to message #281617] Tue, 20 November 2007 15:27 Go to previous messageGo to next message
dews
Messages: 7
Registered: November 2007
Junior Member
I was looking for a better solution where i can achieve this with less lines of code. I wrote a lengthy pl/sql code where i stored all combinations of numbers and thier sum in a different array. At the end i check at the resultant array and picked the best cobination.

Thanks for your kind suggestions.
Re: selecting a best combination of numbers from a list of numbers [message #282077 is a reply to message #282075] Tue, 20 November 2007 15:37 Go to previous messageGo to next message
pablolee
Messages: 2835
Registered: May 2007
Location: Scotland
Senior Member
A quick hint. If you already have a solution and are looking for a faster method, it would be courteous for you to point that out at the start of your thread. What if someone spent their own time working on a solution that you already had?
Re: selecting a best combination of numbers from a list of numbers [message #282171 is a reply to message #282077] Wed, 21 November 2007 01:17 Go to previous messageGo to next message
Michel Cadot
Messages: 64139
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
And it would be courteous to post a test that we don't to build it just to help you.

Regards
Michel
Re: selecting a best combination of numbers from a list of numbers [message #282190 is a reply to message #282171] Wed, 21 November 2007 02:10 Go to previous messageGo to next message
dews
Messages: 7
Registered: November 2007
Junior Member
No i tried several times but i couldn't succeed in writing. That's why i posted in the forum expecting good suggestions from senior members of the forum.

This was due for the delivery on yesterday morning. So i sat down again on the night before yesterday and i could succeed in that.

[Updated on: Wed, 21 November 2007 02:14]

Report message to a moderator

Re: selecting a best combination of numbers from a list of numbers [message #282196 is a reply to message #282190] Wed, 21 November 2007 02:46 Go to previous messageGo to next message
Michel Cadot
Messages: 64139
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
And maybe I could help if only you posted a full test case.

Regards
Michel
Re: selecting a best combination of numbers from a list of numbers [message #283046 is a reply to message #281617] Mon, 26 November 2007 00:29 Go to previous messageGo to next message
kir_ait
Messages: 198
Registered: November 2007
Location: Bangalore,India
Senior Member

Quote:

(Sundhari = Beautiful Lady in Indian Languages )


Not only Sundari, TripuraSundari!

Regards,
Kiran
Re: selecting a best combination of numbers from a list of numbers [message #285095 is a reply to message #282190] Mon, 03 December 2007 06:55 Go to previous messageGo to next message
sundha
Messages: 6
Registered: November 2007
Junior Member
Hi,

You can use the following queries for your requirement. I hope the product is not duplicated within a category.

I assume the total price should be less than or equal to 25, then you can use the following query

SELECT * FROM ( SELECT a.categories, a.combo,SUM(b.PRICE) tot_price,COUNT(PRODUCT),rank () OVER (PARTITION BY a.categories ORDER BY SUM(b.PRICE) DESC) price_rank
FROM (SELECT categories, SYS_CONNECT_BY_PATH (PRODUCT, '#') || '#' combo FROM PRODUCT_DETAILS
CONNECT BY PRIOR categories = categories AND PRODUCT > PRIOR PRODUCT) a, PRODUCT_DETAILS b WHERE b.categories = a.categories AND INSTR (a.combo, '#' || b.PRODUCT || '#') > 0
GROUP BY a.categories, a.combo HAVING SUM (b.PRICE) <= 25
AND COUNT(PRODUCT) <=3 ) WHERE price_rank = 1


With Regards,
Sundari
Re: selecting a best combination of numbers from a list of numbers [message #285098 is a reply to message #281617] Mon, 03 December 2007 07:13 Go to previous messageGo to next message
kir_ait
Messages: 198
Registered: November 2007
Location: Bangalore,India
Senior Member

Hi Sundari,

Difficult to read this code, format it. Use [CODE] tag before post.

Regards,
Kiran.
Re: selecting a best combination of numbers from a list of numbers [message #285099 is a reply to message #285095] Mon, 03 December 2007 07:15 Go to previous message
Michel Cadot
Messages: 64139
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
And pretty format it and limit your lines to 80 characters.

Regards
Michel
Previous Topic: I want Pass4sure exam 1z0-001
Next Topic: Design problem
Goto Forum:
  


Current Time: Fri Dec 09 02:10:54 CST 2016

Total time taken to generate the page: 0.06035 seconds